# Implementing Quick Select in Python

If I ask you to think about an algorithm to find the kth smallest element in a list of integers, your answer would probably be this: sort the list first and then extract the element at index k-1. This is a simple and effective solution. The time complexity of the above algorithm would be dependent on the sorting algorithm used.

But how can we find the kth smallest element in a list without (completely) sorting the list? The answer is Quick Select. And we can implement it using a simple technique: partitioning, which is also used in quicksort.

## How Does Quick Select Work?

In order to understand how this algorithm works, let’s first look at the pseudocode:

1. Choose a pivot p
2. Partition the array in two sub-arrays w.r.t. p (same partitioning as in quicksort)
3. LEFT –> elements smaller than or equal to p
4. RIGHT–>  elements greater than p
5. If index(pivot) == k:
6.     Return pivot (or index of pivot)
7. If k > index(pivot)
8.     QuickSelect(LEFT)
9. Else:
10.     QuickSelect(RIGHT)

The logic of the algorithm is extremely evident from the above pseudocode: if the index of the pivot after partitioning is the same as ‘k’ then return the pivot; else if k is greater than the index of the pivot then we recur the left side of the partition; else we recur on the right side of the partition.

NOTE: This can be easily converted into an algorithm to find kth largest element by simply changing the condition in line 7 (from ‘>’ to ‘<’)  of the pseudocode.

## Complexity analysis

Considering an input list of size n:

• Best case time complexity: O(n) when the first chosen pivot is also the kth smallest element.
• Worst-case time complexity: O(n^2)

The worst-case occurs when we are extremely unlucky in our pivot choices and our partitions only remove one element from the list at a time. Hence, our list sizes in each of the recursive calls would reduce by 1.

This would result in the following time complexity: O( (n) + (n -1) + (n – 2) +……+3+2+1) which is equal to O(n^2)

NOTE: Although the worst-case complexity is O(n^2), in practice the average time complexity turns out to be O(n).

## Implementation of Quick Select in Python

We already discussed a lot in theory. Now its time to code in Python to implement the Quick Select technique. Below is the given code:

```import math

def quickselect(list_of_numbers, k):
"""
Input: a list of numbers and an integer 'k'.
Output: kth smallest element in the list.
Complexity: best case: O(n)
worst case: O(n^2)
"""
quick_selected= _kthSmallest(list_of_numbers, k, 0, len(list_of_numbers)-1)
if quick_selected!=math.inf:
print('The ' + str(k)+ 'th smallest element of the given list is ' + str(quick_selected))

else:
print('k-th element does not exist')

def _kthSmallest(arr, k, start, end):
"""
private helper function for quickselect
"""
# checking if k is smaller than
# number of elements in the list
if (k > 0 and k <= end - start + 1):

# Partition the array with last
# element as the pivot and get
# position of pivot element in
# sorted array
pivot_index = _partition(arr, start, end)

# if position of the pivot
# after partition is same as k
if (pivot_index - start == k - 1):
return arr[pivot_index]

# if position of the pivot
# is greater than k then
# recursive call _kthSmallest
# on the left partition of the pivot
if (pivot_index - start > k - 1):
return _kthSmallest(arr, k, start, pivot_index - 1)

# Else recursive call for right partition
return _kthSmallest(arr,   k - pivot_index + start - 1, pivot_index + 1, end)
return math.inf

def _partition(arr, l, r):
""" private helper function
Input: a list and two integers:
l: start index of the list to be partitioned
r: end index of the list to be partitioned

Output: index of the pivot after partition (using arr[r] as the pivot)

"""

pivot = arr[r]
i = l
for j in range(l, r):

if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1

arr[i], arr[r] = arr[r], arr[i]
return i

```

Now let’s run an example:

```num_list=[5,2,3,6,2,3,7,6]
quickselect(num_list,4)```

Output:

`The 4th smallest element of the given list is 3`