Quick select

The quickselect algorithm is used to obtain the kth smallest element in an unordered list of items, and is based on the quicksort algorithm. In quicksort, we recursively sort the elements of both the sublists from the pivot point. In quicksort, in each iteration, we know that the pivot value reaches its correct position in the list with two sublists (left and right sublists), having all of their elements set to be unordered.

However, in the case of the quickselect algorithm, we recursively call the function exclusively for the sublist that has the kth smallest element. In the quickselect algorithm, we compare the index of the pivot point with the k value to obtain the kth smallest element from the given unordered list. There will be three cases in the quickselect algorithm, and they are as follows:

  1.  If the index of the pivot point is smaller than k, then we are sure that the kth smallest value will be present in the right sublist from the pivot point. So, we only recursively call the quickselect function for the right sublist. 
  2. If the index of the pivot point is greater than k, then it is obvious that the kth smallest element will be present in the left side from the pivot point. So, we only recursively look for the ith element in the left sublist.
  3. If the index of the pivot point is equal to k, then it means that we have found out the kth smallest value, and we return it.

Let's understand how the quickselect algorithm work by looking at an example. Let's consider a list of elements, {45, 23, 87, 12, 72, 4, 54, 32, 52}, where want to find out the 3rd smallest element from this list—we do this by using the quicksort algorithm.

We start the algorithm by selecting a pivot value, that is, 45. After the first iteration of the algorithm, we place the pivot value to its correct position in the list, that is, at index 4 (the index is starting from 0). Now, we compare the index of the pivot value (that is, 4 ) with the value of k (that is, 3rd position, or at index 2). Since this is at the k<pivot point (that is, 2<4), we only consider the left sublist, and recursively call the function.

Now, we take the left sublist and select the pivot point (that is, 4). After the run, the 4 is placed at its correct position (that is, the 0th index). As the index of the pivot is less than the value of k, we consider the right sublist. Similarly, we take 23 as the pivot point, which is also placed at its correct position. Now, when we compare the index of the pivot point and the value of k, they are equal, which means we have found the 3rd smallest element, and it will be returned. 

This process is also shown in the following diagram:

To implement the quickselect algorithm, we first need to understand the main function, where we have three possible conditions. We declare the main method of the algorithm as follows:

    def quick_select(array_list, left, right, k): 

split = partition(array_list, left, right)

if split == k:
return array_list[split]
elif split < k:
return quick_select(array_list, split + 1, right, k)
else:
return quick_select(array_list, left, split-1, k)

The quick_select function takes the index of the first element in the list—as well as the last —as parameters. The ith element is specified by the third parameter, k. The value of k should always be positive; the values greater or equal to zero (0) are only allowed in such a way that when k is 0, we know to search for the first-smallest item in the list. Others like to treat the k parameter so that it maps directly with the index that the user is searching for, so that the first-smallest number maps to the 0 index of a sorted list.

A method call to the partition function, split = partition(array_list, left, right), returns the split index. This index of the split array is the position in the unordered list where all elements between right to split-1 are less than the element contained in the split array, while all elements between split+1 to left are greater.

When the partition function returns the split value, we compare it with k to find out if the split corresponds to the kth items.

If split is less than k, then it means that the kth smallest item should exist or be found between split+1 and right:

In the preceding example, a split within an imaginary unordered list occurs at index 5, while we are searching for the second-smallest number. Since 5<2 yields false, a recursive call to return quick_select(array_list, left, split-1, k) is made so that the other half of the list is searched.

If the split index was less than k, then we would make a call to quick_select, like this:

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset