These are the main issues:
Your function does not return the results, so you'll get None
back from the recursive call and then the + [pivot]
operation will raise an error.
Related to the previous point: when the recursive result comes back, it should not be printed. Printing should only happen when the final result is ready, i.e. this is a job for the original caller (in the main code).
The recursive call should not be made in the loop where you populate the two partitions. It should be made after that loop
Not a problem, but the spelling of "greter" is "greater"
Also, you can skip the first else
, as the if
block will end in a return
.
Correction:
def quick_sort(sequence):
length = len(sequence)
if length <= 1:
return sequence
pivot = sequence.pop()
item_greater = []
item_lower = []
for item in sequence:
if item > pivot:
item_greater.append(item)
else:
item_lower.append(item)
return quick_sort(item_lower) + [pivot] + quick_sort(item_greater)
print(quick_sort([91,45,78,124,174,32,75,69,43,15,2,45,19,66]))
Final remarks
It is not nice that this function destroys the input list. If the caller has a reference to that list and inspects it after the call, it will lack one element. This is due to the first pop
that is executed on it:
lst = [91,45,78,124,174,32,75,69,43,15,2,45,19,66]
print(quick_sort(lst))
print(lst) # misses the last element and is not sorted
Quick sort is intended to be an in-place sorting algorithm, so you should not need to create new lists (item_greater
and item_greater
). Instead these partitions should be formed by swapping values in the input list. There should be no []
(new empty list) or +
(list concatenation) in such an implementation.
Correct versions of in-place quick sort algorithms are readily available. There are many variants possible, depending on the pivot selection. Also on this site there are several Q&A on the topic. See for instance: