Hot answers tagged

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


46

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


37

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


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


32

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


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


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


18

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


18

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


17

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

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


15

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


14

Because you asked for minimum number of comparisons, so I assume the algorithm can only compare the numbers. The idea is to extend the sorting lower bound argument. Assume you want to sort $n$ elements knowing there exist at most $k$ distinct values. There are $n!$ ways to permute the elements, but many of them are equivalent. If there are $n_i$ element of ...


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


13

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


13

I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well. If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you ...


13

A sorting algorithm using at most $h$ comparisons on all inputs corresponds to a tree of height at most $h$. Such a tree has at most $2^h$ leaves. On the other hand, each permutation of $1,\ldots,N$ must land at a different leaf, and so there must be at least $N!$ leaves. Putting these together, we deduce that $2^h \geq N!$ and so $h \geq \log_2 N! = \Omega(...


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

The asymptotic cost, or $\mathcal O$-notation, describes the limiting behaviour of a function as its argument tends to infinity, i.e. its growth rate. The function itself, e.g. the number of comparisons and/or swaps, may be different for two algorithms with the same asymptotic cost, provided they grow with the same rate. More specifically, Bubble sort ...


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

If you run "balanced Quicksort" (using the exact median at every step) up to depth $k$ (at the cost of $O(n k)$), you get a partition of the original array into $2^k$ sorted parts of $n/2^k$ unsorted elements each. Given an element, we can locate the correct part in time $O(\log(2^k)) = O(k)$ using binary search, and then look it up using an additional $O(n/...


11

Furthermore, answering your second question Theoretically, is it possible that there are even faster ones? So, what's the least complexity for sorting? For general purpose sorting, the comparison-based sorting problem complexity is Ω(n log n). There are some algorithms that perform sorting in O(n), but they all rely on making assumptions about the ...


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


11

I suggest Tree Sort, variant with self-balanced tree. In this case complexity is $O(logn)$ (per insertion). In that case you can access sorted structure at any time. If inputs comes in batches, sort batch (with any fast algoritm) and then merge. Other algorithms will also suffer from divided input, but insertion sort is poor even if input is available at ...


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