**Find the k ^{th} 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.

**Python Implementation**

This file contains 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