Hi all
the people of the world!
Welcome back again to my blog, thanks for opening this post.
Kali ini gw akan membahas masalah Sort(Pengurutan) dalam data? Jadi, Apasih
yang dimaksud dengan SORT itu? Yup, seperti namanya Sort/Sorting merupakan
suatu proses mengatur susunan data-data menurut syarat tertentu. Meskipun
pengurutan ini sepertinya hanya sebuah masalah klasik dalam
keinformatikaan,namun perannya tidak dapat dipisahkan terutama dalam pengolahan
data. Suatu pengolahan data biasanya akan lebih efisien jika datanya telah
terurut,seperti Binary Search misalnya.
Mengingat pentingnya pengurutan dalam penggunaannya dalam hal keinnformatikaan,
maka perlu diketahui algoritma mana yang sebenarnya paling efisien untuk dipakai.
Meskipun suatu algoritma pengurutan mempunyai kelebihan dan keterbatasan
masing-masing, kompleksitas dan keefisiensiannya tetap harusdipertimbangkan.
Dalam ilmu komputer, algoritma pengurutan (sorting adalah):
1. algoritma yang meletakkan elemen-elemen suatu kumpulan
data dalam urutan tertentu atau
2. proses pengurutan data yang sebelumnya disusun secara acak
sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.
Dan berikut ini adalah pengertian dari beragam sorting..
A. Bubble Sort
Metode pengurutan gelembung (Bubble Sort)
diinspirasikan oleh gelembung sabun yang berada dipermukaan air. Karena
berat jenis gelembung sabun lebih ringan daripada berat jenis air, maka
gelembung sabun selalu terapung ke atas permukaan. Prinsip di atas dipakai pada
pengurutan gelembung.
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.
B. Insertion Sort
Metode penyisipan (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 denganmembandingkan
elemen-elemen data yang akan diurutkan, algoritma ini termasuk pula dalam comparison-based
sort.
C. Merge Sort
Merge sort adalah algoritma yang berdasarkan stategi
devide-and-conquer. Algoritmaini terdiri 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.
- Devide membagi masalah menjadi beberapa submasalah yang memiliki kemiripan dengan masalah semula namun berukuran lebih kecil.
- Conquer memecahkan masing-masing submasalah.
- Combine menggabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.
D. Quick Sort
Quick sort adalah metode pengurutan data yang
dikemukakan pertama kali oleh C. AR Hoare pada tahun 1962. Metode ini
menggunakan strategi "pecah-pecah" dengan mekanisme :
Larik L[p..r] (Indeks terkecil adalah p dan terbesar
adalah r) disusun ulang 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.
E. Selection Sort
Metode seleksi merupakan metode pengurutan dengan cara
mencari data yang terkecil kemudian menukarkannya dengan data yang digunakan
sebagai acuan atau sering dinamakan pivot.
Langkah-langkah melakukan selection sort :
- Mencari data terkecil dari elemen pertama (Data[0]) sampai elemen terakhir (Data[n-1]). Kemudian data terkecil ditukar posisinya dengan Data[0].
- Mencari data terkecil dari elemen kedua (Data[1]) sampai elemen terakhir (Data[n-1]). Kemudian data terkecil ditukar posisinya dengan Data[1], dan seterusnya.
F. 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.
Untuk Melakukan perbandingan kecepatan/analisa beragam
sorting diatas saya menggunakan laptop dengan spesifikasi..
Dengan menggunakan program Python IDLE versi Python..
Berikut ini adalah grafik dari data hasil percobaan tersebut.
Dari grafik tersebut dapat disimpulkan bahwa didapatkan didapatkan dengan
iterasi sebanyak 10 kali dengan menggunakan lima macam jenis sorting yaituQuick sort, Merge sort, Shell sort, Selection Sort, Bubble
sort, dan Insertion sort. Grafik serta tabel diatas menunjukan bahwa Quick Sort memiliki
kecepatan paling tinggi dalam mensorting 10.000 d ata dengan kecepatan rata-rata 2.2 detik . Pada bubble sort memiliki rata-rata
kecepatan dalam mensorting adalah 15.24 detik,
insertion sort memiliki rata-rata
kecepatan dalam mensorting adalah 8 detik,
merge sort memiliki rata-rata
kecepatan dalam mensorting adalah 2.3detik,
quick sort memiliki rata-rata
kecepatan dalam mensorting adalah 2.2 detik, selection
sort memiliki rata-rata kecepatan dalam mensorting adalah 7.63 detik. sedangkan
shell sort memiliki rata-rata kecepatan dalam mensorting adalah 2.4 detik.
