# Tag Info

22

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case. Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array ...

22

The memory access pattern in Quicksort is random, also the out-of-the-box implementation is in-place, so it uses many swaps if cells to achieve ordered result. At the same time the merge sort is external, it requires additional array to return ordered result. In array it means additional space overhead, in the case if linked list, it is possible to pull ...

21

This particular implementation of quicksort is not in-place. It treats the data structure as a list that can only grow in one direction (in which case a merge sort would be simpler and faster). However, it is possible to write an in-place implementation of quicksort, and this is the way it is usually presented. In an in-place implementation, instead the ...

16

Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat. This ...

14

Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns. So the running time of quicksort ...

13

We are indeed assuming $P(k)$ holds for all $k < n$. This is a generalization of the "From $P(n-1)$, we prove $P(n)$" style of proof you're familiar with. The proof you describe is known as the principle of strong mathematical induction and has the form Suppose that $P(n)$ is a predicate defined on $n\in \{1, 2, \dotsc\}$. If we can show that $... 12 In order to know that you may just decrement gt, you have to compare the element at position gt to the pivot. For illustration, here is the relevant part of the code from the slides you took your illustration from: while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) exch(a, lt++, i++); else if (cmp > 0) exch(a, i, gt--); ... 12 You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator? The answer: Of course. You can run any algorithm with any input. However, you know the rule: Garbage In, Garbage Out. If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output. In particular, there is no guarantee that the output will ... 11 I tried to do exactly such a comparison in my master thesis, which thus naturally includes pseudo-code of “basic” versions of several dual-pivot Quicksorts (there is a list of them on page 9). Here is my basic implementation of Yaroslavskiy's algorithm (the dual-pivot scheme that is used in Java 7): void sort(int[] A, int left, int right) { if (right &... 10 Using the mean for your partition does not prevent the$\Omega(n^2)$worst-case behavior. It occurs when the input list is exponentially increasing. Consider the input:$1,n^2,n^3,\ldots,n^n$The mean of this set is (asymptotically)$n^{n-1}$so you obtain the worst partition possible. This is a bit of a cheat considering that storing the list takes$\...

8

Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$. When the presenter is speaking about linear time for partition, this is a stronger statement than $O(n)$ time. All linear functions are in $O(n)$, but it also contains non-linear functions. For example: $\sin n, \... 7 Some comments added to the excellent Sebastian answer. I'm going to talk about the partition rearrangements algorithm in general and not about its particular use for Quicksort. Stability Lomuto's algorithm is semistable: the relative order of the elements not satisfying the predicate is preserved. Hoare's algorithm is unstable. Element Access Pattern ... 7 If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers? The worst case is when the selected pivot reduces the problem size by the smallest possible amount, i.e. provides ... 7 This proof uses the principle of complete induction: Suppose that: Base case:$P(1)$Step: For every$n > 1$, if$P(1),\ldots,P(n-1)$hold (induction hypothesis) then$P(n)$also holds. Then$P(n)$holds for all$n \geq 1. You can prove this principle using the usual induction principle by considering the property $$Q(m) \... 6 You were missing that these texts talk about "worst case expected run time", not "worst case runtime". They are discussing a Quicksort implementation that involves a random element. Normally you have a deterministic algorithm, that is an algorithm which for a given input will always produce the exact same steps. To determine the "worst case runtime", you ... 6 The short answer is that the O(n\log n) component dominates the O(n) component, hence the O(n) part can be ignored in the statement of complexity. 6 "The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail. The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot.... 6 The short answer is no, in the worst-case comparison based algorithms, for reasons stated here. Using a counting technique will at least take O(n \log n) worst case and O(n \log k) if you use a BST. Here I'll give a variant of quick-sort which also achieves O(n \log k) With a slight modification and a more careful analysis of quick-sort. We will ... 5 Some Context and History FrankW's post answers most of the question, but I can add some references and give some context to it. First of all, the algorithm is named after Dijkstra because of his 1976 programming book “A Discipline of Programming”, wherein chapter 14 deals with the so-called “Dutch National Flag Problem (DNFP)”: Rearrange an array of red, ... 5 If \alpha=0.5, then 1-2 * 0.5 = 0, which says that the smaller subarray cannot have length greater than half the original, since then it would be the larger subarray. If \alpha=0, then 1-2 * 0 = 1, so the size of any subarray must be greater than or equal to zero. The pivot is randomly chosen, so uniformly distributed between 0 and 1. The ... 5 The term "Quicksort" stands for this abstract algorithmic idea: Pick a value x. Partition the input into \{y\mid y \leq x\} and \{y \mid y > x\}. Recurse on the partitions (if they are non-trivial) and append the results. You may want to generalise to multiple pivots, or create a third partition for elements equal the pivot, but mostly that's it. ... 5 The phrase in Cormen is a bit obscure (and does read a bit quaint). A 1978 paper by Sedgewick "Implementing Quicksort Programs" has a nutshell on this: The hardware feature on modern computers that has the most drastic effect on the performance of algorithms is paging. Quicksort actually does not perform badly in a virtual memory situation (see [2]) ... 5 Your mistake is 2\mathcal{O}(n/2) = \mathcal{O}(n/2). More generally, in order not to be confused, it is much better to replace \mathcal{O}(n) with An for some constant A, which can be taken as 1 without loss of generality. Then we have$$ \begin{align*} T(n) &\leq 2T\left(\frac{n}{2}\right) + n \\ &\leq 4T\left(\frac{n}{4}\right) + 2 \frac{... 5 You can quick sort linked lists however you will be very limited in terms of pivot selection, restricting you to pivots near the front of the list which is bad for nearly sorted inputs, unless you want to loop over each segment twice (once for pivot and once for partition). And you will need to keep a stack of the partition boundaries for the lists you still ... 5 The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot. In pseudocode, the algorithm looks like the following. algorithm quicksort(A, lo, hi): if lo < hi then p ← pivot(A, lo, hi) left, right ← three-way-partition(A, p, lo, ... 5 The worst case for the Quicksort algorithm depends how a pivot is chosen and it can range from\Theta(n \log n)$(if you choose the pivot to be the median) to$\Theta(n^2)$(if the pivot is always a constant number of elements away from the minimum/maximum element). That said, C++ standards do not mandate any particular implementation of the sort() ... 5 The partition method in the question, partition(a, lo, hi) is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort. Here is the situation. There are$n$numbers that are non-equal pairwise. Array$a=(a_0, a_1, \cdots, a_{n-1})$is a uniformly-random permutation of those$n$numbers. We will run the method partition(a,... 4 Inversions are one way to measure "disorder" in a list: Let$A[1..n]$be an array of$n$distinct numbers. If$i < j$and$A[i] < A[j]$then the pair$(i,j)$is an inversion of$A$. However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly: An integer function on a permutation$\...

4

The relative costs of various operations are different on different machines, and compilers have varying degrees of ability to optimize various constructs. David Richerby goes into somewhat more detail on that, but the last half-sentence of the highlighted quote is perhaps the most important. In many cases where one algorithm is more efficient than another ...

4

Given a set of elements and a binary ordering relation, transitivity is required to totally order the elements. In fact, transitivity is even required to define a partial order on the elements. http://en.m.wikipedia.org/wiki/Total_order You would need a much broader definition of what "sorted" means in order to sort elements without transitivity. It is ...

Only top voted, non community-wiki answers of a minimum length are eligible