import random def selection(S, k, start=0, end=None): '''find the k-minimum element in S. Position k is always included in interval [start, end], including the extremes''' if end is None: end = len(S)-1 if start == end: return S[start] pivot_pos = partition(S, start, end) if pivot_pos == k: return S[k] if k < pivot_pos: return selection(S, k, start, pivot_pos - 1) else: return selection(S, k, pivot_pos+1, end) def partition(S, start, end): # choose pivot in random position pivot_pos = random.randint(start, end) pivot = S[pivot_pos] # swap pivot and start element S[start], S[pivot_pos] = S[pivot_pos], S[start] i = start+1 j = end # scan list from the start (pivot excluded) towards the end # and from the end towards the start while i= pivot i += 1 while i= pivot: # looks for an element < pivot j -= 1 if i= pivot: # decides whether pivot must go in position i or i-1 i -= 1 S[start], S[i] = S[i], S[start] # put pivot in the middle return i example = [23, 21, 5, 2, 1, 55, 32, 67, 5, 67, 91, 12] print(example) print("k=6, element", selection(example, 6)) print(example) # the sequence is not sorted, but "almost sorted" around the required position