Algoritma Sorting
Dalam
matematika dan komputasi, algoritma merupakan kumpulan perintah untuk
menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara
bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan
catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi
sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua
kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik.
Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan
keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
Desain dan
analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang
mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan
masalah, terlepas dari implementasi algoritma tersebut. Dalam cabang disiplin
ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau
bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada
suatu masalah dengan kriteria yang sama.
Kompleksitas
dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang
dibutuhkan algoritma tersebut untuk menyelesaikan masalah. Secara informal,
algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat
memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu
lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
Sedangkan sorting
adalah sebuah proses merangkai benda dalam urutan tertentu dan/atau dalam
himpunan yang berbeda, dan oleh karena itu dia memiliki dua arti umum yang
berbeda:
- pengurutan: merangkai benda yang sejenis, sekelas, dll, dalam urutan yang teratur.
- kategorisasi: pengelompokan dan pemberian label kepada benda dengan sifat yang serupa.
algoritma sorting
terdiri dari beberapa algoritma seperti Bubble sort, Quick sort, Selection
Sort, Insertion Sort, dan Merge Sort yang dimana setiap jenis sorting
ini memiliki perbedaan satu sama lainnya. berikut ini merupakan pembahasan umum
mengenai jenis-jenis atau algoritma sorting yang telah dijelaskan diatas
:
Bubble Sort
Bubble Sort merupakan cara pengurutan
yangsederhana. Konsep dari ide dasarnya adalah seperti“gelembung air” untuk
elemen struktur data yangsemestinya berada pada posisi awal. Cara
kerjanyaadalah dengan berulang-ulang melakukan traversal (proses looping)
terhadap elemen-elemen struktur datayang belum diurutkan. Di dalam traversal
tersebut,nilai dari dua elemen struktur data dibandingkan. Jikaternyata
urutannya tidak sesuai dengan “pesanan”,maka dilakukan pertukaran (swap).
Algoritma sortingini disebut juga dengan comparison sort dikarenakanhanya
mengandalkan perbandingan nilai elemen untukmengoperasikan elemennya.
Algoritma
Bubble Sort
Algoritma
bubble sort dapat diringkas sebagaiberikut, jika N adalah panjang elemen
struktur data, dengan elemen-elemennya adalah T1, T2, T3, …, TN-1,TN, maka:
- Lakukan traversal untuk membandingkan dua elemen berdekatan. Traversal ini dilakukan dari belakang.
- Jika elemen pada TN-1 > TN , maka lakukan pertukaran (swap). Jika tidak, lanjutkan ke proses traversal berikutnya sampai bertemu dengan bagian struktur data yang telah diurutkan.
- Ulangi langkah di atas untuk struktur data yang tersisa.
Selection
Sort
Algoritma
sorting sederhana yang lain adalahSelection Sort. Ide dasarnya adalah melakukan
beberapa kali pass untuk melakukan penyeleksianelemen struktur data. Untuk
sorting ascending(menaik), elemen yang paling kecil di antara elemenelemenyang
belum urut, disimpan indeksnya,kemudian dilakukan pertukaran nilai elemen
denganindeks yang disimpan tersebut dengan elemen yangpaling depan yang belum
urut. Sebaliknya, untuksorting descending (menurun), elemen yang paling. besar
yang disimpan indeksnya kemudian ditukar.
Algoritma
Selection Sort
Algoritma
selection sort dapat dirangkum sebagaiberikut:
- Temukan nilai yang paling minimum (atau sesuaikeinginan) di dalam struktur data. Jika ascending, maka yang harus ditemukan adalah nilai yang paling minimum. Jika descending, maka temukan nilai yang paling maksimum.
- Tukar nilai tersebut dengan nilai pada posisipertama di bagian struktur data yang belum diurutkan.
- Ulangi langkah di atas untuk bagian struktur datayang tersisa.
Insertion
Sort
Cara kerja
insertion sort sebagaimana namanya.Pertama-tama, dilakukan iterasi, dimana di
setiap iterasi insertion sort memindahkan nilai elemen,kemudian menyisipkannya
berulang-ulang sampai ketempat yang tepat. Begitu seterusnya dilakukan.
Dariproses iterasi, seperti biasa, terbentuklah bagian yang telah di-sorting
dan bagian yang belum di-sorting.
Algoritma
Insertion Sort
Algoritma
Insertion Sort dapat dirangkum sebagai berikut:
- Simpan nilai Ti kedalam variabel sementara, dengan i = 1.
- Bandingkan nilainya dengan elemen sebelumnya.
- Jika elemen sebelumnya (Ti-1) lebih besar nilainya daripada Ti, maka tindih nilai Ti dengan nilai Ti-1 tersebut. Decrement i (kurangi nilainya dengan 1).
- Lakukan terus poin ke-tiga, sampai Ti-1 ≤ Ti.
- Jika Ti-1 ≤ Ti terpenuhi, tindih nilai di Ti dengan variabel sementara yang disimpan sebelumnya.
- Ulangi langkah dari poin 1 di atas dengan i di-increment (ditambah satu).
Merge Sort
Algoritma Merge
Sort ditemukan oleh John vonNeumann di tahun 1945. Merge Sort termasuk
paradigma algoritma divide and conquer (kurang lebih berarti: bagi dan atasi).
Hal ini dikarenakan algoritma ini melakukan pembagian struktur data sebelum
kemudian dioperasi satu per satu. Intinya, algoritma ini menggunakan dua ide
utama sebagai berikut,
- Sebuah list yang kecil membutuhkan langkah yang lebih sedikit untuk pengurutan daripada sebuah list yang besar.
- Untuk membentuk sebuah list terurut dari duabuah list terurut membutuhkan langkah yangl ebih sedikit daripada membentuk sebuah list terurut dari dua buah list tak terurut. Contoh:hanya diperlukan satu kali traversal untuk masing-masing list jika keduanya sudahterurut.
Algoritma
Merge Sort
Algoritma
Merge Sort sederhananya, dapat ditulis berikut:
- Bagi list yang tak terurut menjadi dua sama panjang atau salah satunya lebih panjang satu elemen.
- Bagi masing-masing dari 2 sub-list secara rekursif sampai didapatkan list dengan ukuran 1.
- Gabung 2 sublist kembali menjadi satu list terurut.
Quick Sort
Quick Sort adalah algoritma sorting yang
terkenal yang dirancang oleh C.A.R. Hoare pada tahun 1960 ketika bekerja untuk
perusahaan manufaktur komputer saintifik kecil, Elliott Brothers. Algoritma ini
rekursif, dan termasuk paradigma algoritma divide and conquer.
Algoritma
Quick Sort
Algoritma
ini terdiri dari 4 langkah utama:
- Jika struktur data terdiri dari 1 atau 0 elemen yang harus diurutkan, kembalikan struktur data itu apa adanya.
- Ambil sebuah elemen yang akan digunakansebagai pivot point (poin poros). (Biasanya elemen yang paling kiri.)
- Bagi struktur data menjadi dua bagian – satu dengan elemen-elemen yang lebih besar daripada pivot point, dan yang lainnya dengan elemen-elemen yang lebih kecil dari pada pivot point.
- Ulangi algoritma secara rekursif terhadap kedua paruh struktur data.
KESIMPULAN
Algoritma
yang mudah dalam hal implementasi adalah Bubble Sort, Selection Sort, dan
Insertion Sort. Ketiganya memiliki kompleksitas O(n2). Di antara algoritma ini,
yang paling effisien adalah Insertion Sort. Algoritma yang lebih mangkus
adalah MergeSort dan Quick Sort dengan kompleksitasnya adalah O(n log n).
Adapun yang paling mangkus dari lima algoritma ini adalah Quick Sort.
0 comments:
Post a Comment