Почему моя программа Quicksort неправильно сортирует элементы?

Question

Моя программа быстрой сортировки изменяет порядок элементов в списке в правильном направлении, но не полностью сортирует их.

def quick_sort(arr, low, high):
    if (low < high):
        pi = pivot(arr, low, high)
        pivot(arr, low, pi-1)
        pivot(arr, pi+1, high)

def pivot(arr, low, high):
    i = ( low-1 )         
    pivot = arr[high]      

    for j in range(low , high): 

        if   arr[j] <= pivot: 

            i += 1
            arr[i],arr[j] = arr[j],arr[i] 


    arr[i+1], arr[high] = arr[high], arr[i+1] 
    return ( i + 1 ) 
print (numbers)
quick_sort(numbers, 0, len(numbers)-1)
print (numbers)

Я ожидал, что результаты будут отсортированы правильно, а не частично отсортированы.

отл.[-9859, -8554, -9846, -9558, -9153, -9483, -7946, -8255, -9743, -8330, -7632, -7513, -7125, 1756, -5176, -441, -3385, 896, -4748, 3811, 4285, -5883, -4342, 6275, 5753, 585, -2491, -243, -3590, -4377, 5986, -3393, -3727, 2976, -1532, -3924,53, -2461, -5882, -1022, 2881, -3586, -3191, 6153, -4970, -5602, -5944, 5528, -3281, 1515, -680, -1975, -2472, -4371, -2574, -5248, -773, -271, -1967, 5079, 3040, -5871, 4825, 2810, -2301, 1371, 315, 2911, 2669, 2477, -3205, -2350, 2402, 5217, 6205,2593, 4595, -4340, 6654, 7783, 9653, 8331, 8092, 6869, 7556, 9719, 8555, 9430, 8137, 9057, 8124, 7662, 6991, 6928, 7728, 7849, 7955, 7696, 7775]

Answer 1

Я не подробно рассмотрел вашу реализацию pivot (поэтому могут быть дополнительные проблемы), но функция верхнего уровня quick_sort имеет одну очевидную проблему.Вы звоните pivot три раза с него, но вместо этого вам следует звонить только один раз, а рекурсивно вызывать quick_sort два других.

Попробуйте:

def quick_sort(arr, low, high):
    if (low < high):
        pi = pivot(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)

Рекурсия важна, потому что она сортируется на все меньших и меньших интервалах.Ваш текущий код эффективно сортирует элементы в четыре сегмента, но в этих сегментах значения будут в случайном порядке.