Quicksort: Perbedaan antara revisi
Tidak ada ringkasan suntingan Tag: Suntingan perangkat seluler Suntingan peramban seluler |
|||
(24 revisi perantara oleh 11 pengguna tidak ditampilkan) | |||
Baris 1: | Baris 1: | ||
{{Infobox |
{{Infobox |
||
|title = QuickSort |
|title = QuickSort |
||
|image=[[ |
|image=[[Berkas:Sorting quicksort anim.gif|Quicksort merupakan tindakan dalam membuat daftar angka. Garis horisontal merupakan nilai sumbu.]] |
||
|caption=Visualisasi |
|caption=Visualisasi Algoritme Quicksort. Garis horisontal merupakan nilai sumbu. |
||
|headerstyle = background:#ccf; |
|headerstyle = background:#ccf; |
||
|labelstyle = background:#ddf; |
|labelstyle = background:#ddf; |
||
Baris 9: | Baris 9: | ||
|data1 = O(''n''<sup>2</sup>) |
|data1 = O(''n''<sup>2</sup>) |
||
|label2 = Kelas |
|label2 = Kelas |
||
|data2 = |
|data2 = Algoritme Sorting |
||
|label5 = Waktu |
|label5 = Waktu |
||
|data5 = O(''n''<sup>2</sup>) |
|data5 = O(''n''<sup>2</sup>) |
||
Baris 22: | Baris 22: | ||
}} |
}} |
||
'''Quicksort''' merupakan Algoritma |
'''Quicksort''' merupakan [[Algoritma|Algoritme]] pengurutan yang dikembangkan oleh [[Tony Hoare]]. performa rata-rata pengurutan O(''n'' log ''n'') untuk mengurutkan ''n'' item. Algoritme ini juga dikenal sebagai '''Partition-Exchange Sort''' atau disebut sebagai '''Sorting Pergantian Pembagi'''. Pada kasus terburuknya, algoritme ini membuat perbandingan O(''n''<sup>2</sup>), walaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya daripada algoritme [[urut gabung]] dan heapshort.<ref>S. S. Skiena, The Algorithm Design Manual, Second Edition, Springer, 2008, p. 129</ref> Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log ''n'').<ref>{{cite web |url=http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html |title=Data structures and algorithm: Quicksort |publisher=Auckland University |access-date=2012-11-17 |archive-date=2013-12-05 |archive-url=https://web.archive.org/web/20131205080625/http://www.cs.auckland.ac.nz/~jmor159/PLDS210/qsort1a.html |dead-url=yes }}</ref> |
||
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan |
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritme sorting yang stabil. |
||
== |
== Algoritme == |
||
Quicksort merupakan '' |
Quicksort merupakan ''Algoritme Pembagi''. Pertama quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil: element kecil dan element besar. Quicksort kemudian dapat menyortir sub list itu secara rekursif. |
||
Langkah-Langkah pengerjaannya ialah: |
Langkah-Langkah pengerjaannya ialah: |
||
Baris 36: | Baris 36: | ||
Kasus dasar dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di sorting. |
Kasus dasar dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di sorting. |
||
===Versi Sederhana=== |
=== Versi Sederhana === |
||
Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut: |
Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut: |
||
Baris 50: | Baris 50: | ||
else append 'x' to 'greater' |
else append 'x' to 'greater' |
||
return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls |
return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls |
||
</syntaxhighlight |
</syntaxhighlight> |
||
[[ |
[[Berkas:Quicksort-diagram.svg|ka|200px|jmpl|Contoh keseluruhan dari quicksort pada kumpulan acak dari angka. Element yang gelap merupakan pivot. Pivot selalu dipilih sebagai element terakhir pada partisi. Bagaimanapun, selalu memilih elemen terakhir pada partisi sebagai pivot sehingga hasil pada kasus terburuk (<math>O(n^2)</math>) pada daftar ''yang telah diurutkan'', atau daftar yang serupa. Karena elemen yang sama memotong hingga pada akhir dari prosedur soring pada jumlah yang besar, versi dari algoritme quicksort yang memilih pivot sebagai elemen tengah berjalan lebih cepat daripada algortima yang dijelaskan pada diagram ini pada sejumlah besar angka.]] |
||
Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan membandingkan mereka pada elemen yang lain. Prosedur ini disebuk ''Sorting Pembandingan''. Jenis ini juga merupakan jenis ''sorting yang stabil'' (asumsikan bahwa ''untuk setiap'' method menerima elemen pada urutan aslinya dan pivot yang dipilih merupakan elemen terakhir dari nilai yang sama). |
Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan membandingkan mereka pada elemen yang lain. Prosedur ini disebuk ''Sorting Pembandingan''. Jenis ini juga merupakan jenis ''sorting yang stabil'' (asumsikan bahwa ''untuk setiap'' method menerima elemen pada urutan aslinya dan pivot yang dipilih merupakan elemen terakhir dari nilai yang sama). |
||
Kebenaran dari |
Kebenaran dari algoritme partisi didasari pada dua argumen berikut: |
||
*Pada setiap iterasi, seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot ('''Invarian Loop'''). |
* Pada setiap [[iterasi]], seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot ('''Invarian Loop'''). |
||
Kebenaran dari keseluruhan algortima dapat dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, |
Kebenaran dari keseluruhan algortima dapat dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, algoritme tidak akan mengubah data; untuk jumlah data yang lebih besar, algoritme akan menghasilkan dua bagian, elemen yang kurang dari pivot dan elemen yang lebih besar dari nya, data ini sendiri akan diurutkan secara [[hipotesis]] rekursif. |
||
[[ |
[[Berkas:Quicksort-example.gif|350px|jmpl|kiri|Contoh dari penerapan Quicksort.]] |
||
[[ |
[[Berkas:Partition example.svg|200px|jmpl|kiri|Partisi ditepat bekerja pada daftar yang kecil. Elemen kotak merupakan element pivot, elemen berwarna biru merupakan elemen yang bernilai kecil atau sama, dan elemen yang berwarna merah lebih besar.]] |
||
{| style="clear:both;" |
{| style="clear:both;" |
||
|} |
|} |
||
===Versi In-place=== |
=== Versi In-place === |
||
Kerugian dari versi sederhana diatas membutuhkan ruang simpan O(''n'') yang lebih besar, yang sama buruknya seperti '''merge sort'''. Memory tambahan yang dibutuhkan dapat juga secara radikal berpengaruh pada kecepatan dan performa cache pada implementasi praktiknya. Terdapat juga versi yang lebih rumit yang menggunakan |
Kerugian dari versi sederhana diatas membutuhkan ruang simpan O(''n'') yang lebih besar, yang sama buruknya seperti '''merge sort'''. Memory tambahan yang dibutuhkan dapat juga secara radikal berpengaruh pada kecepatan dan performa cache pada implementasi praktiknya. Terdapat juga versi yang lebih rumit yang menggunakan algoritme partisi '''in-place''' dan dapat mencapai urutan lengkap menggunakan ruang O(log''n'') (tidak dihitung input) pada rata-rata (untuk sekali pemanggilan tumpukan). Kita mulai dengan fungsi partisi: |
||
{| |
{| |
||
Baris 79: | Baris 79: | ||
// number of elements in subarray = right-left+1 |
// number of elements in subarray = right-left+1 |
||
function partition(array, 'left', 'right', 'pivotIndex') |
function partition(array, 'left', 'right', 'pivotIndex') |
||
'pivotValue' |
'pivotValue':= array['pivotIndex'] |
||
swap array['pivotIndex'] and array['right'] // Move pivot to end |
swap array['pivotIndex'] and array['right'] // Move pivot to end |
||
'storeIndex' |
'storeIndex':= 'left' |
||
for 'i' from 'left' to 'right' - 1 // left ≤ i < right |
for 'i' from 'left' to 'right' - 1 // left ≤ i < right |
||
if array['i'] < 'pivotValue' |
if array['i'] < 'pivotValue' |
||
swap array['i'] and array['storeIndex'] |
swap array['i'] and array['storeIndex'] |
||
'storeIndex' |
'storeIndex':= 'storeIndex' + 1 |
||
swap array['storeIndex'] and array['right'] // Move pivot to its final place |
swap array['storeIndex'] and array['right'] // Move pivot to its final place |
||
return 'storeIndex' |
return 'storeIndex' |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
Ini merupakan |
Ini merupakan Algoritme Partisi In-Place. algortima ini memisahkan bagian dari array antara index ''kiri'' dan ''kanan'' secara inklusif, dengan memindahkan seluruh elemen kurang dari <code>array[pivotIndex]</code> sebelum pivot, dan elemen yang sama atau lebih besar darinya. Dalam prosesnya, algoritme ini juga mencari posisi akhir untuk elemen pivot, yang kembali. algoritme ini secara sementara memindahkan elemen pivot pada akhir dari subarray, sehingga tidak mengganggu proses algoritme. Karena hanya menggunakan penukaran, list akhir memiliki elemen yang sama seperti elemen awalnya. Perlu diperhatikan bahwa elemen ditukan beberapa kali sebelum mencapai tempat akhirnya. Dan juga, jika pivot itu ganda pada inputan array, mereka dapat menyebar pada subarray kanan, pada urutan apapun. Cara ini tidak mewakili kesalahan dalam membagi, dimana pengurutan lebih lanjut akan memindahkan dan akhirnya ''merekatkan'' mereka bersama. |
||
Setelah kita memiliki ini, menulis quicksort sendiri ialah mudah: |
Setelah kita memiliki ini, menulis quicksort sendiri ialah mudah: |
||
Baris 107: | Baris 107: | ||
// Get lists of bigger and smaller items and final position of pivot |
// Get lists of bigger and smaller items and final position of pivot |
||
'pivotNewIndex' |
'pivotNewIndex':= partition(array, 'left', 'right', 'pivotIndex') |
||
// Recursively sort elements smaller than the pivot |
// Recursively sort elements smaller than the pivot |
||
Baris 114: | Baris 114: | ||
// Recursively sort elements at least as big as the pivot |
// Recursively sort elements at least as big as the pivot |
||
quicksort(array, 'pivotNewIndex' + 1, 'right') |
quicksort(array, 'pivotNewIndex' + 1, 'right') |
||
</syntaxhighlight |
</syntaxhighlight> |
||
|} |
|} |
||
Setiap pemanggilan rekursif pada fungsi ''quicksort'' ini mengurangi besar dari array yang akan diurutkan paling tidak satu elemen, semenjak setiap elemen pada ''pivotNewIndex'' diletakkan pada posisi akhirnya. Oleh karena itu, |
Setiap pemanggilan rekursif pada fungsi ''quicksort'' ini mengurangi besar dari array yang akan diurutkan paling tidak satu elemen, semenjak setiap elemen pada ''pivotNewIndex'' diletakkan pada posisi akhirnya. Oleh karena itu, algoritme ini menjamin mengakhiri pemanggilan rekursif pada paling banyak ''n'' pemanggilan. Bagaimanapun, versi dari quicksort ini tidak stabil semenjak pengurutan elemen ''partisi'' hanya dilakukan pada satu partisi. |
||
⚫ | |||
===Implementasi Masalah=== |
|||
⚫ | |||
Pada setiap versi awal quicksort, elemen yang paling kiri dari partisi akan sering menjadi pilihan sebagai elemen pivot. Sayangnya, ini menyebabkan perilaku ''worst-case'' pada array yang telah diurut, yang merupakan penggunaan kasus yang sering dipakai. Masalah ini dengan mudah diselesaikan dengan memilih salah satu dari index acak untuk pivot, memilih indek tengah dari partisi atau (secara khusus untuk partisi panjang) memilih [[median]] dari elemen awal, tengah, dan akhir dari partisi untuk pivot (sebagaimana direkomendari oleh '''Robert Sedgewick'''.<ref name='sedgewickBook'>[[Robert Sedgewick (computer scientist)|R. Sedgewick]], Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd Edition, Addison-Wesley</ref><ref name='sedgewickQsortPaper'>[[Robert Sedgewick (computer scientist)|R. Sedgewick]], Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978.</ref> |
Pada setiap versi awal quicksort, elemen yang paling kiri dari partisi akan sering menjadi pilihan sebagai elemen pivot. Sayangnya, ini menyebabkan perilaku ''worst-case'' pada array yang telah diurut, yang merupakan penggunaan kasus yang sering dipakai. Masalah ini dengan mudah diselesaikan dengan memilih salah satu dari index acak untuk pivot, memilih indek tengah dari partisi atau (secara khusus untuk partisi panjang) memilih [[median]] dari elemen awal, tengah, dan akhir dari partisi untuk pivot (sebagaimana direkomendari oleh '''Robert Sedgewick'''.<ref name='sedgewickBook'>[[Robert Sedgewick (computer scientist)|R. Sedgewick]], Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching, 3rd Edition, Addison-Wesley</ref><ref name='sedgewickQsortPaper'>[[Robert Sedgewick (computer scientist)|R. Sedgewick]], Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978.</ref> |
||
Memilih elemen pivot juga rumit dengan dengan kehadiran dari '''Integer Overflow'''. Jika indeks batas dari subarray yang diurutkan cukup besar, ungkapan naif untuk indeks tengah, ''(kiri + kanan)/2'', akan menyebabkan luapan dan memberikan indeks pivot yang salah. Masalah ini dapat terselesaikan dengan menggunakan, sebagai contoh, ''kiri + (kanan-kiri)/2'' pada indeks elemen tengah, pada masalah dari |
Memilih elemen pivot juga rumit dengan dengan kehadiran dari '''Integer Overflow'''. Jika indeks batas dari subarray yang diurutkan cukup besar, ungkapan naif untuk indeks tengah, ''(kiri + kanan)/2'', akan menyebabkan luapan dan memberikan indeks pivot yang salah. Masalah ini dapat terselesaikan dengan menggunakan, sebagai contoh, ''kiri + (kanan-kiri)/2'' pada indeks elemen tengah, pada masalah dari aritmetika kompleks. Masalah yang sama muncul pada beberapa metode yang lain dari pemilihan elemen pivot. |
||
===Optimisasi=== |
=== Optimisasi === |
||
Dua optimisasi penting lainnya, juga disarankan oleh Robert Sedgewick, sebagai pernyataan yang secara umum diakui, dan digunakan secara luas ialah:<ref name= |
Dua optimisasi penting lainnya, juga disarankan oleh Robert Sedgewick, sebagai pernyataan yang secara umum diakui, dan digunakan secara luas ialah:<ref name="glibc_qsort">qsort.c in [[GNU libc]]: [http://www.cs.columbia.edu/~hgs/teaching/isp/hw/qsort.c], [http://repo.or.cz/w/glibc.git/blob/HEAD:/stdlib/qsort.c]</ref><ref>{{Cite web |url=http://home.tiscalinet.ch/t_wolf/tw/ada95/sorting/index.html |title=Salinan arsip |access-date=2012-11-17 |archive-date=2007-09-27 |archive-url=https://web.archive.org/web/20070927203904/http://home.tiscalinet.ch/t_wolf/tw/ada95/sorting/index.html |dead-url=yes }}</ref><ref>http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html{{Pranala mati|date=Mei 2021 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> |
||
* Untuk meyakinkan paling banyak ruang O(log N) digunakan, pertama sekali |
* Untuk meyakinkan paling banyak ruang O(log N) digunakan, pertama sekali algoritme melakukan rekursif pada bagian array yang lebih kecil, dan menggunakan '''pemanggilan ekor''' untuk merekursif yang lainnya. |
||
* Menggunakan '''Insertion Sort''', yang memiliki faktor konstant dan lebih cepat pada array yang lebih kecil, untuk pengerjaan pada array yang lebih kecil (dimana panjang nya kurang dari ambang ''t'' yang ditentukan secara percobaan). Cara ini dapat diimplementasikan dengan meninggalkan beberapa array tak terurut dan menjalankan ''Insertion Sort'' tunggal di akhir, karena tipe sorting ini menangani array yang terurut secara efisien. Insertion Sort yang terpisah pada setiap segmen kecil yang dimana mereka dikenal menambahkan awal dan akhir tambahan pada banyak sorting yang kecil, tetapi juga mencegah pembuangan kunci pembanding pada banyak segment batas, yang kunci ini akan berurut karena Proses kerja quicksort. Cara ini juga meningkatkan penggunaan cahce. |
* Menggunakan '''Insertion Sort''', yang memiliki faktor konstant dan lebih cepat pada array yang lebih kecil, untuk pengerjaan pada array yang lebih kecil (dimana panjang nya kurang dari ambang ''t'' yang ditentukan secara percobaan). Cara ini dapat diimplementasikan dengan meninggalkan beberapa array tak terurut dan menjalankan ''Insertion Sort'' tunggal di akhir, karena tipe sorting ini menangani array yang terurut secara efisien. Insertion Sort yang terpisah pada setiap segmen kecil yang dimana mereka dikenal menambahkan awal dan akhir tambahan pada banyak sorting yang kecil, tetapi juga mencegah pembuangan kunci pembanding pada banyak segment batas, yang kunci ini akan berurut karena Proses kerja quicksort. Cara ini juga meningkatkan penggunaan cahce. |
||
===Paralelisasi=== |
=== Paralelisasi === |
||
Seperti '''Merge Sort''', Quicksort juga dapat diparalelisasikan dikarenakan sifat pembagi-dan-penakluk alaminya. Operasi Partisi In-Place sulit untuk diparalelisasikan |
Seperti '''Merge Sort''', Quicksort juga dapat diparalelisasikan dikarenakan sifat pembagi-dan-penakluk alaminya. Operasi Partisi In-Place sulit untuk diparalelisasikan, tetapi setelah dibagi, bagian list yang berbeda dapat diurutkan secara paralel. Berikut ini merupakan pendekatan langsung: Jika kita memiliki prosesor <math>p</math>, kita dapat membagi list dari element <math>n</math> menjadi sublist <math>p</math> pada rata-rata waktu ''O''(''n''), kemudian mengurutkannya pada rata-rata waktu <math>\textstyle O\left(\frac{n}{p} \log\frac{n}{p}\right)</math>. Abaikan pra pengolahan ''O''(''n'') dan waktu penggabungan merupakan '''Linear Speedup''' atau '''Percepatan Linear'''. Jika pemisahannya tak tampak, abaikan nilai waktu penggabungan ''O''(''n''). Jika Partisi pemisah didasari pada penggantian pivot, sangat rumit untuk memparelisasikan dan secara langsung memiliki nilai waktu ''O''(''n''). Jika diberikan ''O''(log''n'') atau lebih banyak prosesor, hanya sebesar ''O''(''n'') waktu keseluruhan yang digunakan, sedangkan pendekatan dengan ''linear speedup'' akan mencapai waktu ''O''(log ''n'') secara keseluruhan. |
||
Salah satu keuntungan dari quicksort paralel sederhana |
Salah satu keuntungan dari quicksort paralel sederhana daripada algortima sorting paralel yang lain ialah tidak dibutuhkannya sinkronisasi, tetapi kerugiannya ialah tipe sorting ini masih membutuhkan ''O''(''n'') dan hanya ''sublinear speedup'' dari ''O''(log ''n'') yang dapat dicapai. Rangkaian baru dimulai segera setelah sublist tersedia untuk bekerja dan tidak berkomunikasi dengan rangkaian yang lain. Ketika setelah semua rangkaian selesai, Proses sorting juga akan selesai. |
||
Satu lagi algortima sorting paralel yang mutakhir dapat mencapai ikatan waktu yang bahkan lebih baik.<ref>R.Miller, L.Boxer, Algorithms Sequential & Parallel, A Unified Approach, Prentice Hall, NJ, 2006</ref> Sebagai contoh pada tahun 1991 David Powers menjelaskan quicksort paralelisasi (dan '''radix sort''' yang dapat berjalan di waktu ''O''(log ''n'') pada CRWC prosesor ''n'' dengan menjalankan pemisahan secara tak langsung.<ref>David M. W. Powers, [http://citeseer.ist.psu.edu/327487.html Parallelized Quicksort and Radixsort with Optimal Speedup], ''Proceedings of International Conference on Parallel Computing Technologies''. [[Novosibirsk]]. 1991.</ref> |
Satu lagi algortima sorting paralel yang mutakhir dapat mencapai ikatan waktu yang bahkan lebih baik.<ref>R.Miller, L.Boxer, Algorithms Sequential & Parallel, A Unified Approach, Prentice Hall, NJ, 2006</ref> Sebagai contoh pada tahun 1991 David Powers menjelaskan quicksort paralelisasi (dan '''radix sort''' yang dapat berjalan di waktu ''O''(log ''n'') pada CRWC prosesor ''n'' dengan menjalankan pemisahan secara tak langsung.<ref>David M. W. Powers, [http://citeseer.ist.psu.edu/327487.html Parallelized Quicksort and Radixsort with Optimal Speedup], ''Proceedings of International Conference on Parallel Computing Technologies''. [[Novosibirsk]]. 1991.</ref> |
||
⚫ | |||
== Analisa Formal == |
|||
⚫ | |||
Quicksort menggunakan waktu rata-rata ''O''(''n'' log ''n''), ketika inputan merupakan permutasi acak. Mengapa? Sebagai pemulaian, tidak sulit untuk mengetahui bahwa opearasi pemisahan menggunakan ''O''(''n'') waktu. |
Quicksort menggunakan waktu rata-rata ''O''(''n'' log ''n''), ketika inputan merupakan permutasi acak. Mengapa? Sebagai pemulaian, tidak sulit untuk mengetahui bahwa opearasi pemisahan menggunakan ''O''(''n'') waktu. |
||
Pada kasus unbalance sering muncul, setiap kita melakukan partisi kita membagi list menjadi dua buah sublist dari besar 0 dan <math>n-1</math> (sebagai contoh jika seluruh elemen array itu sama). Ini berarti setiap rekursif memanggil proses list dari besar kurang satu dari list sebelumnya. Konsekuensinya, kita dapat membuat penggilan bersarang <math>n-1</math> sebelum kita menccapai list dengan besar 1. Ini berarti bahwa pemanggilan tree ialah rantai linear dari pemanggilan bersarang <math>n-1</math>. Pemanggilan ke-<math>i</math> memanggil <math>O(n-i)</math> pada partisi, dan <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math>, jadi pada kasus ini, Quick sort mengambil waktu sebesar <math>O(n^2)</math>. Itu merupakan worst case dimana input yang diberikan dari perbandingan dilakukan oleh |
Pada kasus unbalance sering muncul, setiap kita melakukan partisi kita membagi list menjadi dua buah sublist dari besar 0 dan <math>n-1</math> (sebagai contoh jika seluruh elemen array itu sama). Ini berarti setiap rekursif memanggil proses list dari besar kurang satu dari list sebelumnya. Konsekuensinya, kita dapat membuat penggilan bersarang <math>n-1</math> sebelum kita menccapai list dengan besar 1. Ini berarti bahwa pemanggilan tree ialah rantai linear dari pemanggilan bersarang <math>n-1</math>. Pemanggilan ke-<math>i</math> memanggil <math>O(n-i)</math> pada partisi, dan <math>\textstyle\sum_{i=0}^n (n-i) = O(n^2)</math>, jadi pada kasus ini, Quick sort mengambil waktu sebesar <math>O(n^2)</math>. Itu merupakan worst case dimana input yang diberikan dari perbandingan dilakukan oleh algoritme sorting, terdapat pula algortima penyesuaian yang secara efektif membuat inputan worst-case pada quicksort menjadi mudah, dengan tanpa teknik pemilihan pivot secara khusus.<ref>M. D. McIlroy. A Killer Adversary for Quicksort. Software Practice and Experience: vol.29, no.4, 341–344. 1999. [http://citeseer.ist.psu.edu/212772.html At Citeseer]</ref> |
||
Pada kasus balance, setiap kali kita melakukan partisi, kita membagi list menjadi dua buah sublist yang bernilai hampir sama. Ini berarti setiap proses pemanggilan rekursif memanggil setengah dari besar list. Konsekuensinya, kita dapat hanya memakai pemanggilan bersarang <math>\log n / \log 2</math> sebelum mencapai list dengan besar 1. Ini berarti bahwa kedalaman pemanggilan tree sebesar <math>\log n / \log 2</math>. Tetapi tidak ada dua pemanggilan pada level pemanggilan tree pada bagian yang sama dari list yang aslinya; oleh karena itu setiap level pemanggilan hanya membutuhkan waktu keseluruhan ''O''(''n'') (setiap pemanggilan memiliki nilai keluar yang konstan, tetapi sejak terdapat hanya ''O''(''n'') pemanggilan pada setiap level, kejadian ini digolongkan pada faktor ''O''(''n'')). Hasilnya ialah algortima hanya menggunakan waktu sebanyak ''O''(''n'' log ''n''). |
Pada kasus balance, setiap kali kita melakukan partisi, kita membagi list menjadi dua buah sublist yang bernilai hampir sama. Ini berarti setiap proses pemanggilan rekursif memanggil setengah dari besar list. Konsekuensinya, kita dapat hanya memakai pemanggilan bersarang <math>\log n / \log 2</math> sebelum mencapai list dengan besar 1. Ini berarti bahwa kedalaman pemanggilan tree sebesar <math>\log n / \log 2</math>. Tetapi tidak ada dua pemanggilan pada level pemanggilan tree pada bagian yang sama dari list yang aslinya; oleh karena itu setiap level pemanggilan hanya membutuhkan waktu keseluruhan ''O''(''n'') (setiap pemanggilan memiliki nilai keluar yang konstan, tetapi sejak terdapat hanya ''O''(''n'') pemanggilan pada setiap level, kejadian ini digolongkan pada faktor ''O''(''n'')). Hasilnya ialah algortima hanya menggunakan waktu sebanyak ''O''(''n'' log ''n''). |
||
Baris 148: | Baris 145: | ||
Sebenarnya, seimbang secara sempurna tidak dibutuhkan; bahkan jika setiap pivot membagi elemen dengan 75% pada satu sisi dan 25% pada sisi yang lainnya (atau pada pecahan tetap), pemanggilan dalam masih dibutuhkan untuk <math>\log n/ \log (4/3)</math>, jadi total running time masih berupa ''O''(''n'' log ''n''). |
Sebenarnya, seimbang secara sempurna tidak dibutuhkan; bahkan jika setiap pivot membagi elemen dengan 75% pada satu sisi dan 25% pada sisi yang lainnya (atau pada pecahan tetap), pemanggilan dalam masih dibutuhkan untuk <math>\log n/ \log (4/3)</math>, jadi total running time masih berupa ''O''(''n'' log ''n''). |
||
Jadi apa yang terjadi pada average case? Jika pivot memiliki peringkat acak di tengah 50 persen, yang |
Jadi apa yang terjadi pada average case? Jika pivot memiliki peringkat acak di tengah 50 persen, yang di antara persentil ke-25 dan persentil ke-75, kemudian memisahkan elemen dengan paling kurang 25% dan paling banyak 75% dari setiap sisi. Jika kita dapat secara konsisten memilih pivot dari pertengahan 50 persen, kita hanya harus memisahkan list paling banyak <math>\log n/ \log (4/3)</math> kali sebelum mencapai list sebesar 1, menghasilkan sebuah algoritme ''O''(''n'' log ''n'') |
||
Ketika inputan merupakan permutasi acak, pivot akan memiliki peringkat acak, dan tidak menjamin berada pada pertengahan 50 persen. Bagaimanapun, ketika kita memulai dari permutasi acak, setiap pemanggilan pivot secara rekursif memiliki peringkat acak dari listnya, dan jika terdapat pada pertengahan list, maka akan menghabiskan waktu setengah. Itu cukup bagus, anggap bahwa kamu membalikkan koin: kepala berarti bahwa peringkat pivot berada pada 50 persen, sedang ekor tidak. Anggap bahwa kamu membalikkan coin berkali-kali sehingga mendapatkan kepala sejumlah ''k'', walaupun akan menghabiskan banyak waktu, secara rata-rata hanya membutuhkan pembalikan 2''k'', kesempatan yang kamu tidak akan dapatkan sebesar <math>k</math> kepala setelah <math>100k</math> lemparan sangat mustahil (dapat diteliti menggunakan ikatan Chernoff). Dengan memakan cara yang sama, rekursif yang dilakukan oleh Quicksort akan mengentikan average case pada pemanggilan dari hanya <math>2(\log n/ \log (4/3))</math>. Tetapi jika pemanggilan rata-rata ialah ''O''(long ''n''), dan setiap level dari proses pemanggilan tree paling banyak <math>n</math> elemen, makan jumlah total dari tugas yang dilakukan pada kasus average case ialah ''O''(''n'' log ''n''). Perlu diperhatikan bahwa |
Ketika inputan merupakan permutasi acak, pivot akan memiliki peringkat acak, dan tidak menjamin berada pada pertengahan 50 persen. Bagaimanapun, ketika kita memulai dari permutasi acak, setiap pemanggilan pivot secara rekursif memiliki peringkat acak dari listnya, dan jika terdapat pada pertengahan list, maka akan menghabiskan waktu setengah. Itu cukup bagus, anggap bahwa kamu membalikkan koin: kepala berarti bahwa peringkat pivot berada pada 50 persen, sedang ekor tidak. Anggap bahwa kamu membalikkan coin berkali-kali sehingga mendapatkan kepala sejumlah ''k'', walaupun akan menghabiskan banyak waktu, secara rata-rata hanya membutuhkan pembalikan 2''k'', kesempatan yang kamu tidak akan dapatkan sebesar <math>k</math> kepala setelah <math>100k</math> lemparan sangat mustahil (dapat diteliti menggunakan ikatan Chernoff). Dengan memakan cara yang sama, rekursif yang dilakukan oleh Quicksort akan mengentikan average case pada pemanggilan dari hanya <math>2(\log n/ \log (4/3))</math>. Tetapi jika pemanggilan rata-rata ialah ''O''(long ''n''), dan setiap level dari proses pemanggilan tree paling banyak <math>n</math> elemen, makan jumlah total dari tugas yang dilakukan pada kasus average case ialah ''O''(''n'' log ''n''). Perlu diperhatikan bahwa algoritme tidak perlu memverifikasi pivot berada ditengah jika diberikan pecahan tetap acak dari berapa kali masukkan, yang cukup untuk kerumitan yang diinginkan. |
||
== |
== Analisis Average-case menggunakan rekursif == |
||
Pendekatan alternatif digunakan untuk mengatur hubungan rekursif untuk faktor ''T''(''n''), waktu yang dibutuhkan untuk mengurutkan list dari besar <math>n</math>. Pada sekian banyak kasus unbalanced, satu Quicksort dapat melibatkan tugas ''O''(''n'') ditambah pemanggilan dua rekursif pada list <math>0</math> dan <math>n-1</math>, jadi hubungan rekurensnya ialah |
Pendekatan alternatif digunakan untuk mengatur hubungan rekursif untuk faktor ''T''(''n''), waktu yang dibutuhkan untuk mengurutkan list dari besar <math>n</math>. Pada sekian banyak kasus unbalanced, satu Quicksort dapat melibatkan tugas ''O''(''n'') ditambah pemanggilan dua rekursif pada list <math>0</math> dan <math>n-1</math>, jadi hubungan rekurensnya ialah |
||
:<math>T(n) = O(n) + T(0) + T(n-1) = O(n) + T(n-1).</math> |
:<math>T(n) = O(n) + T(0) + T(n-1) = O(n) + T(n-1).</math> |
||
Hubungan ini sama dengan |
Hubungan ini sama dengan '''Insertion Sort''' dan '''Selection Sort''', dan dapat menyelesaikan hingga kasus terburuk <math>T(n) = O(n^2)</math>. |
||
Pada kebanyakan kasus balanced, satu pemanggilan quicksort dapat melibatkan ''O''(''n'') tugas dengan ditambah dua pemanggilan rekursif pada list dengan besar <math>n/2</math>, sehingga hubungan rekursifnya ialah: |
Pada kebanyakan kasus balanced, satu pemanggilan quicksort dapat melibatkan ''O''(''n'') tugas dengan ditambah dua pemanggilan rekursif pada list dengan besar <math>n/2</math>, sehingga hubungan rekursifnya ialah: |
||
Baris 164: | Baris 161: | ||
Teorima dasar menjelaskan kepada kita bahwa ''T''(''n'') = ''O''(''n'' log ''n''). |
Teorima dasar menjelaskan kepada kita bahwa ''T''(''n'') = ''O''(''n'' log ''n''). |
||
Garis besar dari pembuktian formal dari ''O''(''n'' log ''n'') dapat dijelaskan sebagai berikut. Asumsikan bahwa tidak ada duplikasi dimana duplikasi itu dapat ditangani dengan pre dan post prosesing linear, atau anggap bahwa kasus lebih mudah dari yang |
Garis besar dari pembuktian formal dari ''O''(''n'' log ''n'') dapat dijelaskan sebagai berikut. Asumsikan bahwa tidak ada duplikasi dimana duplikasi itu dapat ditangani dengan pre dan post prosesing linear, atau anggap bahwa kasus lebih mudah dari yang dianalisiskan. Ketika input merupakan permutasi acak, peringkat dari pivot diseragamkan secara acak dari 0 hingga ''n''=1. Kemudian bagian hasil dari partisi memiliki besaran i dan n-i-1, dan i merupakan seragam acak dari 0 hingga ''n''-1. Jadi, jika dirata-ratakan dari semua pemisahan yang mungkin dan melihat bahwa seluruh perbandingan angka untuk pemisahan ialah <math>n-1</math>, jumlah rata-rata dari pembanding dari keseluruhan permutasi dari urutan input dapat diperkirakan secara akuran dengan menyelesaikan hubungan rekursif ini: |
||
:<math>C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1))</math> |
:<math>C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1))</math> |
||
Dimana rekursifnya |
Dimana rekursifnya |
||
<math>C(n) = 2n \ln n = 1.39n \log_2 n.</math> |
<math>C(n) = 2n \ln n = 1.39n \log_2 n.</math> |
||
Ini berarti bahwa, secara rata-rata, Quicksort melakukan hanya sekitar 39% lebih buruk dari best casenya. Hal ini menjelaskan bahwa average case lebih dekat pada best case |
Ini berarti bahwa, secara rata-rata, Quicksort melakukan hanya sekitar 39% lebih buruk dari best casenya. Hal ini menjelaskan bahwa average case lebih dekat pada best case daripada worst case. Juga perlu dicatat bahwa '''Comparison Sort''' tidak dapat menggunakan kurang dari perbandingan <math>\log_2(n!)</math> secara rata-rata untuk mengurutkan <math>n</math> item. Seandainya <math>n</math> besar, maka akan menghasilkan <math>\log_2(n!) \approx n (\log_2 n - \log_2 e)</math>, sehingga quicksort tidak akan lebih buruk dari comparison sort. Perhitungan waktu yang cepat ini menjadi alasan mengapa secara praktiknya quicksort lebih dominan dibandingkan algortima sorting yang lainnya. |
||
=== |
=== Analisis Quicksort acak === |
||
Menggunakan |
Menggunakan analisis yang sama, seseorang dapat menunjukkan bahwa quicksort yang teracak memiliki sifat yang diinginkan, untuk inputan apapun, membutuhkan ''O''(''n'' log ''n'') kali. Bagaimanapun, terdapat bukti yang kombinatorial, yang lebih elegan dari kedua analisis menggunakan kemungkinan yang berlainan dan analisis menggunakan rekursif. |
||
Untuk setiap eksekusi quicksort harus bersesuaian dengan binary search tree (BST): pivot awal berada pada node rootl pivot dari tengah kiri merupakan subtree kiri root, pivot dari tengah kanan merupakan subtree kanan root, dan seterusnya. Jumlah perbandingan dari eksekusi Quicksort sama dengan perbandingan selama konstruksi BST dengan urutan masukan. Jadi, jumlah perbandingan rata-rata untuk Quicksort acak sama dengan average case dari menghasilkan BST ketika nilai yang dimasukkan <math>(x_1,x_2,...,x_n)</math> dari permutasi acak. |
Untuk setiap eksekusi quicksort harus bersesuaian dengan binary search tree (BST): pivot awal berada pada node rootl pivot dari tengah kiri merupakan subtree kiri root, pivot dari tengah kanan merupakan subtree kanan root, dan seterusnya. Jumlah perbandingan dari eksekusi Quicksort sama dengan perbandingan selama konstruksi BST dengan urutan masukan. Jadi, jumlah perbandingan rata-rata untuk Quicksort acak sama dengan average case dari menghasilkan BST ketika nilai yang dimasukkan <math>(x_1,x_2,...,x_n)</math> dari permutasi acak. |
||
Baris 184: | Baris 181: | ||
<math>E(C)= \sum_i \sum_{j<i}</math> |
<math>E(C)= \sum_i \sum_{j<i}</math> |
||
Tetapkan i dan j<i. Nilai <math>{x_1,x_2,...,x_j}</math>, setelah diurutkan, tetapkan interval j+1. Pengamatan struktural inti dimana <math>x_i</math> dibandingkan dengan <math>x_j</math> pada |
Tetapkan i dan j<i. Nilai <math>{x_1,x_2,...,x_j}</math>, setelah diurutkan, tetapkan interval j+1. Pengamatan struktural inti dimana <math>x_i</math> dibandingkan dengan <math>x_j</math> pada algoritme jika dan hanya jika <math>x_i</math> jatuh di dalam satu dari dua interval samping pada <math>x_j</math>. |
||
Amati bahwa sejak <math>(x_1,x_2,...,x_n)</math> merupakan permutasi acak, <math>(x_1,x_2,...,x_j,x_i)</math> juga merupakan permutasi acak, jadi probabilitas <math>x_i</math> berdekatan dengan <math>x_j</math> yang sama persis dengan <math>2/(j+1)</math>. |
Amati bahwa sejak <math>(x_1,x_2,...,x_n)</math> merupakan permutasi acak, <math>(x_1,x_2,...,x_j,x_i)</math> juga merupakan permutasi acak, jadi probabilitas <math>x_i</math> berdekatan dengan <math>x_j</math> yang sama persis dengan <math>2/(j+1)</math>. |
||
Baris 202: | Baris 199: | ||
Dari sudut pandang yang lumayan rumit, variabel seperti ''kiri'' dan ''kanan'' tidak menggunakan ruang konstan; tetapi menggunakan ''O''(log ''n'') bit pada indeks list dari ''n'' kali. Karena terdapat variabel pada setiap tumpukan frame, quicksort menggunakan cara Sedgewick yang membutuhkan <math>O((\log n)^2)</math> bit ruang. Kebutuhan ruang ini tidaklah buruk, walaupun sejak jika list yang mengandung elemen berbeda, maka akan membutuhkan paling kurang ''O''(''n'' log ''n'') bits ruang. |
Dari sudut pandang yang lumayan rumit, variabel seperti ''kiri'' dan ''kanan'' tidak menggunakan ruang konstan; tetapi menggunakan ''O''(log ''n'') bit pada indeks list dari ''n'' kali. Karena terdapat variabel pada setiap tumpukan frame, quicksort menggunakan cara Sedgewick yang membutuhkan <math>O((\log n)^2)</math> bit ruang. Kebutuhan ruang ini tidaklah buruk, walaupun sejak jika list yang mengandung elemen berbeda, maka akan membutuhkan paling kurang ''O''(''n'' log ''n'') bits ruang. |
||
Lainnya, kurang lebih, yang bukan |
Lainnya, kurang lebih, yang bukan algoritme In-Place, versi Quicksort yang menggunakan ruang ''O''(''n'') untuk menyimpan dan dapat mengimplementasikan urutan yang stabil. Tempat penyimpanan menyediakan inputan array dengan mudah dipartisi pada cara yang stabil dan kemudian menyalinnya kembali pada inputan array untuk pemanggilan rekursif yang berurutan. Optimisasi Sedgewick masih sangat sesuai. |
||
== Pivot yang Berbasis Pemilihan == |
== Pivot yang Berbasis Pemilihan == |
||
Algoritme seleksi memilih jumlah list ''k'' yang terkecil; masalah ini merupakan yang paling mudah secara umumnya daripada sorting. Algoritme seleksi yang sederhana teatpi efektif bekerja hampir sama seperti quicksort, kecuali yang daripada memanggil rekursif pada kedua sublist, algoritme ini hanya membuat satu pemanggilan rekursif ekor pada sublist yang mengandung elemen yang diinginkan. Perubahan kecil ini menurunkan kerumitan rata-rata pada linear atau ''O''(''n'') kali, dan membuatnya menjadi Algoritme In-Place. Ragam algoritme ini membawa worst case turun menjadi ''O''(''n''). |
|||
Sebaliknya setelah kita mengetahui worst case ''O''(''n'') |
Sebaliknya setelah kita mengetahui worst case ''O''(''n'') algoritme seleksi tersedia, kita dapat menggunakannya untuk mencari pivot ideal (median) pada setiap langkah quicksort, yang menghasilkan ragam kalkulasi waktu worst case ''O''(''n'' log ''n''). Pada implementasi praktiknya, bagaimanapun, varian ini dianggap lebih lambat dari rata-rata. |
||
== Ragam-ragam == |
== Ragam-ragam == |
||
Terdapat empat ragam quicksort yang paling terkenal: |
Terdapat empat ragam quicksort yang paling terkenal: |
||
* '''Balanced Quicksort:''' memilih pivot mungkin untuk mewakili pertengah dari nilai yang akan dipilih, dan kemudian mengikuti |
* '''Balanced Quicksort:''' memilih pivot mungkin untuk mewakili pertengah dari nilai yang akan dipilih, dan kemudian mengikuti algoritme quicksort seperti biasa. |
||
* '''External Quicksort:''' sama seperti quicksort yang biasanya kecuali pivot digantikan dengan buffer. Pertama, baca M/2 elemen pertama dan kedua menjadi buffer dan urutkan mereka. Baca elemen selanjutnya dari awal atau akhir untuk menyeimbangkan penulisan. Jika elemen selanjutnya lebih kurang dari buffer terendah, maka tulis elemen itu pada ruang yang tersedia pada awal. Jika lebih besar dari buffer tertinggi, maka tulis elemen itu pada akhir. Atau tidak tulis buffer terbesar atau terkecil, dan tempatkan elemen selanjutnya pada buffer. Tetap tulis elemen maksimum dan minimum untuk menghindari diurutkannya lagi elemen tengah yang telah terurut. Ketika selesai, tulis buffernya. Secara recursif urutkan kembali partisi yang lebih kecil, dan ulangi urutannya pada partisi yang tersisa. Cara ini merupakan tiga cara quicksort yang yang dimana buffer (partisi tengah) mewakili subarray yang telah diurut dari elemen yang ''kkira-kira'' sama dengan pivotnya. |
* '''External Quicksort:''' sama seperti quicksort yang biasanya kecuali pivot digantikan dengan buffer. Pertama, baca M/2 elemen pertama dan kedua menjadi buffer dan urutkan mereka. Baca elemen selanjutnya dari awal atau akhir untuk menyeimbangkan penulisan. Jika elemen selanjutnya lebih kurang dari buffer terendah, maka tulis elemen itu pada ruang yang tersedia pada awal. Jika lebih besar dari buffer tertinggi, maka tulis elemen itu pada akhir. Atau tidak tulis buffer terbesar atau terkecil, dan tempatkan elemen selanjutnya pada buffer. Tetap tulis elemen maksimum dan minimum untuk menghindari diurutkannya lagi elemen tengah yang telah terurut. Ketika selesai, tulis buffernya. Secara recursif urutkan kembali partisi yang lebih kecil, dan ulangi urutannya pada partisi yang tersisa. Cara ini merupakan tiga cara quicksort yang yang dimana buffer (partisi tengah) mewakili subarray yang telah diurut dari elemen yang ''kkira-kira'' sama dengan pivotnya. |
||
* '''Tiga cara Quicksort radiks''' (ditemukan oleh Sedgewick dan juga dikenal sebagai '''Multikey Quicksort'''): ialah kombinasi dari ''Radix sort'' dan Quicksort. Ambil sebuah elemen dari array (pivotnya) dan tempatkan karakter pertama pada string (multikey). Partisikan elemen sisa menjadi tiga set: karakter yang lebih kecil, sama, dan lebih besar dari karakter pivot. Urut secara rekursif partisi "kurang dari" dan "lebih dari" pada karakter yang sama. Urutkan secara rekursif partisi "sama dengan" dengan karakter selanjutnya (tanda). Pertimbangkan dengan mengurut menggunakan ''bytes'' atau ''words'' dari panjang W bit, best casenya ialah O(KN) dan worst casenya ialah O(2<sup>K</sup>N) atau paling tidak O(N<sup>2</sup>) sebagai quicksort standar, dengan diberikan untuk tanda khusus N<2<sup>K</sup>, dan K adalah konstanta yang tersembunyi pada seluruh algortima sorting pembanding semuanya termasuk quicksort. Ini merupakan salah satu dari tiga cara quicksort yang partisi tengah mewakili urutan subarray elemen (mudah) yang ''persis'' sama dengan pivot. |
* '''Tiga cara Quicksort radiks''' (ditemukan oleh Sedgewick dan juga dikenal sebagai '''Multikey Quicksort'''): ialah kombinasi dari ''Radix sort'' dan Quicksort. Ambil sebuah elemen dari array (pivotnya) dan tempatkan karakter pertama pada string (multikey). Partisikan elemen sisa menjadi tiga set: karakter yang lebih kecil, sama, dan lebih besar dari karakter pivot. Urut secara rekursif partisi "kurang dari" dan "lebih dari" pada karakter yang sama. Urutkan secara rekursif partisi "sama dengan" dengan karakter selanjutnya (tanda). Pertimbangkan dengan mengurut menggunakan ''bytes'' atau ''words'' dari panjang W bit, best casenya ialah O(KN) dan worst casenya ialah O(2<sup>K</sup>N) atau paling tidak O(N<sup>2</sup>) sebagai quicksort standar, dengan diberikan untuk tanda khusus N<2<sup>K</sup>, dan K adalah konstanta yang tersembunyi pada seluruh algortima sorting pembanding semuanya termasuk quicksort. Ini merupakan salah satu dari tiga cara quicksort yang partisi tengah mewakili urutan subarray elemen (mudah) yang ''persis'' sama dengan pivot. |
||
== Membandingkan dengan |
== Membandingkan dengan Algoritme sorting yang lainnya == |
||
Quicksort ialah versi optimisasi memori dari '''Binary Tree Sort'''. Alih-alih memasukkan item secara berurutan pada tree yang jelas, quicksort mengatur mereka secara bersamaan pada tree yang tersirat dengan pemanggilan rekursif. |
Quicksort ialah versi optimisasi memori dari '''Binary Tree Sort'''. Alih-alih memasukkan item secara berurutan pada tree yang jelas, quicksort mengatur mereka secara bersamaan pada tree yang tersirat dengan pemanggilan rekursif. Algoritme membuat perbandingan yang persis sama, tetapi pada urutan yang berbeda. Sifat yang paling diinginkan dari Algoritme Sorting ialah kestabilannya - yang urutan elemennya pada nilai yang sama tidak berubah, memberikan urutan kontrol dari tabel multikey (contoh direktori atau listing folder) pada umumnya. Sifat ini sangat sulit untuk diatur pada quicksort (atau in-place) (yang hanya menggunakan memori tambahan tetap untuk pointer dan buffer, dan memori tambahan lognN untuk pengaturan untuk rekursif yang tampak maupun tidak. Untuk ragam Quicksort melibatkan memori lebih dikarenakan perwakilannya menggunakan pointer (contoh list atau tree) atau file (list yang sering digunakan), yang menjaga stabilitas dengan mudah. Untuk contoh yang lebih kompleks dan rumit, struktur data cenderung meningkatkan waktu yang dibutuhkan, secara umum meningkatkan memori virtual atau disk. |
||
Pesaing quicksort langsung ialah '''Heapsort'''. Waktu kalkulasi Worst case Heasort selalu bernilai ''O''(''n'' log ''n''). Tetapi average casenya heapsort diasumsikan lebih lambat dari Quicksort in-place standarnya. Masalah ini masih diperdebatkan dan masih diteliti, karena ada beberapa jurnal ilmiah yang mengatakan sebaliknya. |
Pesaing quicksort langsung ialah '''Heapsort'''. Waktu kalkulasi Worst case Heasort selalu bernilai ''O''(''n'' log ''n''). Tetapi average casenya heapsort diasumsikan lebih lambat dari Quicksort in-place standarnya. Masalah ini masih diperdebatkan dan masih diteliti, karena ada beberapa jurnal ilmiah yang mengatakan sebaliknya.<ref>{{cite web| first=Paul| last=Hsieh| title=Sorting revisited.| url=http://www.azillionmonkeys.com/qed/sort.html| year=2004| accessdate=26 April 2010| publisher = www.azillionmonkeys.com}}</ref><ref>{{cite web| first=David| last=MacKay| title=Heapsort, Quicksort, and Entropy| url=http://users.aims.ac.za/~mackay/sorting/sorting.html| date=1 December 2005| accessdate=26 April 2010| publisher=users.aims.ac.za/~mackay| archive-date=2009-04-01| archive-url=https://web.archive.org/web/20090401163041/http://users.aims.ac.za/~mackay/sorting/sorting.html| dead-url=yes}}</ref> '''Introsort merupakan variasi dari quicksort yang menukar heapsort ketika terdapat kasus buruk yang dideteksi untuk menghindari worst case quicksort. Lebih lanjut diketahui heapsort akan sangat dibutuhkan, menggunakan heapsort secara langsung akan lebih cepat daripada harus menunggu introsort untuk menukarnya. |
||
Quicksort juga bersaing dengan '''Mergesort''', |
Quicksort juga bersaing dengan '''Mergesort''', algoritme sorting rekursif yang lainnya tetapi dengan keuntungan waktu kalkulasi worst casenya ''O''(''n'' log ''n''). Mergesort merupakan sorting stabil, tidak seperti quicksort in-place dan heapsort standar, dan dapat dengan mudah diadaptasikan untuk berjalan pada ''linked list'' dan list dengan penyimpanan yang sangat besar pada media dengan akses lambat seperti disk penyimpanan atau penyimpanan pada jaringan. Seperti pula mergesort, quicksort dapat diimplementasikan sebagai sorting stabil in-place,<ref>{{Cite web |url=http://h2database.googlecode.com/svn/trunk/h2/src/tools/org/h2/dev/sort/InPlaceStableQuicksort.java |title=A Java implementation of in-place stable quicksort |access-date=2012-11-17 |archive-date=2013-05-16 |archive-url=https://web.archive.org/web/20130516093418/http://h2database.googlecode.com/svn/trunk/h2/src/tools/org/h2/dev/sort/InPlaceStableQuicksort.java |dead-url=yes }}</ref> tetapi hal ini jarang digunakan. Walaupun quicksort dikatakan dapat berjalan pada linked list, tapi sering mendapatkan pivot yang buruk tanpa menggunakan akses acak. Kerugian utama dari mergesort ialah, ketika berjalan pada array, implementasi yang efisient membutuhkan ruang tambahan ''O''(''n''), sedangkan variasi dari quicksort dengan patitisasi in-place dan rekursif ekor hanya menggunakan memori sebesar ''O''(log ''n''). (dengan catatan bahwa ketika menjalankannya pada linked list, mergesort hanya membutuhkan ruang tambahan yang konstan, namun kecil). |
||
'''Bucket Sort''' dengan dua ''keranjang'' atau ''bucket'' hampir sama dengan quicksort; pivot pada kasus ini secara efektif mengambil nilai tengah dari range nilai, yang dimana berjalan dengan sangat baik pada average case untuk input yang terdistribusi secara umumnya. |
'''Bucket Sort''' dengan dua ''keranjang'' atau ''bucket'' hampir sama dengan quicksort; pivot pada kasus ini secara efektif mengambil nilai tengah dari range nilai, yang dimana berjalan dengan sangat baik pada average case untuk input yang terdistribusi secara umumnya. |
||
Baris 236: | Baris 231: | ||
=== Referensi === |
=== Referensi === |
||
*R. Sedgewick, Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978. [http://delivery.acm.org/10.1145/360000/359631/p847-sedgewick.pdf?key1=359631&key2=9191985921&coll=DL&dl=ACM&CFID=6618157&CFTOKEN=73435998 Implementing Quicksort Programs] |
* R. Sedgewick, Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978. [http://delivery.acm.org/10.1145/360000/359631/p847-sedgewick.pdf?key1=359631&key2=9191985921&coll=DL&dl=ACM&CFID=6618157&CFTOKEN=73435998 Implementing Quicksort Programs] |
||
*Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." ''Discrete Applied Mathematics'' 154(1): 1-5. |
* Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." ''Discrete Applied Mathematics'' 154(1): 1-5. 2006. |
||
*Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." [[Comm. ACM]] 4(7), 321-322, 1961 |
* Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." [[Comm. ACM]] 4(7), 321-322, 1961 |
||
*Hoare, C. A. R. [http://dx.doi.org/10.1093/comjnl/5.1.10 "Quicksort."] Computer Journal 5 (1): 10-15. (1962). (Reprinted in Hoare and Jones: [http://portal.acm.org/citation.cfm?id=SERIES11430.63445 ''Essays in computing science''], 1989.) |
* Hoare, C. A. R. [http://dx.doi.org/10.1093/comjnl/5.1.10 "Quicksort."] Computer Journal 5 (1): 10-15. (1962). (Reprinted in Hoare and Jones: [http://portal.acm.org/citation.cfm?id=SERIES11430.63445 ''Essays in computing science''], 1989.) |
||
*David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997 |
* David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997 |
||
*[[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages |
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging. |
||
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. [[MIT Press]] and [[McGraw-Hill]], 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp. |
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. [[MIT Press]] and [[McGraw-Hill]], 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp. 145–164. |
||
*A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379. |
* A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370–379. |
||
*[[Faron Moller]]. [http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf Analysis of Quicksort]. CS 332: Designing Algorithms. Department of Computer Science, [[Swansea University]]. |
* [[Faron Moller]]. [http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf Analysis of Quicksort]. CS 332: Designing Algorithms. Department of Computer Science, [[Swansea University]]. |
||
* Conrado Martínez and Salvador Roura, ''Optimal sampling strategies in quicksort and quickselect.'' SIAM J. Computing 31(3):683-705, 2001. |
* Conrado Martínez and Salvador Roura, ''Optimal sampling strategies in quicksort and quickselect.'' SIAM J. Computing 31(3):683-705, 2001. |
||
* Jon L. Bentley and M. Douglas McIlroy, [http://citeseer.ist.psu.edu/bentley93engineering.html Engineering a Sort Function], |
* Jon L. Bentley and M. Douglas McIlroy, [http://citeseer.ist.psu.edu/bentley93engineering.html Engineering a Sort Function], ''Software—Practice and Experience'', Vol. 23(11), 1249–1265, 1993 |
||
== Pranala luar == |
|||
{{Wikibooks|Algorithm implementation|Sorting/Quicksort|Quicksort}} |
{{Wikibooks|Algorithm implementation|Sorting/Quicksort|Quicksort}} |
||
* [ |
* [https://www.toptal.com/developers/sorting-algorithms Algoritme sorting animasi: Quicksort] – Demonstrasi grafis dan diskusi Quicksort |
||
* [ |
* [https://www.toptal.com/developers/sorting-algorithms/quick-sort-3-way Animated Sorting Algorithms: Demonstrasi grafis dan diskusi dari partisi 3-cara Quicksort] |
||
* [http://pages.stern.nyu.edu/~panos/java/Quicksort/index.html Tutorial interaktif untuk Quicksort] |
* [http://pages.stern.nyu.edu/~panos/java/Quicksort/index.html Tutorial interaktif untuk Quicksort] |
||
* [http://www.yorku.ca/sychen/research/sorting/index.html Quicksort applet] dengan pemanggilan rekursif "Urutan-Level" untuk membantu meningkatkan |
* [http://www.yorku.ca/sychen/research/sorting/index.html Quicksort applet] dengan pemanggilan rekursif "Urutan-Level" untuk membantu meningkatkan analisis algoritme. |
||
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html#SECTION001412000000000000000 Open Data Structures - Section 11.1.2 - Quicksort] |
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/11_1_Comparison_Based_Sorti.html#SECTION001412000000000000000 Open Data Structures - Section 11.1.2 - Quicksort] |
||
* [http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort Quicksort multidimensional pada Java] |
* [http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort Quicksort multidimensional pada Java] {{Webarchive|url=https://web.archive.org/web/20051124012106/http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort |date=2005-11-24 }} |
||
* [http://en.literateprograms.org/Category:Quicksort Implementasi Literatur Quicksort pada ragam bahasa] pada Program Literatur |
* [http://en.literateprograms.org/Category:Quicksort Implementasi Literatur Quicksort pada ragam bahasa] {{Webarchive|url=https://web.archive.org/web/20080509021614/http://en.literateprograms.org/Category:Quicksort |date=2008-05-09 }} pada Program Literatur |
||
* [http://coderaptors.com/?QuickSort Java Applet grafis berwarna] yang dapat bereksperimen dengan pernyataan inisial dan menunjukkan statistik |
* [http://coderaptors.com/?QuickSort Java Applet grafis berwarna] {{Webarchive|url=https://web.archive.org/web/20120218155727/http://coderaptors.com/?QuickSort |date=2012-02-18 }} yang dapat bereksperimen dengan pernyataan inisial dan menunjukkan statistik |
||
{{clear}} |
{{clear}} |
||
{{sorting}} |
{{sorting}} |
||
|} |
|||
[[Kategori: |
[[Kategori:Algoritme pengurutan]] |
||
[[no:Sorteringsalgoritme#Quick sort]] |
Revisi terkini sejak 6 Desember 2022 04.43
![]() Visualisasi Algoritme Quicksort. Garis horisontal merupakan nilai sumbu. | |
Quicksort | |
---|---|
Kelas | Algoritme Sorting |
Waktu | O(n2) |
Kasus rata-rata | O(n log n) |
Kasus terburuk | O(n log n) |
Quicksort merupakan Algoritme pengurutan yang dikembangkan oleh Tony Hoare. performa rata-rata pengurutan O(n log n) untuk mengurutkan n item. Algoritme ini juga dikenal sebagai Partition-Exchange Sort atau disebut sebagai Sorting Pergantian Pembagi. Pada kasus terburuknya, algoritme ini membuat perbandingan O(n2), walaupun kejadian seperti ini sangat langka. Quicksort sering lebih cepat dalam praktiknya daripada algoritme urut gabung dan heapshort.[1] Dan juga, urutan dan referensi lokalisasi memori quicksort bekerja lebih baik dengan menggunakan cache CPU, jadi keseluruhan sorting dapat dilakukan hanya dengan ruang tambahan O(log n).[2]
Quicksort merupakan sorting pembanding dan pada implementasi efisien tidak merupakan algoritme sorting yang stabil.
Algoritme
[sunting | sunting sumber]Quicksort merupakan Algoritme Pembagi. Pertama quicksort membagi list yang besar menjadi dua buah sub list yang lebih kecil: element kecil dan element besar. Quicksort kemudian dapat menyortir sub list itu secara rekursif.
Langkah-Langkah pengerjaannya ialah:
- Ambil sebuah elemen, yang disebut dengan pivot, pada sebuah daftar.
- Urutkan kembali sebuah list sehingga elemen dengan nilai yang kecil dari pivot berada sebelum pivot, sedangkan seluruh element yang memiliki nilai yang lebih besar dari pivot berada setelahnya (nilai yang sama dapat berada pada pivot setelahnya). Setelah pemisahan, pivot berada pada posisi akhirnya. Operasi ini disebut Partition.
- Sub list kemudian disortir secara recursif dari elemen yang lebih kecil dan sub list dari elemen yang lebih besar.
Kasus dasar dari rekusrif ialah list dari besaran nol atau satu, yang tidak perlu untuk di sorting.
Versi Sederhana
[sunting | sunting sumber]Dalam Pseudocode sederhana, Algoritmanya dapat dinyatakan sebagai berikut:
function quicksort('array')
if length('array') ≤ 1
return 'array' // an array of zero or one elements is already sorted
select and remove a pivot value 'pivot' from 'array'
create empty lists 'less' and 'greater'
for each 'x' in 'array'
if 'x' ≤ 'pivot' then append 'x' to 'less'
else append 'x' to 'greater'
return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Quicksort-diagram.svg/200px-Quicksort-diagram.svg.png)
Perlu diperhatikan bahwa kita hanya memeriksa elemen dengan membandingkan mereka pada elemen yang lain. Prosedur ini disebuk Sorting Pembandingan. Jenis ini juga merupakan jenis sorting yang stabil (asumsikan bahwa untuk setiap method menerima elemen pada urutan aslinya dan pivot yang dipilih merupakan elemen terakhir dari nilai yang sama).
Kebenaran dari algoritme partisi didasari pada dua argumen berikut:
- Pada setiap iterasi, seluruh elemen diproses selama ini berada pada posisi yang diinginkan: sebelum pivot lebih kurang dari nilai pivot, setelah pivot lebih besar dari nilai pivot (Invarian Loop).
Kebenaran dari keseluruhan algortima dapat dibuktikan dengan penyederhanaan fakta: untuk elemen nol atau satu, algoritme tidak akan mengubah data; untuk jumlah data yang lebih besar, algoritme akan menghasilkan dua bagian, elemen yang kurang dari pivot dan elemen yang lebih besar dari nya, data ini sendiri akan diurutkan secara hipotesis rekursif.
![](http://upload.wikimedia.org/wikipedia/commons/9/9c/Quicksort-example.gif)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/84/Partition_example.svg/200px-Partition_example.svg.png)
Versi In-place
[sunting | sunting sumber]Kerugian dari versi sederhana diatas membutuhkan ruang simpan O(n) yang lebih besar, yang sama buruknya seperti merge sort. Memory tambahan yang dibutuhkan dapat juga secara radikal berpengaruh pada kecepatan dan performa cache pada implementasi praktiknya. Terdapat juga versi yang lebih rumit yang menggunakan algoritme partisi in-place dan dapat mencapai urutan lengkap menggunakan ruang O(logn) (tidak dihitung input) pada rata-rata (untuk sekali pemanggilan tumpukan). Kita mulai dengan fungsi partisi:
// left is the index of the leftmost element of the array
// right is the index of the rightmost element of the array (inclusive)
// number of elements in subarray = right-left+1
function partition(array, 'left', 'right', 'pivotIndex')
'pivotValue':= array['pivotIndex']
swap array['pivotIndex'] and array['right'] // Move pivot to end
'storeIndex':= 'left'
for 'i' from 'left' to 'right' - 1 // left ≤ i < right
if array['i'] < 'pivotValue'
swap array['i'] and array['storeIndex']
'storeIndex':= 'storeIndex' + 1
swap array['storeIndex'] and array['right'] // Move pivot to its final place
return 'storeIndex'
Ini merupakan Algoritme Partisi In-Place. algortima ini memisahkan bagian dari array antara index kiri dan kanan secara inklusif, dengan memindahkan seluruh elemen kurang dari Setelah kita memiliki ini, menulis quicksort sendiri ialah mudah:
Setiap pemanggilan rekursif pada fungsi quicksort ini mengurangi besar dari array yang akan diurutkan paling tidak satu elemen, semenjak setiap elemen pada pivotNewIndex diletakkan pada posisi akhirnya. Oleh karena itu, algoritme ini menjamin mengakhiri pemanggilan rekursif pada paling banyak n pemanggilan. Bagaimanapun, versi dari quicksort ini tidak stabil semenjak pengurutan elemen partisi hanya dilakukan pada satu partisi. Pemilihan Pivot[sunting | sunting sumber]Pada setiap versi awal quicksort, elemen yang paling kiri dari partisi akan sering menjadi pilihan sebagai elemen pivot. Sayangnya, ini menyebabkan perilaku worst-case pada array yang telah diurut, yang merupakan penggunaan kasus yang sering dipakai. Masalah ini dengan mudah diselesaikan dengan memilih salah satu dari index acak untuk pivot, memilih indek tengah dari partisi atau (secara khusus untuk partisi panjang) memilih median dari elemen awal, tengah, dan akhir dari partisi untuk pivot (sebagaimana direkomendari oleh Robert Sedgewick.[3][4] Memilih elemen pivot juga rumit dengan dengan kehadiran dari Integer Overflow. Jika indeks batas dari subarray yang diurutkan cukup besar, ungkapan naif untuk indeks tengah, (kiri + kanan)/2, akan menyebabkan luapan dan memberikan indeks pivot yang salah. Masalah ini dapat terselesaikan dengan menggunakan, sebagai contoh, kiri + (kanan-kiri)/2 pada indeks elemen tengah, pada masalah dari aritmetika kompleks. Masalah yang sama muncul pada beberapa metode yang lain dari pemilihan elemen pivot. Optimisasi[sunting | sunting sumber]Dua optimisasi penting lainnya, juga disarankan oleh Robert Sedgewick, sebagai pernyataan yang secara umum diakui, dan digunakan secara luas ialah:[5][6][7]
Paralelisasi[sunting | sunting sumber]Seperti Merge Sort, Quicksort juga dapat diparalelisasikan dikarenakan sifat pembagi-dan-penakluk alaminya. Operasi Partisi In-Place sulit untuk diparalelisasikan, tetapi setelah dibagi, bagian list yang berbeda dapat diurutkan secara paralel. Berikut ini merupakan pendekatan langsung: Jika kita memiliki prosesor , kita dapat membagi list dari element menjadi sublist pada rata-rata waktu O(n), kemudian mengurutkannya pada rata-rata waktu . Abaikan pra pengolahan O(n) dan waktu penggabungan merupakan Linear Speedup atau Percepatan Linear. Jika pemisahannya tak tampak, abaikan nilai waktu penggabungan O(n). Jika Partisi pemisah didasari pada penggantian pivot, sangat rumit untuk memparelisasikan dan secara langsung memiliki nilai waktu O(n). Jika diberikan O(logn) atau lebih banyak prosesor, hanya sebesar O(n) waktu keseluruhan yang digunakan, sedangkan pendekatan dengan linear speedup akan mencapai waktu O(log n) secara keseluruhan. Salah satu keuntungan dari quicksort paralel sederhana daripada algortima sorting paralel yang lain ialah tidak dibutuhkannya sinkronisasi, tetapi kerugiannya ialah tipe sorting ini masih membutuhkan O(n) dan hanya sublinear speedup dari O(log n) yang dapat dicapai. Rangkaian baru dimulai segera setelah sublist tersedia untuk bekerja dan tidak berkomunikasi dengan rangkaian yang lain. Ketika setelah semua rangkaian selesai, Proses sorting juga akan selesai. Satu lagi algortima sorting paralel yang mutakhir dapat mencapai ikatan waktu yang bahkan lebih baik.[8] Sebagai contoh pada tahun 1991 David Powers menjelaskan quicksort paralelisasi (dan radix sort yang dapat berjalan di waktu O(log n) pada CRWC prosesor n dengan menjalankan pemisahan secara tak langsung.[9] Analisis Average-case menggunakan kemungkinan berlainan[sunting | sunting sumber]Quicksort menggunakan waktu rata-rata O(n log n), ketika inputan merupakan permutasi acak. Mengapa? Sebagai pemulaian, tidak sulit untuk mengetahui bahwa opearasi pemisahan menggunakan O(n) waktu. Pada kasus unbalance sering muncul, setiap kita melakukan partisi kita membagi list menjadi dua buah sublist dari besar 0 dan (sebagai contoh jika seluruh elemen array itu sama). Ini berarti setiap rekursif memanggil proses list dari besar kurang satu dari list sebelumnya. Konsekuensinya, kita dapat membuat penggilan bersarang sebelum kita menccapai list dengan besar 1. Ini berarti bahwa pemanggilan tree ialah rantai linear dari pemanggilan bersarang . Pemanggilan ke- memanggil pada partisi, dan , jadi pada kasus ini, Quick sort mengambil waktu sebesar . Itu merupakan worst case dimana input yang diberikan dari perbandingan dilakukan oleh algoritme sorting, terdapat pula algortima penyesuaian yang secara efektif membuat inputan worst-case pada quicksort menjadi mudah, dengan tanpa teknik pemilihan pivot secara khusus.[10] Pada kasus balance, setiap kali kita melakukan partisi, kita membagi list menjadi dua buah sublist yang bernilai hampir sama. Ini berarti setiap proses pemanggilan rekursif memanggil setengah dari besar list. Konsekuensinya, kita dapat hanya memakai pemanggilan bersarang sebelum mencapai list dengan besar 1. Ini berarti bahwa kedalaman pemanggilan tree sebesar . Tetapi tidak ada dua pemanggilan pada level pemanggilan tree pada bagian yang sama dari list yang aslinya; oleh karena itu setiap level pemanggilan hanya membutuhkan waktu keseluruhan O(n) (setiap pemanggilan memiliki nilai keluar yang konstan, tetapi sejak terdapat hanya O(n) pemanggilan pada setiap level, kejadian ini digolongkan pada faktor O(n)). Hasilnya ialah algortima hanya menggunakan waktu sebanyak O(n log n). Sebenarnya, seimbang secara sempurna tidak dibutuhkan; bahkan jika setiap pivot membagi elemen dengan 75% pada satu sisi dan 25% pada sisi yang lainnya (atau pada pecahan tetap), pemanggilan dalam masih dibutuhkan untuk , jadi total running time masih berupa O(n log n). Jadi apa yang terjadi pada average case? Jika pivot memiliki peringkat acak di tengah 50 persen, yang di antara persentil ke-25 dan persentil ke-75, kemudian memisahkan elemen dengan paling kurang 25% dan paling banyak 75% dari setiap sisi. Jika kita dapat secara konsisten memilih pivot dari pertengahan 50 persen, kita hanya harus memisahkan list paling banyak kali sebelum mencapai list sebesar 1, menghasilkan sebuah algoritme O(n log n) Ketika inputan merupakan permutasi acak, pivot akan memiliki peringkat acak, dan tidak menjamin berada pada pertengahan 50 persen. Bagaimanapun, ketika kita memulai dari permutasi acak, setiap pemanggilan pivot secara rekursif memiliki peringkat acak dari listnya, dan jika terdapat pada pertengahan list, maka akan menghabiskan waktu setengah. Itu cukup bagus, anggap bahwa kamu membalikkan koin: kepala berarti bahwa peringkat pivot berada pada 50 persen, sedang ekor tidak. Anggap bahwa kamu membalikkan coin berkali-kali sehingga mendapatkan kepala sejumlah k, walaupun akan menghabiskan banyak waktu, secara rata-rata hanya membutuhkan pembalikan 2k, kesempatan yang kamu tidak akan dapatkan sebesar kepala setelah lemparan sangat mustahil (dapat diteliti menggunakan ikatan Chernoff). Dengan memakan cara yang sama, rekursif yang dilakukan oleh Quicksort akan mengentikan average case pada pemanggilan dari hanya . Tetapi jika pemanggilan rata-rata ialah O(long n), dan setiap level dari proses pemanggilan tree paling banyak elemen, makan jumlah total dari tugas yang dilakukan pada kasus average case ialah O(n log n). Perlu diperhatikan bahwa algoritme tidak perlu memverifikasi pivot berada ditengah jika diberikan pecahan tetap acak dari berapa kali masukkan, yang cukup untuk kerumitan yang diinginkan. Analisis Average-case menggunakan rekursif[sunting | sunting sumber]Pendekatan alternatif digunakan untuk mengatur hubungan rekursif untuk faktor T(n), waktu yang dibutuhkan untuk mengurutkan list dari besar . Pada sekian banyak kasus unbalanced, satu Quicksort dapat melibatkan tugas O(n) ditambah pemanggilan dua rekursif pada list dan , jadi hubungan rekurensnya ialah Hubungan ini sama dengan Insertion Sort dan Selection Sort, dan dapat menyelesaikan hingga kasus terburuk . Pada kebanyakan kasus balanced, satu pemanggilan quicksort dapat melibatkan O(n) tugas dengan ditambah dua pemanggilan rekursif pada list dengan besar , sehingga hubungan rekursifnya ialah: Teorima dasar menjelaskan kepada kita bahwa T(n) = O(n log n). Garis besar dari pembuktian formal dari O(n log n) dapat dijelaskan sebagai berikut. Asumsikan bahwa tidak ada duplikasi dimana duplikasi itu dapat ditangani dengan pre dan post prosesing linear, atau anggap bahwa kasus lebih mudah dari yang dianalisiskan. Ketika input merupakan permutasi acak, peringkat dari pivot diseragamkan secara acak dari 0 hingga n=1. Kemudian bagian hasil dari partisi memiliki besaran i dan n-i-1, dan i merupakan seragam acak dari 0 hingga n-1. Jadi, jika dirata-ratakan dari semua pemisahan yang mungkin dan melihat bahwa seluruh perbandingan angka untuk pemisahan ialah , jumlah rata-rata dari pembanding dari keseluruhan permutasi dari urutan input dapat diperkirakan secara akuran dengan menyelesaikan hubungan rekursif ini: Dimana rekursifnya Ini berarti bahwa, secara rata-rata, Quicksort melakukan hanya sekitar 39% lebih buruk dari best casenya. Hal ini menjelaskan bahwa average case lebih dekat pada best case daripada worst case. Juga perlu dicatat bahwa Comparison Sort tidak dapat menggunakan kurang dari perbandingan secara rata-rata untuk mengurutkan item. Seandainya besar, maka akan menghasilkan , sehingga quicksort tidak akan lebih buruk dari comparison sort. Perhitungan waktu yang cepat ini menjadi alasan mengapa secara praktiknya quicksort lebih dominan dibandingkan algortima sorting yang lainnya. Analisis Quicksort acak[sunting | sunting sumber]Menggunakan analisis yang sama, seseorang dapat menunjukkan bahwa quicksort yang teracak memiliki sifat yang diinginkan, untuk inputan apapun, membutuhkan O(n log n) kali. Bagaimanapun, terdapat bukti yang kombinatorial, yang lebih elegan dari kedua analisis menggunakan kemungkinan yang berlainan dan analisis menggunakan rekursif. Untuk setiap eksekusi quicksort harus bersesuaian dengan binary search tree (BST): pivot awal berada pada node rootl pivot dari tengah kiri merupakan subtree kiri root, pivot dari tengah kanan merupakan subtree kanan root, dan seterusnya. Jumlah perbandingan dari eksekusi Quicksort sama dengan perbandingan selama konstruksi BST dengan urutan masukan. Jadi, jumlah perbandingan rata-rata untuk Quicksort acak sama dengan average case dari menghasilkan BST ketika nilai yang dimasukkan dari permutasi acak. Ditinjau dari pembuatan BST dengan memasukan urutan nilai yang membentuk permutasi acak. Jika C dianggap sebagai waktu pembuatan BST, maka kita akan memiliki: dengan melinearisasikan ekspektasi, nilai E(C) dari C adalah Tetapkan i dan j<i. Nilai , setelah diurutkan, tetapkan interval j+1. Pengamatan struktural inti dimana dibandingkan dengan pada algoritme jika dan hanya jika jatuh di dalam satu dari dua interval samping pada . Amati bahwa sejak merupakan permutasi acak, juga merupakan permutasi acak, jadi probabilitas berdekatan dengan yang sama persis dengan . Dan menjadi Perhitungan akhir dengan: Kompleksitas Ruang[sunting | sunting sumber]Ruang yang digunakan oleh quicksort tergantung dari versi yang digunakan. Versi In-Place dari Quicksort menggunakan kerumitan ruang dari O(long n), bahkan pada worst case, ketika diimplementasikan menggunakan beberapa strategi berikut:
Quicksort dengan Sistem Partisi In-Place dan unstable menggunakan ruang tambahan konstan sebelum membuat panggilan rekursif manapun. Quicksort haru menyimpan jumlah informasi tetap untuk setiap pemanggilan rekursif bersarang. Sejak best case dapat membuat paling banyak O(long n) pemanggilan rekursif bersarang, yang menggunakan ruang O(log n). Bagaimanapun cara Sedgewick untuk membatasi pemanggilan rekursif, pada worst case quicksort dapat membuat pemanggilan bersarang O(n) dan membutuhkan ruang tambahan O(n). Dari sudut pandang yang lumayan rumit, variabel seperti kiri dan kanan tidak menggunakan ruang konstan; tetapi menggunakan O(log n) bit pada indeks list dari n kali. Karena terdapat variabel pada setiap tumpukan frame, quicksort menggunakan cara Sedgewick yang membutuhkan bit ruang. Kebutuhan ruang ini tidaklah buruk, walaupun sejak jika list yang mengandung elemen berbeda, maka akan membutuhkan paling kurang O(n log n) bits ruang. Lainnya, kurang lebih, yang bukan algoritme In-Place, versi Quicksort yang menggunakan ruang O(n) untuk menyimpan dan dapat mengimplementasikan urutan yang stabil. Tempat penyimpanan menyediakan inputan array dengan mudah dipartisi pada cara yang stabil dan kemudian menyalinnya kembali pada inputan array untuk pemanggilan rekursif yang berurutan. Optimisasi Sedgewick masih sangat sesuai. Pivot yang Berbasis Pemilihan[sunting | sunting sumber]Algoritme seleksi memilih jumlah list k yang terkecil; masalah ini merupakan yang paling mudah secara umumnya daripada sorting. Algoritme seleksi yang sederhana teatpi efektif bekerja hampir sama seperti quicksort, kecuali yang daripada memanggil rekursif pada kedua sublist, algoritme ini hanya membuat satu pemanggilan rekursif ekor pada sublist yang mengandung elemen yang diinginkan. Perubahan kecil ini menurunkan kerumitan rata-rata pada linear atau O(n) kali, dan membuatnya menjadi Algoritme In-Place. Ragam algoritme ini membawa worst case turun menjadi O(n). Sebaliknya setelah kita mengetahui worst case O(n) algoritme seleksi tersedia, kita dapat menggunakannya untuk mencari pivot ideal (median) pada setiap langkah quicksort, yang menghasilkan ragam kalkulasi waktu worst case O(n log n). Pada implementasi praktiknya, bagaimanapun, varian ini dianggap lebih lambat dari rata-rata. Ragam-ragam[sunting | sunting sumber]Terdapat empat ragam quicksort yang paling terkenal:
Membandingkan dengan Algoritme sorting yang lainnya[sunting | sunting sumber]Quicksort ialah versi optimisasi memori dari Binary Tree Sort. Alih-alih memasukkan item secara berurutan pada tree yang jelas, quicksort mengatur mereka secara bersamaan pada tree yang tersirat dengan pemanggilan rekursif. Algoritme membuat perbandingan yang persis sama, tetapi pada urutan yang berbeda. Sifat yang paling diinginkan dari Algoritme Sorting ialah kestabilannya - yang urutan elemennya pada nilai yang sama tidak berubah, memberikan urutan kontrol dari tabel multikey (contoh direktori atau listing folder) pada umumnya. Sifat ini sangat sulit untuk diatur pada quicksort (atau in-place) (yang hanya menggunakan memori tambahan tetap untuk pointer dan buffer, dan memori tambahan lognN untuk pengaturan untuk rekursif yang tampak maupun tidak. Untuk ragam Quicksort melibatkan memori lebih dikarenakan perwakilannya menggunakan pointer (contoh list atau tree) atau file (list yang sering digunakan), yang menjaga stabilitas dengan mudah. Untuk contoh yang lebih kompleks dan rumit, struktur data cenderung meningkatkan waktu yang dibutuhkan, secara umum meningkatkan memori virtual atau disk. Pesaing quicksort langsung ialah Heapsort. Waktu kalkulasi Worst case Heasort selalu bernilai O(n log n). Tetapi average casenya heapsort diasumsikan lebih lambat dari Quicksort in-place standarnya. Masalah ini masih diperdebatkan dan masih diteliti, karena ada beberapa jurnal ilmiah yang mengatakan sebaliknya.[11][12] Introsort merupakan variasi dari quicksort yang menukar heapsort ketika terdapat kasus buruk yang dideteksi untuk menghindari worst case quicksort. Lebih lanjut diketahui heapsort akan sangat dibutuhkan, menggunakan heapsort secara langsung akan lebih cepat daripada harus menunggu introsort untuk menukarnya. Quicksort juga bersaing dengan Mergesort, algoritme sorting rekursif yang lainnya tetapi dengan keuntungan waktu kalkulasi worst casenya O(n log n). Mergesort merupakan sorting stabil, tidak seperti quicksort in-place dan heapsort standar, dan dapat dengan mudah diadaptasikan untuk berjalan pada linked list dan list dengan penyimpanan yang sangat besar pada media dengan akses lambat seperti disk penyimpanan atau penyimpanan pada jaringan. Seperti pula mergesort, quicksort dapat diimplementasikan sebagai sorting stabil in-place,[13] tetapi hal ini jarang digunakan. Walaupun quicksort dikatakan dapat berjalan pada linked list, tapi sering mendapatkan pivot yang buruk tanpa menggunakan akses acak. Kerugian utama dari mergesort ialah, ketika berjalan pada array, implementasi yang efisient membutuhkan ruang tambahan O(n), sedangkan variasi dari quicksort dengan patitisasi in-place dan rekursif ekor hanya menggunakan memori sebesar O(log n). (dengan catatan bahwa ketika menjalankannya pada linked list, mergesort hanya membutuhkan ruang tambahan yang konstan, namun kecil). Bucket Sort dengan dua keranjang atau bucket hampir sama dengan quicksort; pivot pada kasus ini secara efektif mengambil nilai tengah dari range nilai, yang dimana berjalan dengan sangat baik pada average case untuk input yang terdistribusi secara umumnya. Lihat juga[sunting | sunting sumber]Catatan[sunting | sunting sumber]
Referensi[sunting | sunting sumber]
Pranala luar[sunting | sunting sumber]![]()
|