Defenisi
Sorting bisa didefinisikan sebagai suatu proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu. Pada umumnya terdapat dua jenis pengurutan:
- Ascending (Naik).
- Descending (Turun).
Metode Pengurutan Data
- Pengurutanberdasarkanperbandingan(comparison-based sorting)
- Bubble sort, exchange sort
- Pengurutanberdasarkanprioritas(priority queue sorting method)
- Selection sort, heap sort
- Pengurutanberdasarkanpenyisipandanpenjagaanterurut(insert and keep sorted method)
- Insertion sort, tree sort
- Pengurutanberdasarkanpembagiandanpenguasaan(devideand conquer method)
- Quick sort, merge sort
- Pengurutanberkurangmenurun(diminishing increment sort method)
- Shell sort
1. Bubble Sort
Pengertian :
Bubble sort (metode gelembung) adalah metode / algoritma pengurutan dengan dengan cara melakukan penukaran data dengan tepat disebelahnya secara terus menerus sampai bisa dipastikan dalam satu iterasi tertentu tidak ada lagi perubahan. Jika tidak ada perubahan berarti data sudah terurut. Disebut pengurutan gelembung karena masing-masing kunci akan dengan lambat menggelembung ke posisinya yang tepat.
2. Selection Sort
Pengertian :
Algoritma selection sort adalah mencari elemen yang tepat untuk diletakkan di posisi yang telah diketahui, dan meletakkannya di posisi tersebut setelah data tersebut ditemukan. Selection Sort membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar.
3. Insertion Sort
Pengertian :
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama), dan yang telah diurutkan (meja kedua). Elemen pertama yang diambil dari bagian array yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang belum diurutkan.
4. Heap Sort
Pengertian :
Heapsort merupakan salah satu bentuk dari selection sort yang memiliki kompleksitas algorima O(n log(n)) yang menggunakan struktur data heap. Algoritma ini bekerja dengan menentukan elemen terbesar (atau terkecil) dari sebuah daftar elemen, dan diletakkan pada akhir (atau awal) dari daftar tersebut. Heap sort menyelesaikan sebuah pengurutan menggunakan struktur data yang disebut heap. Heap merupakan sebuah pohon biner hampir lengkap dimana isi dari simpul ayah selalu lebih besar dari isi simpul anak-anaknya sehingga simpul akar selalu merupakan elemen terbesar.
5. Shell Sort
Pengertian :
Algoritma ini memiliki kesamaan cara kerja dengan insertion sort, yaitu membandingkan elemen-elemen dengan jarak tertentu. Insertion sort membandingkan elemen–elemen data yang berdekatan (berjarak satu posisi), sedangkan shell sort membandingkan elemen berjarak tertentu, misalnya elemen yang berjarak 5 posisi atau 2 posisi dan pada akhirnya akan selesai pada pengurutan data yang berjarak 1 posisi. Namun nilai ini haruslah dicari sedemikian rupa agar tidak menulangi atau merusak hasil sorting sebelumnya.
6. Quick Sort
Pengertian :
Pengurutan ini berdasar pada prinsip devide and conquer. Devide adalah suatu langkah memilah masalah menjadi sub – masalah dalam proses rekursi, sedangkan conquer adalah proses menyelesaikan sub masalah tersebut, kemudian dilakukan pendekatan terhadap masalah utama. Pada dasarnya prinsip kerjanya adalah membagi atau memartisi sekumpulan data menjadi dua bagian sedemikian rupa sehingga elemen ke-i berada tepat pada posisisnya, dimana semua elemen yang nilainya lebih kecil daripada elemen ke-i akan terletak disebelah kirinya, sedangkan yang mempunyai nilai lebih besar berada disebelah kanannya. Algoritma ini memiliki kompleksitas O(n log n).
7. Merge Sort
Pengertian :
Merge sort merupakan salah satu teknik sorting yang menurutkan suatu data dengan cara penggabungan. Merge sort juga menggunakan proses divide and conquer pada rekursi. Berikut adalah langkah kerja merge sort :
Devide : Memilah elemen – elemen dari data menjadi dua bagian.
Conquer : Menyelesaikan setiap bagian dengan memanggil prosedur merge sort secara rekursif.
Kombinasi : Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan.
Proses rekursi akan berhenti jika telah mencapai lemen dasar, atau artinya jika bagian yang diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah sesuai rangkaian.
8. Radix Sort
Pengertian :
Radix sort adalah salah satu algoritma sorting yang dilakukan tanpa melakukan perbandingan antardata yang dijadikan sebagai input. Makna harfiah Radix dapat diartikan sebagai posisi dalam angka. Dalam system decimal, radix adalah digit dalam angka decimal. Misalkan angka 37 mempunyai nilai radix 3 dan 7. Berdasarkan urutan pemrosesan radix-nya, ada 2 macam Radix sort. Pertama adalah LSD (Least Significant Digit) yaitu proses dimulai dari radix yang paling tidak signifikan(digit yang paling kanan). Kedua adalah MSD (Most Significant Digit), yaitu proses dimulai dari radix yang paling signifikan (digit yang paling kiri).
Contoh Metode Sorting
- Bubble Sort
Tahap 120 10 15 5 3 2
20 10 15 5 2 3
20 10 15 2 5 3
20 10 2 15 5 3
20 10 2 15 5 320 2 10 15 5 3
2 20 10 15 5 3Tahap 22 20 10 15 3 5
2 20 10 15 3 5
2 20 10 3 15 5
2 20 3 10 15 5
2 3 20 10 15 5Tahap 32 3 20 10 15 5
2 3 20 10 5 15
2 3 20 5 10 15
2 3 5 20 10 15Tahap 42 3 5 20 10 15
2 3 5 20 15 10
2 3 5 15 22 10Tahap 52 3 5 15 20 10
2 3 5 15 10 20
- Selection sort
Awal
10
|
8
|
15
|
5
|
2
|
0
|
1
|
2
|
3
|
4
|
Tahap 1
I =2 , Lok =4 :
10
|
8
|
2
|
5
|
15
|
0
|
1
|
2
|
3
|
4
|
Tahap 2 :
I = 0, Lok 3
5
|
8
|
2
|
10
|
15
|
0
|
1
|
2
|
3
|
4
|
Tahap 3:
I = 1, Lok = 2
5
|
2
|
8
|
10
|
15
|
0
|
1
|
2
|
3
|
4
|
Tahap 4 :
I = 0, Lok = 1
2
|
5
|
8
|
10
|
15
|
0
|
1
|
2
|
3
|
4
|
Referensi :
0 komentar:
Posting Komentar