I am studying QuickSort and I practice using Python to complete it. But something happened that I didn't expect. It seems that my QuickSort function only sort once. Why?
array = [3, 1, 4, 5, 6, 7, 2, 0, 8, 9]
def quick_sort(array):
if len(array) <= 1:
# print(array)
# print('')
return
else:
# print(array)
# print('')
pivot = array[0]
i = 1
j = len(array) - 1
while i != j:
while array[j] >= pivot and i < j:
j -= 1
while array[i] <= pivot and i < j:
i += 1
if i < j:
array[i], array[j] = array[j], array[i]
# print(array)
# print('')
if array[0] > array[i]:
array[0], array[i] = array[i], array[0]
# print(array)
# print('')
array_left = array[0:i]
array_right = array[i + 1:]
quick_sort(array_left)
quick_sort(array_right)
def test_quick_sort():
# print(array)
quick_sort(array)
print(array)
test_quick_sort()
The output is [2, 1, 0, 3, 6, 7, 5, 4, 8, 9].
If you cancel all the #,you can see the output of each step which is absolutely correctly.
In python, when you slice a list, a new list is created with the values.
list1 = [1, 2, 3, 4, 5]
list2 = list1[:3] #[1, 2, 3]
list2[0] = 5 #[5, 2, 3]
print(list1, list2) #[1, 2, 3, 4, 5] [5, 2, 3]
Any changes made to the sliced list is not reflected in the original one.
Within your quick_sort function, you sliced the list into left and right portions and called quick_sort on them. This does not affect the order of the original list.
To resolve this, modify your function to instead take in a list together with the start and end index of where to sort.
def quick_sort(array, start, end):
if end - start <= 1:
return
else:
pivot = array[start]
i = start + 1
j = end - 1
while i != j:
while array[j] >= pivot and i < j:
j -= 1
while array[i] <= pivot and i < j:
i += 1
if i < j:
array[i], array[j] = array[j], array[i]
if array[start] > array[i]:
array[start], array[i] = array[i], array[start]
quick_sort(array, start, i)
quick_sort(array, i, end)