Pada Ilmu Komputerisasi, Algoritma Sorting merupakan algoritma yang menempatkan atau menyisipkan elemen list pada urutan tertentu. Maksud dari urutan tertentu itu adalah urutan yang paling sering digunakan , urutan numerikal dan urutan lexicographical. Sorting sangat dibutuhkan untuk mengoptimalkan penggunaan dari algoritma lain seperti untuk pencarian dan penggabungan yang membutuhkan list terurut untuk menjalankan secara sempurna, yang juga sering digunakan untuk Canonicalisisasi data dan menghasilkan output yang dapat dibaca manusia.
Sementara itu output juga 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 masalah pengurutan ini telah banyak menarik penelitian yang serius,yang dikarenakan kerumitan dari penyelesaian secara efisien yang mudah, dan dengan ilmu penyampaiannya yang kita mengerti.
Dalam Algoritma sorting juga terdapat beberapa macam yaitu
1. Quicksort
Quick Sort adalah metode pengurutan data yang dikemukan pertama kali oleh C.AR Hoare pada tahun 1962. Metode ini menggunakan strategi “pecah-pecah” dengan mekanisme seperti berikut : Larik L[p..r] (dengan indeks terkecil adalah p dan indeks terbesar yaitu r) disusun ulang (dipartisi) menjadi dua buah larik A[p..q] dan A[q+1..r] sehingga setiap elemen dalam A[q+1..r]. Selanjutnya kedua larik tersebut diurutkan secara rekursif. Dengan sendirinya kombinasi kedua larik tersebut membentuk larik dengan data yang telah urut.
2. Merge sort,
MergeSort adalah algoritma yang berdasarkan strategi divide-and-conquer. Algoritma ini tediri dari dua bagian utama, yaitu bagian pembagian list menjadi sublist-sublist yang lebih kecil dan bagian sort (pengurutan) dan merge (penggabungan) pada sublist-sublist tersebut.
1) Divide: membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
2) Conquer: memecahkan (menyelesaikan) masing-masing submasalah (secara rekursif), dan
3) Combine: mengabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.
3. Heapsort,
Metode heap sort adalah metode dari pengembangan tree. Heap sort memiliki kecepatan O(NlogN). Heap sort melakukan suatu pengurutan menggunakan suatu struktur data yang di sebut heap. Heap memiliki kompleksitas yang besar dalam pembuatan kodenya, tetapi heap sort mampu mengurutkan data-data yang sangat banyak dengan waktu yang cepat. Dalam sorting biasanya mempunyai sebuah aturan, berikut adalah aturan dari heap sort :
1. Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya.
2. Heap dlm kondisi terurut apabila left child <> parent.
3. Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.
4. Bila menghapus heap dgn mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap
4. RADIX SORT
Radix Sort adalah metode sorting tanpa pembandingan dengan kata lain, sorting Non-Comparasion sort dimana dalam prosesnya tidak melakukan perbandingan antar data. Secara umum yang proses yang dilakukan dalam metode ini adalah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu dan dalam tiap kategorinya dilakukan pengklasifikasian lagi dan seterusnya sesuai dengan kebutuhan. Dan kemudian subkategori-subkategori tersebut digabungkan kembali, yang secara dilakukan hanya dengan metode sederhana concatenation.
Apa itu Radix Sort??? Radix Sort merupakan algoritma pengurutan yang ajaib yang mana mengatur pengurutan nilainya tanpa melakukan beberapa perbandingan pada data yang dimasukkan. Kata radix bermakna harafiah posisi dalam angka [1]. Di mana sederhananya, dalam representasi desimal, radix adalah digitnya. Dalam implementasinya, Radix Sort merupakan algoritma pengurutan yang cepat, mudah, dan sangat efektif. Namun banyak orang yang berpikir bahwa algoritma ini memiliki banyak batasan di mana untuk kasus-kasus tertentu tidak dapat dilakukan dengan algoritma ini, seperti pengurutan bilangan pecahan dan bilangan negatif,
Berdasarkan urutan pemrosesan radixnya, Radix Sort terbagi 2 macam, yaitu: LSD (Least Significant Digit), di mana pemrosesan dimulai dari radix yang paling tidak signifikan. dan MSD (Most Significant Digit), di mana pemrosesan dimulai dari radix yang paling signifikan.
Proses dasar Radix Sort adalah mengkategorikan data-data menjadi subkumpulan-subkumpulan data sesuai dengan nilai radix-nya, mengkonkatenasinya, kemudian mengkategorikannya kembali berdasar nilai radix lainnya.
Insertion sort adalah sebuah algoritma pengurutan yang membandingkan dua elemen data pertama, mengurutkannya, kemudian mengecek elemen data berikutnya satu persatu dan membandingkannya dengan elemen data yang telah diurutkan. Karena algoritma ini bekerja dengan membandingkan elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based sort.
Ide dasar dari algoritma Insertion Sort ini adalah mencari tempat yang “tepat” untuk setiap elemen array, dengan cara sequential search. Proses ini kemudian menyisipkan sebuah elemen array yang diproses ke tempatnya yang seharusnya. Proses dilakukan sebanyak N-1 tahapan (dalam sortingdisebut sebagai “pass“), dengan indeks dimulai dari 0.
Proses pengurutan dengan menggunakan algoritma Insertion Sort dilakukan dengan cara membandingkan data ke-i (dimana i dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai dengan posisi yang seharusnya.
Algoritma Selection sort memilih elemen maksimum/minimum array, lalu menempatkan elemen maksimum/minimum itu pada awal atau akhir array (tergantung pada urutannya ascending/descending). Selanjutnya elemen tersebut tidak disertakan pada proses selanjutnya. Karena setiap kali selection sort harus membandingkan elemen-elemen data, algoritma ini termasuk dalam comparison-based sorting.
Seperti pada algoritma Bubble Sort, proses memilih nilai maksimum /minimum dilakukan pada setiap pass. Jika array berukuran N, maka jumlah pass adalah N-1.
Terdapat dua pendekatan dalam metode pengurutan dengan Selection Sort :
1. Algoritma pengurutan maksimum (maximum selection sort), yaitu memilih elemen maksimum sebagai basis pengurutan.
2. Algoritma pengurutan minimum (minimum selection sort), yaitu memilih elemen minimum sebagai basis pengurutan
Contoh :
procedure Bubble(var Arr: array of string); var I: integer;
Ada_Tukar: boolean;
begin
repeat
Ada_Tukar:= false;
for I:= Low(Arr) to High(Arr)-1 do begin
if Arr[I] > Arr[I+1] then begin
Tukar(Arr[I], Arr[I+1]);
Ada_Tukar:= true;
end;
end;
until Ada_Tukar = false;
end;
7. Shell sort
Metode ini disebut juga dengan metode pertambahan menurun (diminishing increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan
8. Bubble sort
Bubble sort adalah proses pengurutan sederhana yang bekerja dengan cara berulang kali membandingkan dua elemen data pada suatu saat dan menukar elemen data yang urutannya salah. Ide dari Bubble sort adalah gelembung air yang akan “mengapung” untuk table yang terurut menaik (ascending). Elemen bernilai kecil akan “diapungkan” (ke indeks terkecil), artinya diangkat ke “atas”(indeks terkecil) melalui pertukaran. Karena algoritma ini melakukan pengurutan dengan cara membandingkan elemen-elemen data satu sama lain, maka bubble sort termasuk ke dalam jenis algoritma comparison-based sorting.
Kelebihan Bubble Sort
- Metode Buble Sort merupakan metode yang paling simple
- Metode Buble Sort mudah dipahami algoritmanya
Kelemahan Bubble Sort
Meskipun simpel metode Bubble sort merupakan metode pengurutanyang paling tidak efisien. Kelemahan buble sort adalah pada saat mengurutkan data yang sangat besar akan mengalami kelambatan luar biasa, atau dengan kata lain kinerja memburuk cukup signifikan ketika data yang diolah jika data cukup banyak. Kelemahan lain adalah jumlah pengulangan akan tetap sama jumlahnya walaupun data sesungguhnya sudah cukup terurut. Hal ini disebabkan setiap data dibandingkan dengan setiap data yang lain untuk menentukan posisinya.
Disajikan contoh cara kerjanya, untuk 5 buah data yaitu 4, 5, 1, 3, 2. Pengurutan dimulai dari lokasi pertama (I adalah 1), dan dibandingkan dengan lokasi sebelahnya (I+1 adalah 2). Karena data 4 dan 5 sudah berada pada urutan yang cocok, maka tidak terjadi pertukaran. Kemudian dicek data lokasi berikutnya (I adalah 2) dengan lokasi sebelahnya (I+1 adalah 3), ternyata data 5 dan 1 tidak cocok, maka ditukar. Lokasi berikutnya (I adalah 3) dibandingkan
Perulangan Pertama (First Pass)
4 5 1 3 2 (cocok)
4 5 1 3 2 (tukar 5 dan 1) 4 1 5 3 2
4 1 5 3 2 (tukar 5 dan 3) 4 1 3 5 2
4 1 3 5 2 (tukar 5 dan 2) 4 1 3 2 5
Perulangan Kedua (Second Pass)
4 1 3 2 5 (tukar 4 dan 1) 1 4 3 2 5
1 4 3 2 5 (tukar 4 dan 3) 1 3 4 2 5
1 3 4 2 5 (tukar 4 dan 2) 1 3 2 4 5
1 3 2 4 5 (cocok)
Perulangan Ketiga (Third Pass)
1 3 2 4 5 (cocok)
1 3 2 4 5 (tukar 3 dan 2) 1 2 3 4 5
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)
Perulangan Keempat (Fourth Pass)
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)
dengan lokasi sebelahnya (I+1 adalah 4), ternyata data 5 dan 3, tidak cocok lagi, maka ditukar lagi. Demikian seterusnya, dikerjakan sampai dipastikan bahwa semua data ada pada lokasi yang cocok, yang dilakukan dengan carasudah tidak ada lagi pertukaran yang dilakukan. Berikut adalah proses perubahan data untuk contoh data 4, 5, 1, 3, 2 tersebut:
Pada waktu Perulangan Keempat, sudah tidak terjadi pertukaran lagi (semua sudah cocok), maka sudah dapat dipastikan bahwa semua data sudah berada di lokasi yang tepat.
Berikut adalah implementasi dari Algoritma Bubble Sort dengan memakai prosedur. Parameter data berjenis referensi ke tipe data array of string:
procedure Bubble(var Arr: array of string);
var I: integer;
Ada_Tukar: boolean;
begin
repeat
Ada_Tukar:= false;
for I:= Low(Arr) to High(Arr)-1 do begin
if Arr[I] > Arr[I+1] then begin
Tukar(Arr[I], Arr[I+1]);
Ada_Tukar:= true;
end;
end;
until Ada_Tukar = false;
end;
Untuk contohnya kita memilih bubble sort, bubble sort ini pertama kali ditemukan pada tahun 1956. Meskipun sangat banyak yang memperkirakan masalah penggunaan bubble sort ini telah selesai, selain bubble sort juga banyak algoritma sorting baru yang diketemukan sampai sekarang (contoh: Library Sort yang baru dipublikasikan pertama sekali pada tahun 2006). Algoritma sorting sangat umum pada setiap kelas pengenalan bidang Ilmu Komputer, dimana banyaknya algoritma untuk masalah ini menyediakan pengenalan awal mengenai banyaknya konsep algoritma inti, seperti Notasi Big O, Algoritma Pembagi, Struktur Data, Algoritma Acak, Analisa Best, Worst, Average Case, Running Time Calculation, dan Batas Atas dan Bawah.
Sorting juga sering digunakan pada Ilmu Komputer yang diklasifikasikan dengan:
· Kompleksitas Komputasi (Average, Best, Worst case) perbandingan elemen dengan besar list(n). Untuk beberapa Algoritma sorting kasus yang paling baiknya ialah O(n log n) dan kasus terburuknya ialah O(n2). 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 Algoritma "In Place")/
· Penggunaan memori (dan menggunakan sumber daya komputer) khususnya, beberapa algoritma sorting ialah Algoritma 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 algoritma 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. Algoritma yang mengambil cara ini sebagai caranya dikenal sebagai Adaptive.
Algoritma adalah pembanding yang stabi untukl menjaga urutan relatif dari rekord dengan indeks yang sama. Jika seluruh indeks berbeda maka perbedaan ini tidak dibutuhkan. Tetapi jika terdapat indeks yang sama, maka algoritma sorting itu stabil walaupun terdapat dua rekord (misalkan R dan S) dengan indeks yang sama, dan R muncul sebelum S pada list aslinya, maka R yang akan selalu muncul sebelum S sama halnya seperti integer yang semua bilangannya tidak mempengaruhinya.
Contoh1:
(4, 2) (3, 7) (3, 1) (5, 6)
Didalam contoh pertama ini , ada dua nilai yang berbeda itu bisa saja terjadi,karena saat yang pertama menjaga urutan relatif rekord dengan nilai yang sama, maka yang satunya lagi tidak.
Seperti ini :
(3, 7) (3, 1) (4, 2) (5, 6) (urutan terjaga)
(3, 1) (3, 7) (4, 2) (5, 6) (urutan berubah)
Algoritma Sorting juga dapat tidak stabil apabila urutan relatif rekord dengan nilai yang sama,. Algoritma sorting yang tidak stabil maka secara khusus dapat diimplementasikan kepada yang stabil. Salah satu cara melakukannya dengan secara buatan yaitu 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.
Urutan ini akan 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 ,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).
Tidak ada komentar:
Posting Komentar