问题描述:

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 = 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[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_array

return sorted_array

array = [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:

- recursive function receives an array and returns a new array that is sorted
- 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.