4
$\begingroup$

I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I've heard, quicksort is preferred most of the times, yet still it has $O(n^2)$ complexity in case the array is sorted already.

My question is if there is a way to measure in linear time how sorted the array is, and then decide which algorithm is better to use. By measure I mean an algorithm that outputs 1 if the array is sorted already, values closed to 1 if just a few values are unordered, 0 if the input is sorted from the highest to the lowest value. Depending on this output, we could decide if it's a good idea to use quicksort, or we should use some other sorting algorithm.

$\endgroup$
  • $\begingroup$ Mergesort doesn't perform linearly on sorted arrays. It always incurs $n\log n$ time complexity, regardless of the array used. That's why quicksort is preferred in practice. Also, deterministic quicksort (i.e. not randomized) performs worst on an array backwards sorted (highest to lowest), when you intend to sort from low to high. $\endgroup$ – Jason Feb 17 at 16:48
  • $\begingroup$ What does "how sorted an array is mean"? Checking if the array is sorted (or sorted in reverse) can be done in linear time by making one pass. $\endgroup$ – GoodDeeds Feb 17 at 17:09
  • $\begingroup$ @Jason I guess I should edit, thanks. @GoodDeeds rather than "how an array is sorted" I want to know "how much the array is sorted". The idea would be to output a value between 0 and 1. The closer the output is to 1, the more the values are already sorted. For example, [1,2,3,4,5,7,6] is almost sorted, I would expect this fictional algorithm to output something like 0.9, while the score of [4,3,2,1] should be 0. Depending on this output, I shall choose which algorithm to use. $\endgroup$ – Giacomo Parolin Feb 17 at 21:53
  • $\begingroup$ Someone actually has a patent on “Determine which of several compression algorithms compresses some data set best, then compress the data set with that algorithm”. Worked for a company that got sued for violating the patent. We got around it in a ridiculously stupid way. $\endgroup$ – gnasher729 Feb 19 at 17:26
6
$\begingroup$

Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A good way to avoid this problem is to shuffle the whole input randomly before we start sorting.

Now to gain more information about how "sorted" the array is, we have to define this quantity formally. We need a formal mathematical definition of "sortedness" before we can design an algorithm to measure it. Here are two different quantities that show in some way the "sortedness" of the array. Let us call the input array $A := a_1, \dots a_n$ where $n$ is the length of the array.

The first of which is the number of "inversions". So what are inversions? - you might ask. Inversions are pairs $(i, j)$ such that $i < j$ and $a_i > a_j$. Of course in a sorted array we have no inversions. Counting inversions can be done in running time $O(n\log n)$ using different methods among which are divide and conquer and using balanced search trees. However since counting inversions is not faster than sorting, I would not recommend it to find how sorted an array is as a pre-sorting routine.

Another measure is the minimum number of elements to be removed to turn the array sorted. This problem is equivalent to finding the longest increasing subsequence and it has an $O(n \log n)$ algorithm using dynamic programming. However, there is an simple linear time two approximation algorithm for this problem. Intuitively, the algorithm removes pairs of adjacent inversions until the array contains no more inversions. In pseudo-code the algorithm goes as follows:

- Let L be an empty linked list
- For each a := a[1] .. a[n] do
 - Append a to L.
- Set i := 1
- While a[i] is not the last element in L
 - while  a[i] no the first element in L
     and a[i] < a[i-1] do
  - remove a[i] and a[i-1] from L
  - Set i to the next element.
 - Set i to the next element.

Each time we remove two elements from $L$, they form an inversion an at least one of them should be removed. Hence we remove at most twice as many as the total number of elements that must be removed. Note that the running time can be bounded in $O(n)$ since the outer while iterate over all elements once and each call of the inner loop removes two elements and hence it can not be called more than $O(n)$ times in total.

One way to use this measure to sort arrays more efficiently is to use the previous algorithm to find all such pairs. Let $L_1$ be the list above after removing the elements from it and $L_2$ the list of all removed elements. Now since we know that $L_1$ is sorted, all we need to do is to sort $L_2$ in $O(h\log h)$ assuming $h$ is the number of elements has to be removed to turn the array sorted. Using some kind of sliding window (the conquer part of merge sort), we can build a sorted version of $A$ combining $A_1$ and the sorted version of $A_2$ in linear time. In total we get an adaptive sorting algorithm running in $O(n + h \log h)$.

$\endgroup$
0
$\begingroup$

So you learnt that Quicksort takes quadratic time for an already sorted array.

Exercise 1: implement Quicksort so it takes O(n log n) for a already sorted array.

Exercise 2: implement Quicksort so it takes linear time in this case.

$\endgroup$
  • $\begingroup$ For exercise 2, is the only variation allowed the choice of pivot? $\endgroup$ – Daniel M Gessel Feb 19 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.