Python-powered Quickselect: Speed and Precision in One.

Finding the k-th smallest element use case.


Quickselect is a selection algorithm to find the k-th smallest (sometimes largest) element in an unordered list. It can be considered as subtype of quicksort sorting algorithm. In computer science Quickselect sometimes cakked Hoare's selection algorithm by the name of it's creator. It is considered very efficient in practice and has good average-case performance, but is not very good worst-case cases.

Quickselect algorithm.
Python Quickselect algorithm meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-10-14 by Andrey BRATUS, Senior Data Analyst.




    The difference with quicksort is that after finding pivot instead of recurring for both sides, it recurs only for one side containing the k-th smallest element. The algorithm checks if index of the partitioned element is more than k it recurs for the left part, if index is less than k, then process recurs for the right part. When the index is equals k, then the k-th smallest element is found.


  1. Quickselect algorithm Python code:



  2. 
    def partition(arr, l, r):
         
        x = arr[r]
        i = l
        for j in range(l, r):
             
            if arr[j] <= x:
                arr[i], arr[j] = arr[j], arr[i]
                i += 1
                 
        arr[i], arr[r] = arr[r], arr[i]
        return i
     
    
    # ASSUMPTION: all elements in array are distinct
    def kthSmallest(arr, l, r, k):
     
        # if k is smaller than number of elements in array
        if (k > 0 and k <= r - l + 1):
     
            # Partition the array around last element and get position of pivot element in sorted array
            index = partition(arr, l, r)
     
            # if position is same as k
            if (index - l == k - 1):
                return arr[index]
     
            # If position is more recur for left subarray
            if (index - l > k - 1):
                return kthSmallest(arr, l, index - 1, k)
     
            # Else recur for right subarray
            return kthSmallest(arr, index + 1, r,
                                k - index + l - 1)
        print("Index out of bound")
     
    # Driver Code
    arr = [ 1, 7, 5, 4, 6, 11, 26 ]
    n = len(arr)
    k = 3
    print("K-th smallest element is ", end = "")
    print(kthSmallest(arr, 0, n - 1, k))
    
  3. Quickselect algorithm code output:


  4. OUT: K-th smallest element is 5





See also related topics: