# Tag Info

103

Pedagogical Dimension Due to its simplicity Lomuto's partitioning method might be easier to implement. There is a nice anecdote in Jon Bentley's Programming Pearl on Sorting: “Most discussions of Quicksort use a partitioning scheme based on two approaching indices [...] [i.e. Hoare's]. Although the basic idea of that scheme is straightforward, I have ...

21

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 ...

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 ...

20

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 ...

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$\...

7

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 ...

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 We're talking about algorithms to sort a list. Therefore, in this context, a problem of size 0 is a list of size 0, i.e., the empty list. Quicksort splits a list of size n into two sublists of size m and n-m-1. They sum to n-1 (not n), because quicksort removes the pivot element: the pivot element is not included in either sublist. Therefore, ... 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 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 ... 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 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 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 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 ... 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 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

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 ...

4

Take a look at McIllroy and Douglas' "A Killer Adversary for Quicksort" (Software -- Practice and Experience 29(4): 341-344 (1999)) or Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks" for the reason behind randomizing. Quicksort behaves very badly if you pick (nearly) the largest/smallest as pivot each time. For randomization to ...

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 ...

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