#### Quick Select

j
p
W
w
9
f
L
C
and 7 more contributors
```"""
A Python implementation of the quick select algorithm, which is efficient for
calculating the value that would appear in the index of a list if it would be
sorted, even if it is not already sorted
https://en.wikipedia.org/wiki/Quickselect
"""
import random

def _partition(data: list, pivot) -> tuple:
"""
Three way partition the data into smaller, equal and greater lists,
in relationship to the pivot
:param data: The data to be sorted (a list)
:param pivot: The value to partition the data on
:return: Three list: smaller, equal and greater
"""
less, equal, greater = [], [], []
for element in data:
if element < pivot:
less.append(element)
elif element > pivot:
greater.append(element)
else:
equal.append(element)
return less, equal, greater

def quick_select(items: list, index: int):
"""
>>> quick_select([2, 4, 5, 7, 899, 54, 32], 5)
54
>>> quick_select([2, 4, 5, 7, 899, 54, 32], 1)
4
>>> quick_select([5, 4, 3, 2], 2)
4
>>> quick_select([3, 5, 7, 10, 2, 12], 3)
7
"""
# index = len(items) // 2 when trying to find the median
#   (value of index when items is sorted)

# invalid input
if index >= len(items) or index < 0:
return None

pivot = items[random.randint(0, len(items) - 1)]
count = 0
smaller, equal, larger = _partition(items, pivot)
count = len(equal)
m = len(smaller)

# index is the pivot
if m <= index < m + count:
return pivot
# must be in smaller
elif m > index:
return quick_select(smaller, index)
# must be in larger
else:
return quick_select(larger, index - (m + count))
```

### Problem Statement

Given an array, find the kth largest / smallest element in linear time complexity.

### Approach

• Select a pivot element at random
• Apply partitioning as used in quick sort
• After partitioning, the pivot will be placed in its sorted location ie. All elements smaller than the pivot will be on its left and greater on its right
• If index of sorted pivot is k, then the pivot is our kth element and we return the number
• Else, check if 'k' is greater or smaller and choose a new pivot in that range.
• Repeat till we get the kth element at kth position

### Time Complexity

• `O(n^2)` Worst-Case Performance

• `O(n)` Best-case Performance

• `O(n)` Average Performance

### Founder's Name

• This algorithm was developed by Tony Hoare and is also called `Hoare's Selection Algorithm`.

### Example

``````arr[] = {8,2,11,7,9,1,3}
Indexes: 0 1 2 3 4 5 6

Let's say k = 4. ie. We have to find 4th smallest element.

1. Choosing random pivot as 7
2. Swap 7 with the last element and apply the partitioning algorithm
3. After applying partition, all elements smaller than 7 will be placed to the left and greater in its right.
Thus we can say that 7 is in its sorted position arr[] = {2,3,1,7,8,9,11}
4. As position of '7' is 4th (ie. k). Thus we will simply return 7
``````  