[ALGO] Complexite des algorithmes (7)

IntroSort

On fait un QuickSort en le limitant a appels recursifs. S’il y en a plus, s’il y en a plus on fait le tri avec HeapSort

IntroSort():
    dmax <- c|log_2n|
    IntroSortRec(A, 0, n, dmax)
    
IntroSortRec(A, b, e, d):
    if e - b > 1:
        if d == 0
            HeapSort(A, b, e)
        else
            m <- Partition(A, b, e)
            d--
            IntroSortRec(A, b, m, d)
            IntroSortRec(A, m, e, d)

Ou c = 2







hierarchy



a < b ?

a < b ?



b < c ?

b < c ?



a < b ?->b < c ?





b < c ? 

b < c ? 



a < b ?->b < c ? 





a < b > c

a < b > c



b < c ?->a < b > c





a < c ?

a < c ?



b < c ?->a < c ?





a < c ? 

a < c ? 



b < c ? ->a < c ? 





c < b < a

c < b < a



b < c ? ->c < b < a





a < c < b

a < c < b



a < c ?->a < c < b





c < a < b

c < a < b



a < c ?->c < a < b





b < a < c

b < a < c



a < c ? ->b < a < c





b < c < a

b < c < a



a < c ? ->b < c < a





Tous les ordres sur les n valeurs Il y a au moins feuilles.

CountingSort

N’a de sens que si il y a plusieurs repetitions de memes nombres

A 1 2 1 0 2 1 1 0 2
C Histogramme
C 2 4 3
C’ 2 6 9
B Resultat
C 2 6 8
B x x x x x x x x 2
C 1 6 8
B x 0 x x x x x x 2
C 1 5 8
B x 0 x x x 1 x x 2
C 1 4 8
B x 0 x x 1 1 x x 2
C 1 4 7
B x 0 x x 1 1 x 2 2
C 0 4 7
B 0 0 x x 1 1 x 2 2
C 0 3 7
B 0 0 x 1 1 1 x 2 2
C 0 3 6
B 0 0 x 1 1 1 2 2 2
C 0 2 6
B 0 0 1 1 1 1 2 2 2
// On suppose ∀i∈[0,n[,0≤A[i]<k
CountingSort(A, n, k):
    for i <- 0 to k - 1:
        C[i] <- 0
    for i <- 0 to n - 1:
        C[A[i]] <- C[A[i]] + 1
    for i <- 1 to k - 1:
        C[i] <- C[i] + C[i - 1]
    for i <- n - 1 down to 0:
        C[A[i]] <- C[A[i]] - 1
        B[C[A[i]]] <- A[i]
    return B
Ligne de code Cout
for i <- 0 to k - 1:
C[i] <- 0
for i <- 0 to n - 1:
C[A[i]] <- C[A[i]] + 1
for i <- 1 to k - 1:
C[i] <- C[i] + C[i - 1]
for i <- n - 1 down to 0:
C[A[i]] <- C[A[i]] - 1
B[C[A[i]]] <- A[i]
return B
Total

RadixSort

Pour trier n valeurs On a fait

RadixSort MSD (Most Significant Digit)

01110
00111
10101
11111
00000
00101
10100
01110
00111
00101
00000
11111
10101
10100

Tri en place si

Avec S(n) complexite spaciale

Resume de tous les tris

Tri Complexite temporelle cas general Complexite spatiale en place stable Utilite
best | any | worst any
SelectionSort 1 0
InsertionSort | | 1 1 petits tableaux
MergeSort 0 1 seul stable
HeapSort 1 0
QuickSort | | 1 0
IntroSort 1 0
CountingSort bien si le = 0 1 nb fixe de valeurs a trier
RadixSort \Theta(n)$ 0 1 si Counting