In der Tat gibt es neben dem Leistungsindikator noch andere Merkmale, die oft gleich wichtig sind. Eine davon ist die Natürlichkeit . Was ist das? Das Sortieren wird als natürlich bezeichnet, wenn es schneller ist, wenn das Array fast sortiert ist. Und welches Array kann als "fast sortiert" angesehen werden? Hier sind zwei Arrays derselben Elemente:
{1,2,9,3,4,5,7,6,8,10} und {9,1,6,3,10,5,4,2, 8.7}
Sogar mit dem Auge kann man sehen, dass das erste Array geordneter ist (nur 9 und 7 sind "fehl am Platz"). Während im zweiten Array die Zahlen zufällig gemischt werden. Was ist das Maß für Ordnung? Die Antwort ist bekannt - die Anzahl der Inversionen. Ein Elementpaar A [i] und A [j] für j> i bildet eine Umkehrung, wenn A [j] <A [i]. (In diesem Hinweis dient die Sortierung immer in aufsteigender Reihenfolge.)
Jetzt können wir eine genaue Definition geben: Die Sortierung wird als natürlich bezeichnet, wenn ihre Geschwindigkeit abnimmt, wenn die Anzahl der Inversionen im ursprünglichen Array abnimmt.
Natürlichkeit ist eine eher „seltene Frucht“ in der Welt des Sortierens - leider haben weder QuickSort noch Shell diese Eigenschaft. Aber es gibt einen Algorithmus, der absolut natürlich ist - es ist eine Einfügungssortierung. Obwohl dieser Algorithmus jeder kultivierten Person bekannt ist, möchte ich kurz seine Essenz wiederholen.
Das zu sortierende Array wird von Anfang bis Ende einmal gescannt. Sobald festgestellt wird, dass das i-te und das (i-1) -Element eine Inversion bilden, wird das i-te Element "zurückgeworfen" (was erreicht wird, indem das erforderliche Segment des Anfangs des Arrays um eine Position nach rechts verschoben wird). Aus dieser Beschreibung geht hervor, dass der Algorithmus bei wenigen Inversionen im Array sehr schnell durch das Array "fliegt". Wenn es überhaupt keine Inversionen gibt, wird der Algorithmus in O (n) Zeit abgeschlossen. In diesem Fall ist es jedoch langwierig und mühsam, ein Trennelement auszuwählen, ein bereits geordnetes Array in Segmente zu unterteilen usw. Wenn es jedoch viele Inversionen gibt, ist die Situation natürlich umgekehrt: Die Leistung der Einfügesortierung sinkt auf O (n ^ 2), und QuickSort wird der Champion - O (n * log (n)).
Diese Situation wirft aus meiner Sicht eine natürliche Frage auf: Wie viele Inversionen überwiegen die Natürlichkeit und die Einfügungssortierung funktioniert schneller als QuickSort?
Um diese Frage zu beantworten, führte ich eine Reihe von Computerexperimenten durch. Ihre Essenz war wie folgt. Wir haben Arrays von ganzen Zahlen mit einer Größe von 3000 bis 30.000 Elementen genommen, eine bestimmte Anzahl von Inversionen wurden in sie eingeführt, dann wurden die Arrays nach Einfügungen und schneller Sortierung sortiert. Die Sortierzeit wurde gemessen (in System-Ticks). Zur Mittelung wurde jede Sortierung zehnmal wiederholt. Die Ergebnisse waren wie folgt:
Das Bild zeigt die Abhängigkeit der Sortierzeit von der Anzahl der eingeführten Inversionen. Die Himbeerserie ist natürlich QuickSort und die blaue Serie ist eine Einfügesortierung. Bei einer Arraygröße von 30.000 Elementen sind bis zu 400.000 Inversionen "natürliche Gewinne". Für weniger geordnete Arrays ist QuickSort bereits vorteilhafter.
Das nächste Bild zeigt die empirische Abhängigkeit der kritischen Anzahl von Inversionen von der Größe des Arrays.
Es ist leicht zu erkennen, dass für ein Array der Größe n die kritische Anzahl von Inversionen ungefähr 10 * n beträgt. Bei mehr Inversionen ist QuickSort von Vorteil. Es ist zu beachten, dass die maximale Anzahl von Inversionen für ein Array der Länge n n * (n-1) / 2 beträgt. Der Wert 10 * n ist ein sehr unbedeutender Teil davon. Was nicht überraschend ist.
Zu dem, was gesagt wurde, muss noch hinzugefügt werden, dass die Ergebnisse solcher Experimente von vielen Faktoren abhängen (Programmiersprache, Art der zu sortierenden Daten usw.). Um ehrlich zu sein, war ich zu faul, um diese Probleme genauer zu untersuchen. Meine Experimente wurden in Microsoft Excel in einer VBA-Umgebung durchgeführt:
Quellcode testen
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
Vielen Dank für Ihre Aufmerksamkeit!
PS
Und danke an alle, die meine Fehler notiert haben! (Falsche Schreibweise von Timsort - in der ersten Ausgabe gab es "TeamSort" und das fehlende "i" in QuickSort). Und ja! - (insbesondere für Perfektionisten) QuickSort kann die quadratische Leistung "verschlechtern". Aber in diesem Beitrag betrachte ich nicht den schlechtesten, sondern den besten Anwendungsfall für QuickSort.