実際、パフォーマンスインジケータに加えて、他の特性があり、多くの場合、同様に重要です。それらの1つは自然です。それは何ですか？配列がほぼソートされているときに高速である場合、ソートは自然と呼ばれます。そして、どの配列が「ほぼソートされている」と見なすことができますか？同じ要素の2つの配列は次のとおりです：
{1,2,9,3,4,5,7,6,8,10}と{9,1,6,3,10,5,4,2、 8.7}
目で見ても、最初の配列がより順序付けられていることがわかります（9と7だけが「ずれている」）。一方、2番目の配列では、数値はランダムに混合されます。秩序の尺度は何ですか？答えはわかっています-反転の数。 A [j] <A [i]の場合、j> iの要素A [i]とA [j]のペアは逆数を構成します。 （このメモでは、並べ替えの目的は常に昇順です。）
これで、正確な定義を与えることができます。元の配列の反転数が減少したときに速度が低下した場合、ソートは自然と呼ばれます。
自然さは、ソートの世界ではかなり「珍しい果物」です。残念ながら、QuickSortもShellソートもこの特性を持っていません。しかし、絶対に自然なアルゴリズムが1つあります。それは、挿入ソートです。このアルゴリズムはすべての文化人に知られていますが、その本質を簡単に繰り返します。
ソートされる配列は、最初から最後まで1回スキャンされます。 i番目と（i-1）の要素が反転を形成することがわかるとすぐに、i番目の要素は「スローバック」されます（これは、配列の先頭の必要なセグメントを1つ右にシフトすることによって実現されます）。この説明から、配列に反転がほとんどない場合、アルゴリズムが配列を非常に高速に「飛行」することは明らかです。反転がまったくない場合、アルゴリズムはO（n）時間で完了します。ただし、この場合のQuickSortは、分離要素の選択、既に順序付けられた配列のセグメントへの分割などに時間がかかり、面倒です。ただし、反転が多い場合は、もちろん逆の状況になります。挿入ソートのパフォーマンスはO（n ^ 2）に低下し、QuickSortがチャンピオンになります-O（n * log（n））。
この状況は、私の観点から自然な疑問を提起します。何回の反転が自然さを上回り、挿入ソートはQuickSortよりも速く機能しますか？
この質問に答えるために、私は一連の計算実験を実行しました。その本質は次のとおりです。 3000から30,000要素のサイズの整数の配列を取得し、それらに特定の数の反転を入力してから、配列を挿入とクイックソートでソートしました。ソート時間は（システムティックで）測定されました。平均化のために、各ソートを10回繰り返しました。結果は次のとおりです。
写真は、導入された反転の数に対するソート時間の依存性を示しています。ラズベリーシリーズはもちろんQuickSortで、青いシリーズは挿入ソートです。アレイサイズが3万要素の場合、最大約40万回の反転が「自然に勝ちます」。順序の少ないアレイの場合、QuickSortはすでにより有益です。
次の図は、反転の臨界数がアレイのサイズに経験的に依存していることを示しています。
サイズnの配列の場合、反転の臨界数は約10 * nであることが簡単にわかります。反転が多いほど、QuickSortは有益です。長さnの配列の最大反転数はn *（n-1）/ 2であることに注意してください。値10 * nは、それらの非常に重要でない部分です。これは驚くべきことではありません。
とはいえ、そのような実験の結果は多くの要因（プログラミング言語、ソートされるデータの種類など）に依存することを付け加えておきます。正直なところ、私はこれらの問題を詳細に調査するのが面倒でした。私の実験は、VBA環境のMicrosoftExcelで行われました。
ソースコードをテストする
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
ご清聴ありがとうございました！
PS
そして私の間違いに気づいたすべての人に感謝します！（Timsortのスペルが正しくありません。初版では「TeamSort」があり、QuickSortに「i」がありませんでした）。はい！-（特に完璧主義者の場合）QuickSortは2次パフォーマンスに「低下」する可能性があります。しかし、この投稿では、最悪ではなく、QuickSortの最良の使用例を検討しています。