En effet, en plus de l'indicateur de performance, il existe d'autres caractéristiques, souvent non moins importantes. L'un d'eux est le naturel . Ce que c'est? Le tri est dit naturel s'il est plus rapide lorsque le tableau est presque trié. Quel tableau peut être considéré comme "presque trié"? Voici deux tableaux des mêmes éléments:
{1,2,9,3,4,5,7,6,8,10} et {9,1,6,3,10,5,4,2, 8.7}
Même à l'œil nu, vous pouvez voir que le premier tableau est plus ordonné (seuls 9 et 7 sont "hors de propos"). Alors que dans le deuxième tableau, les nombres sont mélangés de manière aléatoire. Quelle est la mesure de l'ordre? La réponse est connue - le nombre d'inversions. Un couple d'éléments A [i] et A [j] pour j> i constitue un inverse si A [j] <A [i]. (Dans cette note, le but du tri est toujours l'ordre croissant.)
Nous pouvons maintenant donner une définition précise: le tri est dit naturel si la vitesse de son opération diminue avec une diminution du nombre d'inversions dans le tableau d'origine.
La naturalité est un fruit plutôt «rare» dans le monde du tri - ni QuickSort ni Shell sort n'ont cette propriété, hélas. Mais il y a un algorithme qui, pourrait-on dire, est absolument naturel: c'est le tri par insertion. Bien que cet algorithme soit connu de chaque personne cultivée, permettez-moi de répéter brièvement son essence.
Le tableau à trier est analysé une fois du début à la fin. Dès qu'on constate que le i-ème et (i-1) -éléments forment une inversion, le i-ème élément est "renvoyé" (ce qui est obtenu en décalant le segment requis du début du tableau vers la droite d'une position). Il est clair d'après cette description que s'il y a peu d'inversions dans le tableau, l'algorithme «volera» très rapidement dans le tableau. S'il n'y a pas du tout d'inversions, alors l'algorithme se terminera en un temps O (n). Mais QuickSort dans ce cas sera long et fastidieux pour sélectionner un élément de séparation, diviser un tableau déjà ordonné en segments, etc. Mais s'il y a beaucoup d'inversions, la situation sera bien sûr l'inverse: les performances du tri par insertion chuteront à O (n ^ 2), et QuickSort sera le champion - O (n * log (n)).
Cette situation soulève une question naturelle de mon point de vue: combien d'inversions l'emportent sur le naturel et le tri par insertion fonctionne plus rapidement que QuickSort?
Pour répondre à cette question, j'ai mené une série d'expériences informatiques. Leur essence était la suivante. Des tableaux d'entiers allant de 3000 à 30 000 éléments ont été pris, un certain nombre d'inversions y ont été introduits, puis les tableaux ont été triés par insertions et tri rapide. Le temps de tri a été mesuré (en ticks système). Pour la moyenne, chaque tri a été répété 10 fois. Les résultats sont les suivants:
L'image montre les dépendances du temps de tri sur le nombre d'inversions introduites. La série framboise est, bien sûr, QuickSort, et la série bleue est le tri par insertion. Pour une taille de tableau de 30 000 éléments, jusqu'à environ 400 000 inversions «gains naturels». Pour les baies moins ordonnées, QuickSort est déjà plus avantageux.
Et l'image suivante montre la dépendance empirique du nombre critique d'inversions sur la taille du tableau.
Il est facile de voir que pour un tableau de taille n, le nombre critique d'inversions est d'environ 10 * n. Avec plus d'inversions, QuickSort est bénéfique. Il est à noter que le nombre maximum d'inversions pour un tableau de longueur n est n * (n-1) / 2. La valeur 10 * n en est une partie très insignifiante. Ce qui n’est pas surprenant.
A ce qui a été dit, il reste à ajouter que les résultats de telles expériences dépendent de nombreux facteurs (langage de programmation, type de données à trier, etc.) Pour être honnête, j'étais trop paresseux pour étudier ces questions plus en détail. Mes expériences ont été réalisées sous Microsoft Excel en environnement VBA:
Tester le code source
Private Declare Function GetTickCount Lib "kernel32" () As Long
':::
Sub JSort(A() As Long)
n& = UBound(A, 1)
For i& = 2 To n
If A(i&) < A(i& - 1) Then
j& = i& - 1
x& = A(i&)
Do While (A(j&) > x&)
A(j& + 1) = A(j&)
j& = j& - 1
If j& = 0 Then Exit Do
Loop
A(j& + 1) = x&
End If
Next i&
End Sub
':::
Sub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)
If (e - b) <= 1 Then Exit Sub
i& = b
j& = e
w& = A((i& + j&) / 2)
Do While (i& < j&)
Do While (A(i&) < w&)
i& = i& + 1
Loop
Do While (A(j&) > w&)
j& = j& - 1
Loop
If i& < j& Then
tmp& = A(i&)
A(i&) = A(j&)
A(j&) = tmp&
i& = i& + 1
j& = j& - 1
End If
Loop
If j& > b Then QSort A, b, j&
If i& < e Then QSort A, i&, e
End Sub
'::: ( )
Sub InsInv(A() As Long, k As Long)
n& = UBound(A, 1)
For i& = 1 To k
Do
k1& = n& * Rnd
k2& = n& * Rnd
If (k1& <> k2&) And (k1& >= 1) And (k2& >= 1) Then Exit Do
Loop
tmp& = A(k1&)
A(k1&) = A(k2&)
A(k2&) = tmp&
Next i&
End Sub
':::
Function NumInv(A() As Long) As Long
n& = UBound(A, 1)
For i& = 1 To n& - 1
For j& = i& + 1 To n&
If A(j&) < A(i&) Then NumInv = NumInv + 1
Next j&
Next i&
End Function
':::
Sub Gtest_1()
Dim Eta() As Long
Dim Arr() As Long
Size& = CLng(InputBox("Sz="))
ReDim Eta(1 To Size&) As Long
ReDim Arr(1 To Size&) As Long
Randomize
For i& = 1 To Size&
Eta(i&) = i&
Next i&
q# = Size& * (Size& - 1) / 2
For iii% = 1 To 10
InsInv Eta, CLng(iii%)
ni# = CDbl(NumInv(Eta))
Cells(iii%, 1).Value = ni#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
JSort Arr
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
Next l%
Cells(iii%, 2).Value = S#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
QSort Arr, 1, Size&
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
If Not check(Arr) Then Exit Sub
Next l%
Cells(iii%, 3).Value = S#
DoEvents
Next iii%
MsgBox "OK"
End Sub
Merci pour l'attention!
PS
Et merci à tous ceux qui ont noté mes erreurs! (Orthographe incorrecte de Timsort - dans la première édition, il y avait "TeamSort" et le "i" manquant dans QuickSort). Et oui! - (spécialement pour les perfectionnistes) QuickSort peut "dégrader" en performances quadratiques. Mais dans cet article, je ne considère pas le pire, mais le meilleur cas d'utilisation de QuickSort.