Memang, selain indikator kinerja, ada karakteristik lain yang kerap tak kalah pentingnya. Salah satunya adalah kealamian . Apa itu? Pengurutan disebut natural jika lebih cepat ketika array hampir diurutkan. Array apa yang dapat dianggap "hampir diurutkan"? Berikut adalah dua array dari elemen yang sama:
{1,2,9,3,4,5,7,6,8,10} dan {9,1,6,3,10,5,4,2, 8.7}
Bahkan secara kasat mata Anda dapat melihat bahwa larik pertama lebih teratur (hanya 9 dan 7 yang "tidak pada tempatnya"). Sedangkan pada larik kedua jumlahnya tercampur secara acak. Apa ukuran keteraturan? Jawabannya diketahui - jumlah inversi. Sepasang elemen A [i] dan A [j] untuk j> i merupakan invers jika A [j] <A [i]. (Dalam catatan ini, tujuan pengurutan selalu dalam urutan naik.)
Sekarang kita dapat memberikan definisi yang tepat: pengurutan disebut natural jika kecepatannya menurun ketika jumlah inversi dalam larik asli berkurang.
Kealamian adalah "buah langka" di dunia penyortiran - baik jenis QuickSort maupun Shell tidak memiliki sifat ini, sayangnya. Tapi ada satu algoritma yang, bisa dikatakan, sepenuhnya alami - itu adalah semacam penyisipan. Meskipun algoritma ini dikenal oleh setiap orang yang berbudaya, izinkan saya mengulangi esensinya secara singkat.
Larik yang akan diurutkan dipindai sekali dari awal hingga akhir. Segera setelah ditemukan bahwa elemen ke-i dan (i-1) membentuk sebuah inversi, elemen ke-i "dilempar" ke belakang (yang dicapai dengan menggeser segmen awal array yang diperlukan ke kanan dengan satu posisi). Dari uraian ini jelas bahwa jika ada sedikit inversi dalam larik, algoritme akan "terbang" melalui larik dengan sangat cepat. Jika tidak ada inversi sama sekali, maka algoritma akan selesai dalam waktu O (n). Tetapi QuickSort dalam hal ini akan memakan waktu lama dan membosankan untuk memilih elemen pemisah, membagi larik yang sudah dipesan menjadi beberapa segmen, dll. Tetapi jika ada banyak inversi, situasinya tentu saja akan sebaliknya: kinerja sortir penyisipan akan turun ke O (n ^ 2), dan QuickSort akan menjadi juaranya - O (n * log (n)).
Situasi ini menimbulkan pertanyaan wajar dari sudut pandang saya: berapa banyak inversi yang melebihi kealamian dan jenis penyisipan bekerja lebih cepat daripada QuickSort?
Untuk menjawab pertanyaan ini, saya menjalankan serangkaian eksperimen komputasi. Esensi mereka adalah sebagai berikut. Array bilangan bulat mulai dari 3000 hingga 30.000 elemen diambil, sejumlah inversi dimasukkan ke dalamnya, kemudian array diurutkan berdasarkan sisipan dan sortir cepat. Waktu penyortiran diukur (dalam sistem tick). Untuk rata-rata, setiap sortir diulang 10 kali. Hasilnya adalah sebagai berikut:
Gambar menunjukkan ketergantungan waktu penyortiran pada jumlah inversi yang dimasukkan. Seri raspberry, tentu saja, QuickSort, dan seri biru adalah jenis penyisipan. Untuk ukuran array 30 ribu elemen, hingga sekitar 400 ribu inversi "kemenangan alami". Untuk larik yang kurang berurutan, QuickSort sudah lebih bermanfaat.
Dan gambar selanjutnya menunjukkan ketergantungan empiris dari jumlah kritis inversi pada ukuran array.
Sangat mudah untuk melihat bahwa untuk larik berukuran n, jumlah inversinya yang kritis adalah sekitar 10 * n. Dengan lebih banyak inversi, QuickSort bermanfaat. Perlu dicatat bahwa jumlah maksimum inversi untuk larik dengan panjang n adalah n * (n-1) / 2. Nilai 10 * n adalah bagian yang sangat tidak signifikan darinya. Itu tidak mengherankan.
Mengenai apa yang telah dikatakan, tetap menambahkan bahwa hasil eksperimen tersebut bergantung pada banyak faktor (bahasa pemrograman, jenis data yang diurutkan, dll.) Sejujurnya, saya terlalu malas untuk menyelidiki masalah ini secara lebih detail. Eksperimen saya dilakukan di Microsoft Excel di lingkungan VBA:
Uji kode sumber
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
Terima kasih atas perhatiannya!
PS
Dan terima kasih kepada semua orang yang mencatat kesalahan saya! (Ejaan Timsort salah - di edisi pertama ada "TeamSort" dan "i" yang hilang di QuickSort). Dan ya! - (terutama untuk perfeksionis) QuickSort dapat "menurunkan" kinerja kuadrat. Tetapi dalam posting ini saya mempertimbangkan bukan yang terburuk, tetapi kasus penggunaan terbaik untuk QuickSort.