-
Notifications
You must be signed in to change notification settings - Fork 367
Expand file tree
/
Copy pathquick_select.py
More file actions
44 lines (35 loc) · 1.33 KB
/
quick_select.py
File metadata and controls
44 lines (35 loc) · 1.33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
# Path: Python\Searching\quick_select.py
# Python program to kth smallest element using quickSelect Algorithm.
# Time-Complexity: O(N^2), where N is the size of array.
import random
# Function to swap two elements in the list
def swap(arr, a, b):
arr[a], arr[b] = arr[b], arr[a]
# Partition function to rearrange elements around the pivot
def partition(arr, left, right, pivotIndex):
pivotValue = arr[pivotIndex]
swap(arr, pivotIndex, right) # Move pivot to the end
storeIndex = left
for i in range(left, right):
if arr[i] < pivotValue:
swap(arr, i, storeIndex)
storeIndex += 1
swap(arr, storeIndex, right) # Move pivot to its final place
return storeIndex
# Quickselect function
def quickSelect(arr, left, right, k):
if left == right:
return arr[left]
pivotIndex = left + random.randint(0, right - left)
pivotIndex = partition(arr, left, right, pivotIndex)
if k == pivotIndex:
return arr[k]
elif k < pivotIndex:
return quickSelect(arr, left, pivotIndex - 1, k)
else:
return quickSelect(arr, pivotIndex + 1, right, k)
if __name__ == "__main__":
arr = [3, 8, 2, 5, 1, 4, 7, 6]
k = 4 # Find the 4th smallest element
result = quickSelect(arr, 0, len(arr) - 1, k - 1)
print(f"The {k}-th smallest element is: {result}")