Merge pull request seeditsolution#243 from jayantk137/patch-1

seeditsolution · web-flow · commit 6f8c6fbdf2d9 · 2020-10-02T18:53:30.000+05:30
QuickSelect.py
diff --git a/QuickSelect.py b/QuickSelect.py
@@ -0,0 +1,29 @@
+def quickselect(array,startind,endind,position):  
+    while True:
+        pivotind = startind
+        leftmark = startind + 1
+        rightmark = endind
+        while leftmark <= rightmark:
+            if array[leftmark] > array[pivotind] and array[rightmark] < array[pivotind]:
+                swap(leftmark,rightmark,array)
+            if array[leftmark] <= array[pivotind]:
+                leftmark += 1
+            if array[rightmark] >= array[pivotind]:
+                rightmark -=1
+        swap(pivotind, rightmark,array)
+        if rightmark == position:
+            print(array[rightmark])
+            return
+        elif rightmark < position :
+            startind = rightmark+1
+        else :
+            endind = rightmark - 1
+            
+def swap(one,two,array):
+    array[one],array[two]=array[two],array[one]
+    
+for _ in range(int(input())):
+    n = int(input())
+    arr = list(map(int,input().split()))
+    k = int(input())
+    quickselect(arr,0,n-1,k-1)
