We left our series of Sorting Algorithms about two months ago. Till then we discussed many in-place sorting algorithms like insertion sort, bubble sort, selection sort and gnome sort. These all were the basic algorithms which were inefficient for sorting large lists. For large amount of data, very advanced sorting algorithms have been developed by the experts and a lot of research is still going on in this area. According to many, the fastest Sorting Algorithm in Computer Science is the Quick Sort Algorithm. I shall explain this brilliant algorithm to you in this article in detail. Afterwards we would together write a source code for that.
Basic Structure of Quick Sort:
Quick sort is a divide and conquer algorithm. It divides the list into smaller sub lists and follows the path of recursion to sort them individually. The basic principle in quick sort is the concept of a mean value or middle value in the whole of list. This middle value is known as a Pivot.
The idea is to select a middle value or a pivot from the list. Move smaller values than the pivot to its left and larger values to its right. So there would be two lists. One consists of all the values smaller than the pivot. Second consists of all the values equal to and greater to the pivot. Pivot serves as the boundary between these two parts. Consider these two sub lists separately one by one.
In the sub list, select a pivot value again and divide that sub list into two portions again; one of values smaller than the pivot and second of values greater than the pivot. Then these two portion sub lists would again be sorted according to the same pattern; selecting a pivot value and sorting the resulting lists. Follow this procedure recursively until the size of the smaller list becomes equal to one. Pretty Cool? Yeah.
Selecting the Pivot for Quick Sort:
The whole building of quick sort is built around the pivot value. I referred to pivot as the middle or mean value from the list. For example if we have this list with us.
10, 43, 29, 65, 23, 50, 32.
In this list, the pivot value is 32 because there are 3 values smaller than 32 and 3 values greater than 32. In sorted form, we can write the list as follows.
10, 23, 29, 32, 43, 50, 65
Now the question arises: How to identify and select the pivot value? Well there are several methods of selecting the pivot value. Some of which are these.
- Select the first value of the list as pivot. Compare all other values with it and adjust the list accordingly.
- Select the last value of the list as pivot. Compare all other values with it and adjust the list accordingly.
- Select a random value from the list. Some people employ this method and argue that it reduces the computational complexity.
- Select two or three different values randomly and take their middle value as the pivot.
Regardless of the method of selecting the pivot, pivot is an integral part of the Quick Sort Algorithm. In our next post when I shall explain quick sort by an example and how to select a pivot in detail.
Recursion in Quick Sort:
Quick sort algorithm is a recursive algorithm. You are very much familiar with recursion by now as I explained it to you in detail in relation with Selection Sort. Nevertheless, recursion is basically calling the same function within its own body. Remember that we employ recursion whenever a process is repeating itself in our program in the same manner.
In Quick sort, we divide a large list into smaller lists, select a pivot for each of these lists and then again divide its two parts into further two parts each and so on, until we get a list of such small size that can be sorted easily. So recursion is employed here. Without recursion, quick sort becomes extremely difficult to manage. In fact what makes quick sort the fastest algorithm is the recursive technique. The computational complexity or running time of Quick Sort is O (nlog(n)) which is very close to that of binary search algorithm. Bubble Sort and Selection Sort have a running time of O (n2) whereas Insertion sort has running time of O (n). Imagine the difference!!!
In the next post, I would be taking up a sample list and sort it step by step. We would also write a basic source after explaining that example. Save your thumbs till then!