Quicksort retourne une mauvaise commande

Question

Je travaille sur une implémentation de quicksort en Python avec récursivité sans créer de nouvelles variables pour contenir les parties gauche et droite du tableau partitionné.

J'obtiens des valeurs erronées lors de l'exécution de l'étape récursive. Voici ce que j'ai fait jusqu'à présent:

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

En supposant que le code de modèle ci-dessus est "correct". J'ai dû implémenter le tri rapide en utilisant les implémentations ci-dessus de pivot et de partition. C'est ce que j'ai fait:

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)

Lorsque j'appelle le tri rapide avec une liste:

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]

Vous pouvez voir que le 98 est égaré. Si je cours comme ça:

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]

Donc, pour le cas ci-dessus, c'est correct. Mais dans d'autres cas plus petits, cela échoue:

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

Quelqu'un peut-il m'aider à trouver l'erreur? Merci :-)

Answer 1

Je vois deux erreurs, la première est dans votre partition()fonction.

Essayez de remplacer swap(a, i, hi - 1)parswap(a, i, hi)

Le second est entré _sort(). Le dernier appel devrait être_sort(a, piv, right)

Le code correct est:

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

et

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)

Tester:

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

Quelques tests supplémentaires:

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]