December 5, 2010 Leave a comment
As the name suggests, quick sort is indeed a quick sorting technique.
Suppose that you have to sort an array of n integers. The method used in quick sort is to choose a pivot element, traverse the array and rearrange the elements such that all elements less than (or equal to) the pivot element are placed to the left of the pivot element, and those that are greater than the pivot element are placed to its right.
What we can observe here is that the pivot element has been placed in its correct final position (i.e. the position where it would be after the array is completely sorted).
So, now we need to only concentrate on rearranging the elements to the left and to the right of the pivot element. And to do so, we perform quick sort separately on the left-elements and on the right-elements.
Let’s look at an example.
Suppose the array we want to sort is: 23 12 3 43 26 18 95 6 34 11.
1. We observe first of all that if an array has just one element, or has no elements, the array is trivially sorted.
2. First, we select a pivot element. Let’s say it is 23.
3. We traverse the array once from left to right, and divide the elements into two parts (those less than, and those greater than, the pivot).
We compare 12 to 23, and find that 12 < 23 and hence, 12 would occur to the left of 23 at the end of this stage. We then compare 3 to 23, and again finding that 3 < 23, place 3 to the left of 23. Next, we compare 43 to 23. We find that 43 > 23, and hence place 43 to the right of 23. We similarly go through each of the remaining elements of the array, and place them either to the left or to the right of the pivot element.
At the end of this step, the array that we have is as follows:
12 3 18 6 11 23 43 26 95 34.
Before proceeding to the next step, we observe an important point: at the end of Step 3, we find that the pivot element 23 is placed in position # 6, which is also its rightful position in the completely sorted array.
4. We now look to sorting two smaller arrays — the ones to the left and to the right of the pivot element.
We resort to recursion in order to sort the arrays (12, 3, 18, 6, 11) and (43, 26, 95, 34).
[In order to sort the array on the left, we select a pivot (let’s say 12) and repeat Step 3 and Step 4 for this array. Similarly, we sort the array on the right of the pivot element. While doing so, we keep in mind the observation in Step 1.]
Running time of Quick Sort algorithm (best-case scenario) :
1. Let’s say we always select the first element of the array as the pivot element. So, it takes O(!) time to select the pivot element.
2. Now, we use the pivot element to divide the array into elements less than (or equal to) and greater than the pivot element. This division of the array takes O(n) time (where n refers to the size of the array).
3. In our best-case scenario, we assume that the array gets divided into 2 (almost) equal halves. (i.e. the pivot element always divides the array as equally (in size) as possible).
Thus, we get the following recurrence relation:
T(n) <= 2 T(n/2) + kn.
Here, T(n) refers to the running time of the algorithm on an array of size n, and k is a constant.
We also have, T(1) = T(0) = O(1) [this is another way of writing what we wrote earlier in Step 1.]
Thus, we get T(n) is O(n log n).
Now, let’s look at the worst-case running time of Quick Sort.
To look for the worst-case scenario, we’ll assume that the pivot element always divides the array as unequally as possible.
Consider the following array:
2 5 9 14 45 56 89.
If we always use the first element as the pivot element, we find that the array gets divided in a totally lop-sided manner.
The recurrence that we get is as follows:
T(n) <= T(n-1) + kn.
This means that T(n) is O(n^2).
A final note: Always selecting the first element as pivot can lead us into trouble (as we saw above in the worst-case scenario). A way of somewhat circumventing this problem is to pick the pivot element randomly from among the elements of the array. This is what is known as randomized quick sort.