I am implementing Quick Sort in Python. My code succeeds in sorting the list, but fails to include the duplicate elements. Please help me find the bug.
from random import choice
def quickSort(lst):
if not lst:
return []
else:
pivot = choice(lst)
lesser = quickSort([l for l in lst if l < pivot])
greater = quickSort([l for l in lst if l > pivot])
#print lesser, pivot, greater
return lesser + [pivot] + greater
print quickSort([3, 2, 5, 6, 1, 7, 2, 4,234, 234, 23, 1234, 24, 132])
Output:
[1, 2, 3, 4, 5, 6, 7, 23, 24, 132, 234, 1234]
One of your conditions needs to be <= or >= (but not both).
Otherwise, you wind up eventually picking one of the repeated elements as a pivot, and since the other copies are neither greater than nor less than the pivot, they don't get passed to either of the lesser or greater sorts.
However, since you aren't using unique identifiers for your items, in the example you're using with integers, this will also involve your pivot being included in the set. In order to avoid that, you'd probably need to choose an index for your pivot instead of a value.
For instance:
from random import randint
def quickSort(lst):
if not lst:
return []
else:
pivot = randint(0, len(lst) - 1)
pivot_value = lst[pivot]
lesser = quickSort([l for i,l in enumerate(lst)
if l <= pivot_value and i != pivot])
greater = quickSort([l for l in lst if l > pivot_value])
return lesser + [pivot_value] + greater
Tested:
>>> from random import randint
>>>
>>> def quickSort(lst):
... if not lst:
... return []
... else:
... pivot = randint(0, len(lst) - 1)
... pivot_value = lst[pivot]
... lesser = quickSort([l for i,l in enumerate(lst)
... if l <= pivot_value and i != pivot])
... greater = quickSort([l for l in lst if l > pivot_value])
... return lesser + [pivot_value] + greater
...
>>> print quickSort([3, 2, 5, 6, 1, 7, 2, 4,234, 234, 23, 1234, 24, 132])
[1, 2, 2, 3, 4, 5, 6, 7, 23, 24, 132, 234, 234, 1234]