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 !

``def quick_sort(array):if len(array) > 1:pivot = array[0]index_lower = 1for index in range(len(array)):if array[index] < pivot:array[index_lower], array[index] = array[index], array[index_lower]index_lower += 1array[index_lower-1], array[0] = array[0], array[index_lower-1]left_array = array[:index_lower]pivot = array[index_lower:index_lower+1]right_array = array[index_lower+1:]quick_sort(left_array)quick_sort(right_array)sorted_array = left_array + pivot + right_arrayreturn sorted_arrayarray = [78, 45, 2, 111, 49, 44, 98, 777, 345, 6548, 4954654, 123, 1, 3, 5]x = quick_sort(array)print x``

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. recursive function receives an array and returns a new array that is sorted
2. recursive function receives an array and modifies the same array, and returns nothing.

1) is broken since you are not returning anything when `len(array) <= 1`, and you do nothing with the result of `quicksort(left_array)`.

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:

``````   quick_sort(left_array)
quick_sort(right_array)
``````

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.

Top