DSA 31: Quickselect [Part 2]

1. quickselect: Function

The quickselect (& quicksort) uses the:

• partition algorithm
  • introduced in DSA 30: Quicksort [Part 1] post.
• to rearrange an array to be below and above a pivot

def quickselect(arr, k, l, r):
    if r-l<=0:
        return
    p=quickselect(arr, k, l, r)
    if k<p:
        return quickselect(arr,k,l,p-1)
    elif k>p:
        return quickselect(arr,k,l+1,r)
    else:
        return arr[p]

2. quickselect: Instance Method within SortableArray class

A SortableArray class also previously introduced:

• introduced in DSA 30: Quicksort [Part 1] post.

class SortableArray():
    def __init__(self, arr):
        self.arr = arr
        
    def partition(self, l: int, r: int):
        p=r
        pivot=self.arr[p]
        r-=1
        while True:
            while self.arr[l]<pivot:
                l+=1
            while self.arr[r]>pivot:
                r-=1
            if l>=r: 
                break
            else:
                self.arr[l],self.arr[r]=self.arr[r],self.arr[l]
                l+=1
        self.arr[l],self.arr[p]=self.arr[p],self.arr[l]
        return l

    def quickselect(self, k, l, r):
        if r-l<=0:
            return self.arr[l]
        
        p = self.partition(l, r)
        
        if k<p:
            return self.quickselect(k,l,p-1)
        elif k>p:
            return self.quickselect(k,l+1,r)
        else:
            return self.arr[p]

3. Testing quickselect

Parameter	Values
input_array	052163
sorted_array	012356
indexes	012345
k	index 5 of sorted input array
Output	6

arr = [int(char) for char in "052163"]
sortable_arr = SortableArray(arr)
sortable_arr.quickselect(5,l=0,r=len(sortable_arr.arr)-1)

6