Sorting – Quick Sort

A post dedicated to that oh so famous, Quick sort! ^^

Quick Sort

Quick Sort is very similar to the Merge Sort in the previous post, such to the fact that it also uses the Divide-and-Conquer strategy:

• DIVIDE – If a sequence S has zero or one element, simply return it. Otherwise we need to select one of the elements in S, which is most commonly the last element in S. This element is our pivot. With this we then need to split S into three new sequences.
  • A sequence L for elements less than the pivot.
  • A sequence E for elements equal to the pivot.
  • A sequence G for elements greater than the pivot.
    
• RECURSIVLEY – We then need to sort the sequences L and G. Not E, can you thing why? :)
  
• CONQUER – Put the elements from L, E and G back into S. first place the elements from L into S, then that of E and finally that of G.

Now, like a merge sort, a quick sort also divides up a sequence into more sequences to create subproblems. However, unlike a merge sort, when a merge sort divides up its sequences, the maximum height of the tree created in log(n), because we don’t care what the values are. But, with a quick sort, the maximum height of the tree can be n-1 in the worse case. This is because if the sequence is already sorted, and we constantly select the pivot as the last element, then we’re only creating an ‘L’ sequence every time. Therefore, in order to solve this, we use a randomized quick sort, such that we randomly select an element to be the pivot. Although this doesn’t perfectly solve it – you could still have a very bad chose of random elements! :(

 

Example

Okay, enough babble, time for an example – lets consider the same elements as from the merge sort.

Here, the number is red is the pivot. And yes, i was an idiot, i stupidly made the pivot the highest element, doh! Ah well, this now has the chance for you to see a possible worse case quick sort :D

Anyway. As you can see, the numbers in the left new sequence are the elements less than 74. But since there are none that are greater than 74, then the left sequence is left empty. the third sequence, for values equal to the pivot is there, im just not showing it :) just imagine that the pivot ‘stays’ in the original sequence S.

a few steps later and we get this:

If you see an error in this – please tell me =S

With this, we do something similar to the merge sort. That is, put the sequences back together whilst sorting them into the correct order:

Complexity

the quick sort is very similar to the merge sort for its complexity explaination’s. However, this time we have to discuss best and worse case. In the best case, we have a tree height as log(n) and we spend O(n) at each level; therefore the best case complexity is O(n log n). However, the worse case is O(n^2), this happens if the list is already sorted, and the tree is n-1 in height.