Algoritma Sorting

Algoritma Penyusunan kembali

Dalam Ilmu Komputer, Algoritme Sorting merupakan algoritme yang menempatkan elemen list pada urutan tertentu. Urutan yang paling sering digunakan ialah urutan numerikal dan urutan lexicographical(perkamusan). Sorting yang efisien sangat dibutuhkan untuk mengoptimisasi penggunaan dari algoritme lain seperti pencarian dan penggabungan yang membutuhkan list terurut untuk berjalan dengan sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia. Untuk lebih lanjutnya, output harus melengkapi dua syarat ini:

1. Output merupakan urutan yang tidak menurut (nondecreasing) (setiap elemen tidak lebih kecil dari elemen sebelumnya menurut dari urutan keseluruhan yang diinginkan.
2. 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. Walaupun banyak yang memperkirakan masalahnya telah terselesaikan, banyak algoritme sorting baru yang masih ditemukan samap sekarang (sebagai contoh, Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritme sorting 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, Analisa Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.

Klasifikasi

Algoritme sorting 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 sorting; 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.