Algoritma penyortiran

Dalam ilmu komputer, algoritme penyortiran atau algoritme pemilahan merupakan algoritme yang menempatkan elemen daftar pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerik dan urutan leksikografis. Penyortiran yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritme lain seperti algoritme pencarian dan algoritme penggabungan yang membutuhkan data input di dalam daftar terurut, yang juga sering digunakan untuk menganonikalisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:

Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.
Output merupakan permutasi (pengurutan kembali) dari inputan yang diberikan.

Sejak permulaan komputasi, masalah pengurutan ini telah menarik penelitian yang serius, mungkin dikarenakan kerumitan dari penyelesaian secara efisien disamping mudah, dan dengan statemen yang kita mengerti. Sebagai contoh, bubble sort pertama sekali ditemukan pada tahun 1956.^[1] Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritme penyortiran baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritme penyortiran sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritme untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritme inti, seperti Notasi Big O, Algoritme Pembagi, Struktur Data, Algoritme Acak, Analisis Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.

Klasifikasi

Algoritme penyortiran digunakan pada Ilmu Komputer sering diklasifikasikan dengan:

Kompleksitas Komputasi (Average, Best, Worst case) perbandingan elemen dengan besar list(n). Untuk beberapa Algoritme sorting kasus yang paling baiknya ialah O(n log n) dan kasus terburuknya ialah O(n²). Kasus ideal untuk masalah sorting ialah O(n), tetapi ini tidak mungkin terjadi pada average case. Sequential Sort, yang menaksir elemen dari list dari operasi perbandingan indeks abstrak, yang membutuhkan paling kurang perbandingan O(n log n) untuk paling banyak input.
Penukaran Kompleksitas Komputasi (untuk Algoritme "In Place")/
Penggunaan memori (dan menggunakan sumber daya komputer) khususnya, beberapa algoritme sorting ialah Algoritme In Place. Dengan sorting in place membutuhkan hanya O(1) memori lebih tinggi dari item yang sedang diurut; kadang-kadang memori tambahan O(log(n)) dianggap "in place"
Rekursif. Beberapa algoritme ada yang rekursif dan ada pula yang tidak, sedangkan beberapa yang lain bisa menjalankan keduanya sekaligus (contoh: merge sort).
Stabilitas: menjaga urutan relatif dari rekord dengan indeks sama (contoh: nilai).
Apakah dia merupakan Sorting Pembanding atau tidak. Sorting pembanding memeriksa data dengan hanya membandingkan dua elemen dengan operator pembanding.
Metode Umum: memasukkan, menukar, memilih, menggabungkan, dll. Sorting Penukaran mencangkup bubble sort dan quicksort. Sorting Seleksi mencangkup shaker sort dan heapsort.
Penyesuaian: Apakah terdapat sorting yang belum terurut atau tidak dari inputannya, segalanya akan mempengaruhi waktu kalkulasinya. Algoritme yang mengambil cara ini sebagai caranya dikenal sebagai Adaptive.

Stabilitas

Algoritme pembanding yang stabil menjaga urutan relatif dari rekord dengan indeks yang sama. (Indeks merupakan porsi dari rekors yang menjadi basis dari penyortiran; yang mungkin ataupun tidak termasuk dalam rekord tersebut.) Jika seluruh indeks berbeda maka perbedaan ini tidak dibutuhkan. Tetapi jika terdapat indeks yang sama, maka algoritme sorting itu stabil walaupun terdapat dua rekord (misalkan R dan S) dengan indeks yang sama, dan R muncul sebelum S pada list aslinya, kemudian R akan selalu muncul sebelum S pada list yang terurut. Ketika elemen yang sama tak dapat dibedakan, seperti dengan integer, atau secara umumnya, setiap data dimana seluruh elemen ialah nilai, tingkat kestabilannya tidak dipermasalahkan. Walaupun, asumsikan bahwa setiap angka yang ganda diurutkan berdasarkan komponen pertama mereka:

(4, 2)  (3, 7)  (3, 1)  (5, 6)

Pada kasus ini, dua nilai yang berbeda itu bisa saja terjadi, yang pertama menjaga urutan relatif rekord dengan nilai yang sama, dan yang satunya lagi tidak.

(3, 7)  (3, 1)  (4, 2)  (5, 6)   (urutan terjaga)
(3, 1)  (3, 7)  (4, 2)  (5, 6)   (urutan berubah)

Algoritme Sorting yang tidak stabil bisa saja mengubah urutan relatif rekord dengan nilai yang sama, tetapi algoritme sorting yang stabil tidak. Algoritme sorting yang tak stabil dapat secara khusus diimplementasikan pada yang stabil. Satu cara melakukannya ialah dengan secara buatan memperluas perbandingan nilainya, jadi perbandingan di antara dua objek dengan nilai yang sama dipilih dengan menggunakan urutan dari keseluruhan urutan data asli sebagai pemutus ikatan. Oder yang teratur ini bagaimanapun, sering melibatkan Nilai Komputasional tambahan.

Urutan didasari pada nilai pertama, kedua, ketiga, dll. Nilai urutan dapat dilakukan dengan metode sorting manapun, mengambil seluruh nilai sorting pada cacatan perbandingan (dengan kata lain, menggunakan nilai urutan gabungan tunggal). Jika metode sortingnya stabil, maka juga mungkin untuk mengurutkan kelipatan item, setiap waktu dengan satu nilai urut. Pada kasus ini nilai butuh ditempatkan untuk meningkatkan prioritas.

Contoh: Gabungan dua nilai sorting seperti diatas, kemudian komponen pertama:

(4, 2)  (3, 7)  (3, 1)  (5, 6) (asli)

(3, 1)  (4, 2)  (5, 6)  (3, 7) (setelah diurutkan dengan komponen kedua)
(3, 1)  (3, 7)  (4, 2)  (5, 6) (setelah diurutkan dengan komponen pertama)

Dengan kata lain:

(3, 7)  (3, 1)  (4, 2)  (5, 6) (setelah diurutkan dengan komponen pertama)
(3, 1)  (4, 2)  (5, 6)  (3, 7) (setelah diurutkan dengan komponen kedua, 
                                pengurutan dengan komponen pertama terganggu).

Perbandingan Algortima

Pada tabel ini, n merupakan angka dari rekord yang akan diurut. Kolom "Average" dan "Worst" memberikan kompleksitas waktu pada setiap case, dengan asumsi panjang setiap nilai merupakan konstan, dan oleh karena segala perbandingannya, penukarannya, dan segala operasi yang dibutuhkan dapat diproses pada waktu konstan. "Memori" menunjukkan jumlah dari simpanan tambahan dibutuhkan yang digunakan oleh list ini sendiri. Segala Sorting Pembangding ini. Waktu kalkulasi dan memori dari algoritme dapat diukur menggunakan notasi beragam seperti theta, omega, Big-O, small-o, dll. Memori dan waktu kalkulasi dibawah dapat diaplikasikan pada semua dari 5 notasi dibawah.

Comparison sorts
Name	Best	Average	Worst	Memory	Stable	Method	Other notes
Quicksort	20 ${\mathcal {}}n\log n$	20 ${\mathcal {}}n\log n$	25 ${\mathcal {}}n^{2}$	05 ${\mathcal {}}\log n$	Depends	Partitioning	Quicksort is usually done in place with O(log(n)) stack space.^{[butuh rujukan]} Most implementations are unstable, as stable in-place partitioning is more complex. Naïve variants use an O(n) space array to store the partition.^{[butuh rujukan]}
Merge sort	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	15 Depends; worst case is ${\mathcal {}}n$	Yes	Merging	Highly parallelizable (up to O(log(n))) for processing large amounts of data.
In-place Merge sort	50 ${\mathcal {}}-$	50 ${\mathcal {}}-$	23 ${\mathcal {}}{n\left(\log n\right)^{2}}$	00 ${\mathcal {}}{1}$	Yes	Merging	Implemented in Standard Template Library (STL);^[2] can be implemented as a stable sort based on stable in-place merging.^[3]
Heapsort	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	00 ${\mathcal {}}{1}$	No	Selection
Insertion sort	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Yes	Insertion	O(n + d), where d is the number of inversions
Introsort	20 ${\mathcal {}}n\log n$	20 ${\mathcal {}}n\log n$	20 ${\mathcal {}}n\log n$	05 ${\mathcal {}}\log n$	No	Partitioning & Selection	Used in several STL implementations
Selection sort	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	No	Selection	Stable with O(n) extra space, for example using lists.^[4] Used to sort this table in Safari or other Webkit web browser.^[5]
Timsort	15 ${\mathcal {}}{n}$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	15 ${\mathcal {}}n$	Yes	Insertion & Merging	${\mathcal {}}{n}$ comparisons when the data is already sorted or reverse sorted.
Shell sort	15 ${\mathcal {}}n$	23 ${\mathcal {}}n(\log n)^{2}$ or ${\mathcal {}}n^{3/2}$	23 Depends on gap sequence; best known is ${\mathcal {}}n(\log n)^{2}$	00 ${\mathcal {}}1$	No	Insertion
Bubble sort	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Yes	Exchanging	Tiny code size
Binary tree sort	15 ${\mathcal {}}n$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	15 ${\mathcal {}}n$	Yes	Insertion	When using a self-balancing binary search tree
Cycle sort	50 —	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	No	Insertion	In-place with theoretically optimal number of writes
Library sort	50 —	20 ${\mathcal {}}{n\log n}$	25 ${\mathcal {}}n^{2}$	15 ${\mathcal {}}n$	Yes	Insertion
Patience sorting	50 —	50 —	20 ${\mathcal {}}n\log n$	15 ${\mathcal {}}n$	No	Insertion & Selection	Finds all the longest increasing subsequences within O(n log n)
Smoothsort	15 ${\mathcal {}}{n}$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	00 ${\mathcal {}}{1}$	No	Selection	An adaptive sort - ${\mathcal {}}{n}$ comparisons when the data is already sorted, and 0 swaps.
Strand sort	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	15 ${\mathcal {}}n$	Yes	Selection
Tournament sort	50 —	20 ${\mathcal {}}n\log n$	20 ${\mathcal {}}n\log n$			Selection
Cocktail sort	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Yes	Exchanging
Comb sort	15 ${\mathcal {}}n$	15 ${\mathcal {}}n\log n$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	No	Exchanging	Small code size
Gnome sort	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Yes	Exchanging	Tiny code size.
UnShuffle Sort^[6]	15 $kN$	25 $kN$	25 $kN$	00 In place for linked lists. N*sizeof(link) for array.	Can be made stable by appending the input order to the key.	Distribution and Merge	No exchanges are performed. Performance is independent of data size. The constant 'k' is proportional to the entropy in the input. K = 1 for ordered or ordered by reversed input so runtime is equivalent to checking the order O(N).
Franceschini's method^[7]	—	20 $n\log n$	20 $n\log n$	00 $1$	Yes	?
Block sort^[8]	15 $n$	25 $n\log n$	25 $n\log n$	00 $1$	Yes	Insertion & Merging	Combine a block-based O(n) in-place merge algorithm^[9] with a bottom-up merge sort. Turns into a full-speed merge sort if additional memory is optionally provided to it.
Bogosort	15 ${\mathcal {}}n$	45 ${\mathcal {}}n\cdot n!$	45 ${\mathcal {}}{n\cdot n!\to \infty }$	00 ${\mathcal {}}{1}$	No	Luck	Randomly permute the array and check if sorted.
^[10]	50 ${\mathcal {}}-$	20 ${\mathcal {}}n\log n$	20 ${\mathcal {}}{n\log n}$	00 ${\mathcal {}}{1}$	Yes

Catatan

^ Demuth, H. Electronic Data Sorting. PhD thesis, Stanford University, 1956.
^ http://www.sgi.com/tech/stl/stable_sort.html
^ http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381
^ http://www.algolist.net/Algorithms/Sorting/Selection_sort
^ http://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp
^ Kagel, Art (November 1985). "Unshuffle, Not Quite a Sort". Computer Language.
^ Franceschini, Gianni (1 June 2007). "Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves". Theory of Computing Systems. 40 (4): 327–353. doi:10.1007/s00224-006-1311-1.
^ "Public domain implementations of block sort for C, C++, and Java". Diakses tanggal 2014-04-02.
^ Kutzner, Arne; Kim, Pok-Son (2008). Ratio Based Stable In-Place Merging. Lecture Notes in Computer Science. 4978. Springer Berlin Heidelberg. hlm. 246–257. Diakses tanggal 2014-03-14.
^ http://www.springerlink.com/content/d7348168624070v7/^{[pranala nonaktif permanen]}

Pranala luar

Sorting Algorithm Animations - Graphical illustration of how different algorithms handle different kinds of data sets.
Sequential and parallel sorting algorithms Diarsipkan 2012-12-13 di Wayback Machine. - Explanations and analyses of many sorting algorithms.
Dictionary of Algorithms, Data Structures, and Problems - Dictionary of algorithms, techniques, common functions, and problems.
Slightly Skeptical View on Sorting Algorithms Discusses several classic algorithms and promotes alternatives to the quicksort algorithm.

[1] Demuth, H. Electronic Data Sorting. PhD thesis, Stanford University, 1956.

[2] ttp://www.sgi.com/tech/stl/stable_sort.html

[3] ttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.8381

[4] ttp://www.algolist.net/Algorithms/Sorting/Selection_sort

[5] ttp://svn.webkit.org/repository/webkit/trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp

[6] Kagel, Art (November 1985). "Unshuffle, Not Quite a Sort". Computer Language.

[7] Franceschini, Gianni (1 June 2007). "Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves". Theory of Computing Systems. 40 (4): 327–353. doi:10.1007/s00224-006-1311-1.

[wikisort-8] "Public domain implementations of block sort for C, C++, and Java". Diakses tanggal 2014-04-02.

[9] Kutzner, Arne; Kim, Pok-Son (2008). Ratio Based Stable In-Place Merging. Lecture Notes in Computer Science. 4978. Springer Berlin Heidelberg. hlm. 246–257. Diakses tanggal 2014-03-14.

[10] ttp://www.springerlink.com/content/d7348168624070v7/^{[pranala nonaktif permanen]}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]