New answers tagged sorting
1
The answer depends on what you mean by a sorting algorithm. The usual meaning is:
A sorting algorithm is an algorithm that gets a list $L$ of comparable objects, and sorts them in (say) nondecreasing order. The algorithm could only work for a certain class of objects.
If you use this definition, then PageRank isn't a sorting algorithm. But it's up to you....
4
For constant $p>0$ there is no way to exactly sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order.
In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation1 $D$ with high probability, ...
2
Your problem has been considered by Braverman and Mossel in their paper Noisy sorting without resampling. The paper has generated quite a lot of follow-up work, some of which might be more practical than the original algorithm suggested by Braverman and Mossel.
1
This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your convention.
The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)...
1
The algorithm that uses "sort of quicksort" to find the $k$-th smallest (or largest) element is generally called quickselect.
Here is the precise meaning of "the average complexity of quickselect is $O(n)$" as commonly understood. Or one of its precise meanings.
the precise statement
There exists a constant $c$ such that given two integer $n$ and $k$ such ...
1
There is no requirement that $k$ be constant, and those StackOverflow comments are misleading or simply incorrect.
Obviously $k \le n$ and so $k$ is $O(n)$. Your partial bubblesort algorithm is $O(kn)$ which is $O(n^2)$ unless $k$ is somehow restricted.
But the Quickselect algorithm is stochastic $O(n)$ and can be made worst-case $O(n)$ by using the median-...
2
The worst-case time complexity of an algorithm is the time complexity for the worst-case input. Insertion sort takes $\Theta(n^2)$ in the worst-case, not $O(n)$. However, mergesort and heapsort each take $\Theta(n \log n)$ in the worst-case, and so achieve the $\Omega(n \log n)$ lower bound.
Suppose $n!$ is roughly $1000$, so that $\log n!$ is about $10$ (...
2
The lower bound is for the worst-case number of comparisons. Every comparison-based sorting algorithm performs $\Omega(n\log n)$ comparisons in the worst case. This means that the tree has depth $\Omega(n\log n)$.
If you don't like the tree argument, here is an adversary argument which is basically a reformulation of the tree argument. We will maintain the ...
2
Suppose the input array has $n$ elements. The goal of the sorting algorithm is to compute a permutation of $\{1,2,\ldots,n\}$ - the permutation needed to sort the input. Let $A$ be the set of these $n!$ permutations.
Similar to the "guess my number" game (or the game of 20 questions), each comparison can reduce the search space by a factor of at most $2$....
1
There are n! possible orderings for n items. Each comparison reveals only 1 bit of information, so to choose one of n! orderings you need to perform at least log2(n!) comparisons.
log(n!) < C*n*log(n) for some C is known from Math, so log(n!) = O(n*log(n)) by definition of O.
0
Writing a Quicksort implementation where n equal items take $O(n^2)$ is just stupid.
A good implementation will split the array into items less than the median, equal to the median, and greater than the median. That will sort an array of all equal elements in O(n).
1
It depends on the partition algorithm used. Some might be $O(n^2)$ if they put all equal elements on the same side while others remain $O(n \log n)$ if they split the equal elements.
2
In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have ...
1
Let us first recall how quicksort works. We start by choosing a pivot — in your case $M_8$. We then partition the array into elements smaller than the pivot and larger than the pivot (breaking ties arbitrarily), and reorder the array in the following way:
elements smaller than the pivot; the pivot; elements larger than the pivot
We then recursively ...
1
AVL trees, like all other binary search trees, have the following guarantee:
Suppose that $v$ is a node with left child $l$ and right child $r$. If $x$ is a node in the subtree rooted at $l$ and $y$ is a node in the subtree rooted at $r$ then $key(x) \leq key(v) \leq key(y)$.
Using this, you can easily prove by induction that the inorder traversal of a ...
0
The theoretical lower bound on comparison based sorting is $\log(n!)$.
That is to say that to sort $n$ items using only $<$ or $>$ comparisons it takes at least the base 2 logarithm of $n!$, hence $\log(5!) \approx 6.91$ operations.
Since $5!= 120$ and $2^7= 128$,
using a binary decision tree you can sort 5 items in 7 comparisons.
The tree figures out ...
2
The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence
$$ T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n), $$
whose solution is $T(n) = O(n\log n)$.
Top 50 recent answers are included
