I'm new to algorithms and I wrote a Quick Sort algorithm for homework, but there is something not going right. I searched for hours, where ever possible, I couldn't find why it doesn't work !
if len(array) > 1:
pivot = array
index_lower = 1
for index in range(len(array)):
if array[index] < pivot:
array[index_lower], array[index] = array[index], array[index_lower]
index_lower += 1
array[index_lower-1], array = array, array[index_lower-1]
left_array = array[:index_lower]
pivot = array[index_lower:index_lower+1]
right_array = array[index_lower+1:]
sorted_array = left_array + pivot + right_array
array = [78, 45, 2, 111, 49, 44, 98, 777, 345, 6548, 4954654, 123, 1, 3, 5]
x = quick_sort(array)
The output I get on this code is :
[3, 2, 1, 5, 44, 45, 49, 78, 345, 777, 123, 111, 98, 6548, 4954654]
You are mixing two styles of implementing a recursive function:
1) is broken since you are not returning anything when
len(array) <= 1, and you do nothing with the result of
2) is broken since you are only doing the initial sorting on the input
array itself, while the result of
left_array + pivot + right_array is not applied to the original array.
The easiest would probably be to write your function using the first style only, since the second style requires a good knowledge of how python variables are modified in-place and passed around between functions.
You return the sorted array, but never use the return value:
left_array = quick_sort(left_array) right_array = quick_sort(right_array)
The problem is right here:
I see the recursive Call, but you discard the result.
It should be
left_array = quick_sort(left_array) richt_array = quick_sort(right_array)
You also forgot the return for the case that the array length is 1.