当前位置: 动力学知识库 > 问答 > 编程问答 >

QuickSort Python Algorithm

问题描述:

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:

  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.

分享给朋友:
您可能感兴趣的文章:
随机阅读: