QuickSelect works in linear time

QuickSelect is a selection algorithm that finds the kth smallest number from a list. QuickSelect is O(n) algorithm. I built a simple prototype to verify that QuickSelect works in linear time.

QuickSelect uses a random pivot to partition the array. The items to the left of the pivot are lesser than the pivot. The items to the right of the pivot are greater than the pivot. After the partition, the position of pivot is checked for the kth element. Depending on the position of the pivot, the remaining array is recursively partitioned till the kth element is found. The code for QuickSelect is below:

QuickSelect uses a random pivot. So, the running time of the algorithm for the same input varies based on the chosen pivot. The average running time of QuickSelect varies linearly by the input size. For this experiment, five array sizes of 50K, 100K, 200K, 500K, 1000K were used to measure the running times. The result of the experiment is shown below:

QuickSelect

The running time is shown in milliseconds. For million numbers, QuickSelect runs at an average of 1.064 seconds. The final column shows the slope of the line. It is roughly between 0.8 and 1.1. It is nice to see for myself that QuickSelect works in linear time.

Leave a Reply

Your email address will not be published. Required fields are marked *