Блог

Я работаю над реализацией быстрой сортировки в Python с рекурсией без создания новых переменных для хранения левой и правой частей разделенного массива.

Я получаю неправильные значения при выполнении рекурсивного шага. Это то, что я сделал до сих пор:

 def swap(a,i,j):
    tmp = a[i]
    a[i] = a[j]
    a[j] = tmp
    
def pivot(a, lo, hi):
    mid = (lo   hi) // 2
    # sort lo, mid, hi:
    if a[mid] < a[lo]:
        swap(a, lo, mid)
    if a[hi] < a[lo]:
        swap(a, lo, hi)
    if a[hi] < a[mid]:
        swap(a, mid, hi)

def partition(a, lo, hi):
    # place the pivot out of the way, in position hi -1 
    mid = (lo   hi)//2
    swap(a, mid, hi - 1)
    
    i = lo
    j = hi - 1
    pivot = a[j]
    
    while True:
        while True:
            i  = 1
            if a[i] >= pivot: break
           
        while True:
            j -= 1
            if a[j] <= pivot: break
            
            
        if i >= j: break
        swap(a, i, j)
    swap(a, i, hi - 1)
    return i
  

Предполагая, что приведенный выше код шаблона «правильный». Мне пришлось реализовать быструю сортировку, используя вышеупомянутые реализации pivot и partition. Это то, что я сделал:

 def quicksort(a):
    _sort(a, 0, len(a)-1)
    
def _sort(a, left, right):
    if(left <  right):
        pivot(a, left, right)
        piv = partition(a, left, right)
        _sort(a, left, piv-1)
        _sort(a, piv 1, right)
  

Когда я вызываю быструю сортировку со списком:

 x = [98, 33, 11, 5, 1, 10, 11, 12, 14, 33, 55, 66, 556, 88]
quicksort(x)
print(x)
>>> [1, 5, 10, 11, 11, 12, 14, 33, 33, 55, 66, 88, 556, 98]
  

Вы можете видеть, что 98 неуместен. Если я запускаю так:

 x = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6, 55, 66, 888, 33, 556, 10]
quicksort(x)
print(x)
>>> [2, 3, 5, 6, 7, 9, 10, 10, 11, 12, 14, 33, 55, 66, 556, 888]
  

Итак, для приведенного выше случая это правильно. Но в других небольших случаях это не удается:

 x = [98, 33, 11, 556, 88]
quicksort(x)
print(x)
>>> [33, 11, 88, 556, 98]
  

Кто-нибудь может помочь мне найти ошибку? Спасибо 🙂

Я вижу две ошибки, первая из которых в вашей partition() функции.

Попробуйте заменить swap(a, i, hi - 1) на swap(a, i, hi)

Второй находится в _sort() . Последний вызов должен быть _sort(a, piv, right)

Правильный код:

 def partition(a, lo, hi):
    # place the pivot out of the way, in position hi -1 
    mid = (lo   hi)//2
    swap(a, mid, hi - 1)
    
    i = lo
    j = hi - 1
    pivot = a[j]
    
    while True:
        while True:
            i  = 1
            if a[i] >= pivot: break
           
        while True:
            j -= 1
            if a[j] <= pivot: break
            
        if i >= j: break
        swap(a, i, j)
    swap(a, i, hi)
    return i
  

и

 def _sort(a, left, right):
    if(left <  right):
        pivot(a, left, right)
        piv = partition(a, left, right)
        _sort(a, left, piv-1)
        _sort(a, piv, right)
  

Тест:

 x = [98, 33, 11, 556, 88]
quicksort(x)
print(x)
[11, 33, 88, 98, 556]
  

Еще несколько тестов:

 import random
for n in range(10):
    x = [random.randint(1,999) for i in range(random.randint(4,10))]
    quicksort(x)
    print(x)

[104, 226, 721, 769]
[131, 453, 590, 730, 752, 834]
[132, 156, 191, 277, 541, 599, 666, 909, 919]
[114, 210, 280, 919, 968, 978]
[127, 212, 381, 458, 585, 594, 685, 809, 935]
[73, 90, 189, 591, 599, 686, 806, 829, 831, 906]
[89, 115, 208, 601, 774, 813, 842, 981]
[159, 177, 203, 231, 621, 759, 950]
[347, 348, 417, 476, 850, 902]
[8, 50, 51, 483, 499, 696, 842]