DEV Community

itzsrikanth
itzsrikanth

Posted on

Quick Select Algorithm

#dsa #competativeprogramming #leetcode

I would not take full credits for this writing this code by hand, some of it goes to the Leetcode discussion section and "Claude Sonnet 4 Thinking" model. Purpose of this series is to document for my learning and if it proves to be useful for others.

There are two popular parition schemes to find the pivot:

  • hoare
  • lomuto

Lomute partition scheme 

def partition(self, left: int, right: int):

        # choose rightmost element (not the index) as the pivot
        pivot = self.arr[right]

        # boundary pointer - tracks the end of the "≤ pivot" region
        i = left

        # scanner pointer - explores the array from left to right
        for j in range(left, right):
            if self.arr[j] <= pivot:
                self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
                i += 1
        self.arr[i], self.arr[right] = self.arr[right], self.arr[i]
        return i
Enter fullscreen mode Exit fullscreen mode

The idea behind i and j pointer is that the former needs to hold the place for numbers smaller than pivot point to be place. It is moved ahead only when we are going to attempt a swap. The latter would scan the elements looking for a lower value to swap.

Taking the example from geeksforgeeks:

Array: [10, 4, 5, 8, 6, 11, 26]  pivot = 26
       left=0, right=6

Initial: [10, 4, 5, 8, 6, 11, 26]  i=0
         ^i                    ^pivot

j=0: arr[0]=10 ≤ 26? Yes → swap(i=0,j=0), i=1
     [10, 4, 5, 8, 6, 11, 26]  i=1
         ^i

j=1: arr[1]=4 ≤ 26? Yes → swap(i=1,j=1), i=2
     [10, 4, 5, 8, 6, 11, 26]  i=2
            ^i

j=2: arr[2]=5 ≤ 26? Yes → swap(i=2,j=2), i=3
     [10, 4, 5, 8, 6, 11, 26]  i=3
               ^i

...continuing this pattern...

Final: [10, 4, 5, 8, 6, 11, 26]  i=6
                           ^i

Place pivot: swap(i=6, right=6) → no change
Return i=6
Enter fullscreen mode Exit fullscreen mode

The goal is to rearrange array so that:

  • all elements ≤ pivot are on the left, and
  • all elements > pivot are on the right, with pivot in its correct final position. 
[ ≤ pivot | > pivot | unprocessed | pivot]
left  i-1   i    j-1  j    right-1  right
Enter fullscreen mode Exit fullscreen mode

__main__ 

class Solution:
    def __init__(self, arr: List[int]):
        self.arr = arr

    def partition(self, left: int, right: int):
        # ...

    def quickselect(self, left: int, right: int, k: int) -> int:
        if left == right:
            return self.arr[left]

        pivot_index = self.partition(left, right)

        if k == pivot_index - left + 1:
            return self.arr[pivot_index]
        elif k < pivot_index - left + 1:
            return self.quickselect(left, pivot_index - 1, k)
        else:
            return self.quickselect(pivot_index + 1, right, k - (pivot_index - left + 1))
Enter fullscreen mode Exit fullscreen mode

References

Top comments (0)