Random pivot selection for quicksort not working

1
votes

I am trying to choose a random index for quicksort, but for some reason, the array is not sorting. In fact, the algorithm returns a different array (ex. input [2,1,4] and [1,1,4] is outputted) sometimes. Any help would be much appreciated. This algorithm works if, instead of choosing a random index, I always choose the first element of the array as the pivot.

def quicksort(array):
  if len(array) < 2:
    return array
  else:
    random_pivot_index = randint(0, len(array) - 1)
    pivot = array[random_pivot_index]
    less = [i for i in array[1:] if i =< pivot]
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)
1
quicksort

1 Answers

0
votes

less = [i for i in array[1:] if i =< pivot]

You're including elements equal to the pivot value in less here.

But here, you also include the pivot value explicitly in the result:

return quicksort(less) + [pivot] + quicksort(greater)

Instead try it with just:

return quicksort(less) + quicksort(greater)

Incidentally, though this does divide-and-conquer in the same way as QuickSort does, it's not really an implementation of that algorithm: Actual QuickSort sorts the elements in place - your version will suffer from the run-time overhead associated with allocating and concatenating the utility arrays.