Find the kth smallest element in an array without sorting.
That’s basically what this algorithm does. It piggybacks on the partition subroutine from the Quick Sort. If you don’t know what that is, you can check out more about the Quick Sort algorithm here and here, and understand the usefulness of partitioning an unsorted array around a pivot.
smallest value
Python Implementation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from random import randrange | |
| def partition(x, pivot_index = 0): | |
| i = 0 | |
| if pivot_index !=0: x[0],x[pivot_index] = x[pivot_index],x[0] | |
| for j in range(len(x)-1): | |
| if x[j+1] < x[0]: | |
| x[j+1],x[i+1] = x[i+1],x[j+1] | |
| i += 1 | |
| x[0],x[i] = x[i],x[0] | |
| return x,i | |
| def RSelect(x,k): | |
| if len(x) == 1: | |
| return x[0] | |
| else: | |
| xpart = partition(x,randrange(len(x))) | |
| x = xpart[0] # partitioned array | |
| j = xpart[1] # pivot index | |
| if j == k: | |
| return x[j] | |
| elif j > k: | |
| return RSelect(x[:j],k) | |
| else: | |
| k = k – j – 1 | |
| return RSelect(x[(j+1):], k) | |
| x = [3,1,8,4,7,9] | |
| for i in range(len(x)): | |
| print RSelect(x,i), |
Related Posts
Quick Sort Python Code
Computing Work Done (Total Pivot Comparisons) by Quick Sort
Anirudh Jayaraman 