Hot answers tagged

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


61

This algorithm can be re-written like this Scan A until you find an inversion. If you find one, swap and start over. If there is none, terminate. Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the ...


43

In general terms, there are the $O(n^2)$ sorting algorithms, such as insertion sort, bubble sort, and selection sort, which you should typically use only in special circumstances; Quicksort, which is worst-case $O(n^2)$ but quite often $O(n\log n)$ with good constants and properties and which can be used as a general-purpose sorting procedure; the $O(n\log n)...


35

It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases: $$ 1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\ 1,2,\ldots,i-1,i+1,i,i+2,\ldots,n $$


34

All complexities you provided are true, however they are given in Big O notation, so all additive values and constants are omitted. To answer your question we need to focus on a detailed analysis of those two algorithms. This analysis can be done by hand, or found in many books. I'll use results from Knuth's Art of Computer Programming. Average number of ...


31

The following answer is basically equivalent to the one you already know, but may seem a bit less "magical". On the other hand, it's more technical, but I believe the general technique "write your problem as an optimization on permutation matrices and invoke Birkhoff-von Neumann" is a great one to know. For a permutation $\sigma$ of $\{1, \ldots, n\}$ ...


31

No, it depends on your application. The measures of sortedness are often refered to as measures of disorder, which are functions from $N^{<N}$ to $\mathbb{R}$, where $N^{<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood [1] lists and discusses 11 different measures of disorder in the ...


30

The solution is wrong. Demuth [1; via 2, sec. 5.3.1] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance. The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline: Sort the first two pairs. Order the pairs w.r.t....


29

The confusion arises from difference between the conceptual description of the algorithm, and its implementation. Logically merge sort is described as splitting up the array into smaller arrays, and then merging them back together. However, "splitting the array" doesn't imply "creating an entirely new array in memory", or anything like that - it could be ...


23

There is only one way to start this process (and for nearly all of your decisions of what to compare in later steps, there is only one correct one). Here's how to figure it out. First, note that there are $2^7 =128$ possible answers you can get for your comparisons, and $5! = 120$ different permutations you need to distinguish between. The first comparison ...


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


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

When we say an algorithm runs in $O(\lg k)$ time, that is an asymptotic statement. It means that there exists a constant $c$ such that when $k$ is sufficiently large, the running time is $\le c \lg k$. It says nothing about what happens when $k$ is small. In particular, if we say an algorithm runs in $O(\lg k)$ time, that doesn't necessarily mean that ...


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


19

If the input array is distributed uniformly at random then (as you noted) there is no difference between always picking an element at a fixed position (for example the middle one as you suggest) or picking an element chosen at random. If however your input array is not really in random order (which happens to be the case in almost all practical scenarios) ...


19

if we have a list of $n$ numbers we need $\log n$ bits No: if we have a list of numbers between $0$ and $2^k - 1$, we need $k$ bits. There is no relationship between $k$ and $\log n$ in general. If the numbers are all distinct, then $\log n \ge k$, and radix sort on distinct numbers therefore has a time complexity of $\Omega(n \log n)$. In general, the ...


17

If you naively apply the algorithm you need an encoding $f$ of strings of length $m$ into integers such that $s_1≤s_2$ iff $f(s_1)≤f(s_2)$. The bound on these integers is necessarily at least $c^m$ where $c$ is the number of possible characters. You then have a complexity in $O(nc^m)$ where $n$ is the number of elements to be sorted. This could be ...


17

My experience working with real world data is that quicksort is a poor choice. Quicksort works well with random data, but real world data is most often not random. Back in 2008 I tracked a hanging software bug down to the use of quicksort. A while later I wrote simple implentations of insertion sort, quicksort, heap sort and merge sort and tested these. My ...


16

Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines. Zagha and Blelloch: Radix sort for vector multiprocessors. Supercomputing, 1991: 712-721. Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha: A Comparison of Sorting Algorithms for the Connection Machine CM-2. Symp Parallel Algorithms and Arch (SPAA-3):3-16, 1991. ...


15

The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.


15

The answer, as is often the case for such questions, is "it depends". It depends upon things like (a) how large the integers are, (b) whether the input array contains integers in a random order or in a nearly-sorted order, (c) whether you need the sorting algorithm to be stable or not, as well as other factors, (d) whether the entire list of numbers fits in ...


14

Under what conditions is a specific sorting algorithm actually the fastest one? When implemented in a parallel way in hardware, does it need to have a reasonably low latency while requiring as few gates as possible? Yes, use a bitonic sorter or Batcher odd-even mergesort, latency is $\Theta(\log(n)^2)$ and the number of comparators and multiplexers is $\...


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


14

You haven't specified your computation model, so I will assume the comparison model. Consider the special case in which the array $B$ is taken from the list $$ \{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}. $$ In words, the $i$th element is either $2i-1$ or $2i$. I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, ...


14

Consider cocktail shaker sort, which is a bidirectional version of bubble sort. You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done. This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final ...


13

Quicksort: For quicksort, your intuition about recursion requiring O(log(n)) space is correct. Since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log(n)) space complexity. Mergesort: Since mergesort also ...


13

You got a result of $O(N\cdot \log(\sqrt N)+N\log(\sqrt N))$. But $\log \sqrt N = (\log N)/2$, so $N⋅log(\sqrt N)+N·\log(\sqrt N) = N·\log N$. So not only is it the same complexity class, where constant factors don't matter, it is even the same function, therefore the same constant factor. But the underlying reason for any comparison based sorting ...


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


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

I suggest a variation of distribution counting: Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count say maxWordCound . -- $O(n)$ Initialize an array of size maxWordCount. Entry type are lists of strings. -- $...


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