Quicksort реализовать в Python запустить без остановки

Question

Это мои алгоритмы quicksort. Очень простой

x = 0 
def swap(list, a, b): 
    temp = list[a] 
    list[a] = list[b] 
    list[b] = temp 
    return list 
def quicksort2(list, left, right): 
    if right > left: 
     global x 
     x = x + 1 
     print x , list, left, right 
     l = left+1 
     r = right 
     while l <= r : 
      while list[l] < list[left]: 
       l = l + 1 
      while list[r] > list[left]: 
       r = r - 1 
      if l < r: 
       list = swap(list, l, r) 
     list = swap(list, left, r) 
     list = quicksort2(list, left, r-1); 
     return quicksort2(list, r+1, right); 
    return list 

Но когда я бегу мое TestCase

b = list([1, 2, 2, 3, 4, 5, 6, 12, 6, 32]) 
quicksort2(b, 0, len(b)-1) 

результат

1 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 0 9 
2 [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 1 9 

и останавливаться на этом ... Кто-нибудь есть какие-либо причины ...

Answer 1

Вы пытались отследить выполнение программы под отладчиком ...?

Цикл while l <= r работает вечно, потому что после нескольких декрементов r

• left == 1
• l == 2
• r == 2

и

• l не увеличивается, потому что list[2] не менее list[1]
• r не уменьшается больше, потому что list[2] не больше, чем list[1]
• не подкачки не будет сделано, потому что l не менее r
• и цикл будет продолжаться, поскольку l по-прежнему равен r .......

Answer 2

I si немного изменил ваш код. Нашел несколько ошибок, некоторые из которых уже упоминались другими. В остальном я не собираюсь проходить. Однако вам не нужно возвращать измененный список, поскольку списки в python всегда передаются по ссылке.

Это должно работать:

def quicksort2(list, low, high): 
    global x 
    x = x + 1 
    print x , list, low, high 

    l = low 
    r = high 
    mid = list[(r + l)/2] 
    while l <= r: 
     while list[l] < mid: l += 1 
     while list[r] > mid: r -= 1 
     if l <= r: 
     list[l], list[r] = list[r], list[l] #swap(r,l) 
     l += 1 
     r -= 1 

    if r > low: quicksort2(list, low, r); 
    if l < high: quicksort2(list, l, high); 


if __name__ == '__main__': 
    x = 0 
    b = [1, 2, 2, 3, 4, 5, 6, 12, 6, 32] 
    quicksort2(b, 0, len(b)-1) 
    print b