" Sorting "

 

Macam-macam Sorting :

1. Buble Sort :
Merupakan algoritma pengurutan paling tua dengan metode pengurutan paling sederhana. Pengurutan yang dilakukan dengan membandingkan masing-masing item dalam suatu list secara berpasangan, menukar item jika diperlukan, dan mengulaginya sampai akhir list secara berurutan, sehingga tidak ada lagi item yang dapat ditukar.

Ada Beberapa Yang Perlu Diketahui Mengenai Bubble Sort :

• Metode Sorting Termudah

•  Diberi Nama “Bubble” Karena Proses Pengurutan Secara Berangsur-Angsur Bergerak/Berpindah Ke Posisinya Yang Tepat, Seperti Gelembung Yang Keluar Dari Sebuah Gelas Bersoda.

• Bubble Sort Mengurutkan Data Dengan Cara Membandingkan Elemen Sekarang Dengan Elemen Berikutnya.

• Jika Elemen Sekarang Lebih Besar Dari Elemen Berikutnya Maka Kedua Elemen Tersebut Ditukar, Jika Pengurutan Ascending.

• Jika Elemen Sekarang Lebih Kecil Dari Elemen Berikutnya, Maka Kedua Elemen Tersebut Ditukar, Jika Pengurutan Descending.

• Algoritma Ini Seolah-Olah Menggeser Satu Per Satu Elemen Dari Kanan Ke Kiri Atau Kiri Ke Kanan, Tergantung Jenis Pengurutannya.

• Ketika Satu Proses Telah Selesai, Maka Bubble Sort Akan Mengulangi Proses, Demikian Seterusnya.

• Kapan Berhentinya? Bubble Sort Berhenti Jika Seluruh Array Telah Diperiksa Dan Tidak Ada Pertukaran Lagi Yang Bisa Dilakukan, Serta Tercapai Perurutan Yang Telah Diinginkan.

Kelebihan Bubble Sort :

•  Metode Buble Sort Merupakan Metode Yang Paling Simpel

• Metode Buble Sort Mudah Dipahami Algoritmanya

• Mudah Untuk Diubah Menjadi Kode.

•  Definisi Terurut Terdapat Dengan Jelas Dalam Algoritma.

• Cocok Untuk Pengurutan Data Dengan Elemen Kecil Telah Terurut

   Kelemahan Bubble Sort

• Bubble Sort merupakan metode pengurutan yang paling tidak efisien.

•  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.

2. Selection Sort :
Ide utama dari algoritma selection sort adalah memilih elemen dengan nilai paling rendah dan menukar elemen yang terpilih dengan elemen ke-i. Nilai dari i dimulai dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.



Kelebihan Selection Sort :

• Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

• Mempercepat pencarian

• Mudah menentukan data maksimum /minimum.

• Mudah menggabungkannya kembali.Kompleksitas selection sort relatif lebih kecil.

Kekurangan Selection Sort :

• Membutuhkan method tambahan

• Sulit untuk digabungkan kembali

• Perlu dihindari untuk penggunaan data lebih dari 1000 tabel, karena akan menyebabkan kompleksitas yang lebih tinggi dan kurang praktis

3. Insertion Sort :
Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan dan yang sudah diurutkan. Elemen pertama diambil dari bagian array yang belum diurutkan dan kemudian diletakkan sesuai posisinya pada 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.

Kelebihan

•  Sederhana dalam penerapannya.

•  Mangkus dalam data yang kecil.

•  Jika list sudah terurut atau sebagian terurut maka Insertion Sort akan lebih cepat dibandingkan dengan Quicksort.

•  Mangkus dalam data yang sebagian sudah terurut.

•   Lebih mangkus dibanding Bubble Sort dan Selection Sort.

•  Loop dalam pada Inserion Sort sangat cepat, sehingga membuatnya salah satu algoritma pengurutan tercepat pada jumlah elemen yang sedikit.

•  Stabil.

Kekurangan

•  Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.

•   Untuk larik yang jumlahnya besar ini tidak praktis.

•   Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti             seluruh bagian sebelum menyisipkan elemen berikutnya.

•   Membutuhkan waktu O(n2) pada data yang tidak terurut, sehingga tidak cocok dalam pengurutan elemen dalam jumlah besar.

4. Shell Sort :
Merupakan algoritma yang stau jenis dengan insertion sort, dimana pada setiap nilai i dalam n/i item diurutkan. Pada setiap pergantian nilai, i dikurangi sampai 1 sebagai nilai terakhir


 

author: wikipedia. 

 Kelebihan :

•  Algoritma ini sangat rapat dan mudah untuk diimplementasikan.

•  Operasi pertukarannya hanya dilakukan sekali saja.

•  Waktu pengurutan dapat lebih ditekan.

•  Mudah menggabungkannya kembali.

•  Kompleksitas selection sort relatif lebih kecil.

 

Kekurangan :

•  Membutuhkan method tambahan.

•  Sulit untuk membagi masalah.

   5. Merge Sort :

Merge Sort merupakan pengurutan untuk data yang jumlahnya besar, dimana data tidak semuanya dapat dimuat dalam memori utama (main memory), sehingga harus disimpan dalam penyimpanan sekunder (secondary storage) berupa berkas (file). Proses penggabungan sedikitnya dua buah file ke dalam file lain dalam kondisi terurut.  Algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. 

Berikut menjelaskan langkah kerja dari Merge sort : 

1. Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
2. Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
3. Kombinasi
Mengkombinasikan dua bagian tersebut secara rekursif untuk mendapatkan rangkaian data berurutan
Proses rekursi berhenti jika mencapai elemen dasar. Hal ini terjadi bilamana bagian yang akan diurutkan menyisakan tepat satu elemen. Sisa pengurutan satu elemen tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

author : Swfung8  

Konsep dari merge sort sendiri adalah sebagai berikut :
1.) Bagi list besar menjadi setengahnya 

2.) Lakukan hal ini secara rekursif sampai diperoleh list dengan satu elemen saja

3.) List tersebut digabung lagi menjadi sebuah list besar yang sudah terurut.  

Contoh pseudocode untuk merge sort :

function mergesort(m)
var
kiri, kanan, hasil :list
tengah: integer
algoritma
if length(m) _ 1 then
return m
else
tengah = length(m) div 2
for x = m to tengah do
add x to kiri
end for
for x = m after tengah do
add x to kanan
end for
kiri = mergesort(kiri)
kanan = mergesort(kanan)
hasil = merge(kiri, kanan)
end if
return hasil

Kelebihan dari merge sort :

Dibanding dengan algoritma lain, merge sort ini termasuk algoritma yang sangat efisien dalam penggunaannya sebab setiap list selalu dibagi bagi menjadi list yang lebih kecil, kemudian digabungkan lagi

6. Quick Sort :

Algoritma ini berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :
1. Divide
Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1] adalah kurang dari atau sama dengan A[q] dan setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen pada A[q]. A[q] disebut sebagai elemen pivot. Perhitungan pada elemen q merupakan salah satu bagian dari prosedur pemisahan.
2. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif. Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

Author: Matt Chan 

Kelebihan

Algoritma Quicksort memiliki kompleksitas O(n log n) dimana pada  prakteknya lebih cepat dari algoritma pengurutan lainnya.

Kekurangan

Pada kemungkinan terburuknya, algoritma Quicksort ini dapat memiliki kompleksitas O(n2). Meskipun ini sangat langka terjadi  

7. Heap Sort: 

Heap sort adalah sorting yang menggunakan struktur data heap, dengan nilai parent selalu lebih besar dari pada nilai childnya.

Algoritma:

1. Buat suatu heap.
2. Ambil isi dari root masukkan kedalam sebuah array.
3. Hapus element root dengan mempertahankan properti heap.
4. Ulangi sampai tree menjadi kosong

author : Swfung8  8. Bucket Sort :

Algoritma:

• Cari nilai maksimum dan minimum di array
• Inisialisasi array bucket Daftar <> unsur (ukuran maxValue – minValue + 1)
• Pindahkan elemen dalam array untuk bucket
• Write bucket keluar (dalam rangka) ke array yang asli

 
8. Radix Sort:

Pengertian Radix Sort merupakan salah satu algoritma Non-Comparasion Sort (pengurutan tanpa perbandingan). Proses yang dilakukan dalam metode ini adalah mengklasifikasikan/menyelesaikan data sesuai dengan kategori terurut yang tertentu, dan tiap kategori dilakukan pengklasifikasian lagi, dan seterusnya sesuai kebutuhan, kemudian subkategori-kategori atau bagian-bagian dari  kategori  tersebut digabungkan kembali.

Secara harfiah Radix dapat diartikan sebagai posisi dalam angka, karena cara ini pertama kalinya mengurutkan nilai-nilai yang dimasukan (input) berdasarkan radix pertamanya, lalu pengurutan dilakukan berdasarkan radix keduanya, dan begitu seterusnya. Pada sistem desimal, radix adalah digit dalam angka desimal. Misalnya, angka “169” mempunyai 3 digit yaitu 1,6 dan 9.

Secara kompleksitas waktu, radix sort termasuk ke dalam Divide and Conquer.Namun dari segi algoritma untuk melakukan proses pengurutan, radix sort tidak termasuk dalam Divide and Conquer. 

Algoritma radix sort adalah salah satu algoritma pengurutan yang paling mangkus karena tidak menggunakan perbandingan secara langsung. Untuk kasus bilangan bulat (integer), algoritma ini akan mengurutkan data dengan mengelompokkan data-data berdasarkan digit yang memiliki significant position dan value yang sama. Kelompok digit ini ditampung dalam suatu variable “bucket”. Struktur datanya direpresentasikan dengan array. Algoritma ini pertama kali diperkenalkan pada tahun 1887 oleh Herman Hollerith pada mesin tabulasi. 

Ada dua jenis radix sort saat ini :

- LSD (least significant digit) radix sort, yaitu radix sort yang mengurutkan data dimulai dari digit terkecil. Algoritma ini cenderung stabil karena tetap mengikuti urutan awal data-data sebelum diurutkan.

- MSD (most significant digit) radix sort, yaitu radix sort yang mengurutkan data dimulai dari digit terbesar. Algoritma ini lebih susah untuk direalisasikan daripada LSD radix sort, dan biasanya tidak mengikuti urutan awal data-data yang akan diurutkan.

Makalah ini hanya akan membahas LSD radix sort.

Misalkan terdapat sebuah array dengan elemen “121 76 823 367 232 434 742 936 274”. Dengan menggunakan algoritma radix short :

Pertama kali data dibagi-bagi sesuai dengan digit terkanan  :

121

76

823

367

232

434

742

936

274

Pada saat penentuan kategori lihat terlebih dahulu nilai digit yang terbesar dicontoh ini yakni nilai digit yang terbesar 9 sehingga kategori sebanyak 9 baris dan diawali dari 0. Langsung aja supaya lebih jelas perhatikan tabel dibawah ini :

Kategori Digit 1 (satuan)	Isi
0	-
1	121
2	232, 742
3	823
4	434, 274
5	-
6	76, 936
7	367
8	-
9	-

Hasil pengkategori pertama kemudian digabungkan kembali menurut penjelasan yang diatas:

121

232

742

823

434

274

76

936

367

Kemudian dilakukan pengkategorian kembali berdasarkan digit yang kedua dengan berpatokan(melihat) baris urutan pengkategorian pertama yaitu :

Kategori Digit 2 (puluhan)	Isi
0	-
1	-
2	121, 823
3	232, 434, 936
4	742
5	-
6	367
7	274, 76
8	-
9	-

Selanjutnya hasil pengkategori kedua digabungkan kembali.

121

823

232

434

936

742

367

274

76

Kemudian langkah ketiga (terakhir), dilakukan pengkategorian kembali berdasar digit ketiga. dengan berpatokan (melihat) baris urutan pengkategorian kedua  yaitu :

Kategori Digit 3 (Ratusan)	Isi
0	076
1	121
2	232, 274
3	367
4	434
5	-
6	-
7	742
8	823
9	936

Jadi, hasil akhirnya dapat dituliskan :

76

121

232

274

367

434

742

823

936

Dari langkah-langkah yang telah dilakukan dalam proses pengurutan menggunakan radix sort, jelas tampak bahwa radix sort termasuk algoritma pengurutan tanpa pembanding. Dengan sifatnya yang melihat digit-digit angka sebagai pengontrolnya, Radix Sort dapat diimplementasikan dalam pengurutan bilangan desimal dan bilangan bit. Namun dalam penggunaannya radix sort bisa dimodifikasi sehingga bisa digunakan untuk menggurutkan data data negatif dan pecahan.

 Kelebihan dan Kekurangan Redix Short :

Algoritma radix sort memiliki kelebihan dan kekurangan yang berbeda dibandingkan dengan algoritma pengurutan yang lain. Beberapa kelebihan algoritma radix sort adalah sebagai berikut :

- Algoritma sangat mangkus. Hal ini dapat dilihat dari kompleksitas waktu asimptotiknya yang sangat kecil (O(kN)). Hal ini mengakibatkan algoritma radix sort sangat efektif untuk data dalam jumlah yang sangat besar sekalipun.

- Konsep algoritma mudah dipahami. Algoritma radix sort mengurutkan data berdasarkan digit, tidak melalui proses perbandingan yang cenderung sulit dipahami.

Walaupun memiliki banyak kelebihan dibandingkan algoritma pengurutan yang lain, algoritma ini memiliki kekurangan : realisasi program rumit dan kurang fleksibel untuk digunakan pada tipe data lain.

Realisasi program untuk algoritma radix sort tidak semudah memahami konsep dasarnya. Secara umum, algoritma ini membutuhkan bucket untuk mengelompokkan data-data yang sedang diurutkan. Inisialisasi bucket untuk kasus ini tidak mudah dilakukan. Pada awalnya, radix sort hanya dapat digunakan untuk data bertipe bit dan desimal. Tetapi, seiring waktu, radix sort mulai dikembangkan untuk tipe data yang lain. Saat ini radix sort sudah dapat digunakan untuk tipe data berupa bilangan pecahan dan bilangan negatif. Akan tetapi, modifikasi terhadap algoritma ini menjadi signifikan. Pada umumnya, pengembangan algoritma radix sort untuk tipe data lain dibantu dengan menggunakan counting sort, yang merupakan salah satu algoritma pengurutan yang tidak menggunakan perbandingan. Penulis tidak akan membahas algoritma ini mengingat batasan makalah yang diberikan.

 
Daftar Pustaka :
https://lunarphue.wordpress.com/information-technology/asd/macam-macam-sorting/
https://cuwakep.wordpress.com/2012/12/23/buble-sort-kelebihan-kelemahan/
https://giarellagia.wordpress.com/2012/06/17/selection-sort/
https://betaraubd.wordpress.com/2012/11/23/kekurangan-dan-kelebihan-algoritma-insertion-sort-dan-sell-sort/
http://cheatlinknote.blogspot.co.id/2011/02/sharemetode-bubble-sort-dan-merge-sort.html
http://galaksi3.blogspot.co.id/2014/12/makalah-redix-sort-struktur-data-sorting.html