[ALGO] Complexite des algorithmes (6)

Ecrire T(n) en fonction de T(n-1)





QuickSort en moyenne

Ou T(l) = rec a gauche et T(n-l) = rec a droite.

En moyenne




On divise par (n(n-1)) :

ON pose




Comparaison

QuickSort MergeSort
Best
Any
Worst

Partition de QuickSort

QuickSort(A,b,e)
    if e - b > 1:
        m = Partition(A,b,e)
        QuickSort(A,b,m)
        QuickSort(A,m,e)
 
Partition(A,b,e):
    i <- b - 1; j <- e; p = A[b]
    for ever:
        do <ins>i until A[i] >= p
        do --j until A[j] <= p
        if i < j
            A[i] <-> A[j]
        else
            return i + (b == i)


Recherche du pivot ideal pour Partition

Pivot ideal = Mediane du tableau


Recursion terminale : Le dernier appel recursif n’est suivi d’aucune autre operation avant le return.

int fac2(int n, int acc):
start:
    if (n <= 1)
        return acc;
    acc = n * acc;
    n = n - 1;
    goto start;
int fac2(int n, int acc)
    while (n <= 1) {
        acc *= n;
        n--;
    }
    return acc;

Optimisations de QuickSort

QS(A, b, e):
    while (e - b > 1)
        n <- Partition(A, b, e)
        QS(b, m)
        b <- m

Ne change pas la complexite mais on gagne en memoire dans le cas d’un tableau trie a l’endroit : On passe de recursions a


Optimisation 1 :
Faire l’appel recursif sur le plus petit cote, et faire une boucle sur l’autre cote

QS(A, b, e):
    while e - b > 1:
        m <- Partition(A, b, e)
        if m - b > e - m:    
            QuickSort(A, m, e)
            e <- m
        else
            QuickSort(A, b, m)
            b <- m

On consomme moins de pile !

QuickSort'(A, b, e):
    while e - b > 4:
        m <- Partition(A, b, e)
        if m - b > e - m:    
            QuickSort'(A, m, e)
            e <- m
        else
            QuickSort'(A, b, m)
            b <- m
    InsertionSort(A, b, e)
    
QuickSort(A, n):
    QuickSort'(A, 0, n)
    InsertionSort(A, n)

Andrei Alexandrescu - CPPCOM 2019