Commit 7ee7dcc
authored
QuickSelect.py
QuickSelect Algorithm
To Search Efficiently kth element in an array without Sorting Whole Array
In Some Cases You've to sort whole array and in the worst case If array already sorted .1 parent 229f8d6 commit 7ee7dcc
1 file changed
Lines changed: 29 additions & 0 deletions
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
@@ -0,0 +1,29 @@ | |||
| 1 | + def quickselect(array,startind,endind,position): | ||
| 2 | + while True: | ||
| 3 | + pivotind = startind | ||
| 4 | + leftmark = startind + 1 | ||
| 5 | + rightmark = endind | ||
| 6 | + while leftmark <= rightmark: | ||
| 7 | + if array[leftmark] > array[pivotind] and array[rightmark] < array[pivotind]: | ||
| 8 | + swap(leftmark,rightmark,array) | ||
| 9 | + if array[leftmark] <= array[pivotind]: | ||
| 10 | + leftmark += 1 | ||
| 11 | + if array[rightmark] >= array[pivotind]: | ||
| 12 | + rightmark -=1 | ||
| 13 | + swap(pivotind, rightmark,array) | ||
| 14 | + if rightmark == position: | ||
| 15 | + print(array[rightmark]) | ||
| 16 | + return | ||
| 17 | + elif rightmark < position : | ||
| 18 | + startind = rightmark+1 | ||
| 19 | + else : | ||
| 20 | + endind = rightmark - 1 | ||
| 21 | + | ||
| 22 | + def swap(one,two,array): | ||
| 23 | + array[one],array[two]=array[two],array[one] | ||
| 24 | + | ||
| 25 | + for _ in range(int(input())): | ||
| 26 | + n = int(input()) | ||
| 27 | + arr = list(map(int,input().split())) | ||
| 28 | + k = int(input()) | ||
| 29 | + quickselect(arr,0,n-1,k-1) | ||
0 commit comments