Efficiency and correctness of my randomized selection algorithm

Question

Instead of picking a random pivot I'm shuffling the array beforehand. Does it count as randomization and is it efficient to shuffle or pick a random pivot and is my implementation pythonic?

Problem

Algorithm

from random import shuffle
def _partition(arr, lo, hi, pivot):
 p = arr[pivot]
 arr[hi - 1], arr[pivot] = arr[pivot], arr[hi - 1]
 i = lo - 1
 for j in xrange(lo, hi):
 if arr[j] <= p:
 i += 1
 arr[i], arr[j] = arr[j], arr[i]
 return i
def select(arr, lo, hi, spos):
 assert lo <= spos < hi
 shuffle(arr) # here's your randomization.
 while True:
 pos = _partition(arr, lo, hi, lo)
 if pos == spos:
 return arr[pos]
 elif pos < spos:
 lo = pos + 1
 else:
 hi = pos

• Attilio: Could you please describe shortly, what the algorithm is supposed to do, or provide a link to a description (e.g. Wikipedia)?
• eightnoteight: this is the basic problem en.wikipedia.org/wiki/Selection_algorithm and this is the algorithm that i'm implementing.. en.wikipedia.org/wiki/Quickselect and sorry for not including them before

Answer 1

You should learn about how to benchmark your code, from my benchmark, shuffling makes the algorithm slower:

from random import shuffle,randint
import time
def _partition(arr, lo, hi, pivot):
 p = arr[pivot]
 arr[hi - 1], arr[pivot] = arr[pivot], arr[hi - 1]
 i = lo - 1
 for j in xrange(lo, hi):
 if arr[j] <= p:
 i += 1
 arr[i], arr[j] = arr[j], arr[i]
 return i
def select(arr, lo, hi, spos,shuffling=None):
 assert lo <= spos < hi
 if shuffling: shuffle(arr) # here's your randomization.
 while True:
 pos = _partition(arr, lo, hi, lo)
 if pos == spos:
 return arr[pos]
 elif pos < spos:
 lo = pos + 1
 else:
 hi = pos
def random_list(length):
 return [randint(1,100) for _ in range(length)]
start = time.time()
results = []
for _ in range(10000):
 results.append(select(random_list(10),1,5,1,shuffling=True))
print("With shuffling: ",time.time()-start)
start = time.time()
results = []
for _ in range(10000):
 results.append(select(random_list(10),1,5,1,shuffling=False))
print("WithOUT shuffling: ",time.time()-start)

• eightnoteight: sorry for my late comment but my intentions are to implement a randomized selection algorithm not the deterministic one. and this is clearly opposite of it.