Minggu, 27 November 2011

Metode Sorting dalam Java

Berasal dari pertanyaan teman angkatan yang menanyakan tentang Sorting, akhirnya kubuat deh tulisan ini tentang Metode Sorting.

Apa itu Sorting ??
Sorting adalah proses menyusun elemen – elemen dengan tata urut tertentu dan
proses tersebut terimplementasi dalam bermacam aplikasi. Kita ambil contoh pada aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif. Hampir seluruh pengguna pada sistem akan memilih tampilan daftar berurutan secara ascending demi kenyamanan dalam penelusuran data. Dalam artian sorting digunakan untuk mengurutkan sesuatu ( misalnya : kata, buku telepon , dll )

Macam- macam Sorting ?
Metode Sorting sebenarnya ada banyak, namun yang paling terkenal adalah

1. Bubble Sorting
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.

2. Insertion Sorting
Salah satu algoritma sorting yang paling sederhana adalah insertion sort. Ide dari
algoritma ini dapat dianalogikan seperti mengurutkan kartu. Penjelasan berikut ini
menerangkan bagaimana algoritma insertion sort bekerja dalam pengurutan kartu. Anggaplah anda ingin mengurutkan satu set kartu dari kartu yang bernilai paling kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian kita mempunyai meja yang lain, meja kedua, dimana kartu yang diurutkan akan diletakkan. Ambil kartu pertama yang terletak pada pojok kiri atas meja pertama dan letakkan pada meja kedua. Ambil kartu kedua dari meja pertama, bandingkan dengan kartu yang berada pada meja kedua, kemudian letakkan pada urutan yang sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu
pada meja pertama telah diletakkan berurutan pada meja kedua.

Algoritma insertion sort pada dasarnya memilah data yang akan diurutkan menjadi dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja kedua). 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.

3. Selection Sorting
Jika Anda diminta untuk membuat algoritma sorting tersendiri, anda mungkin akan
menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan.

Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket kartu. Asumsikan bahwa kartu tersebut akan diurutkan secara ascending. Pada awalnya, kartu tersebut akan disusun secara linier pada sebuah meja dari kiri ke kanan, dan dari atas ke bawah. Pilih nilai kartu yang paling rendah, kemudian tukarkan posisi kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu cari kartu dengan nilai paling rendah diantara sisa kartu yang tersedia. Tukarkan artu yang baru saja terpilih dengan kartu pada posisi kedua. Ulangi langkah – langkah tersebut hingga posisi kedua sebelum posisi terakhir dibandingkan dan dapat digeser dengan kartu yang bernilai lebih rendah.

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.

4. Merge Sorting
Sebelum mendalami algoritma merge sort, mari kita mengetahui garis besar dari konsep divide and conquer karena merge sort mengadaptasi pola tersebut.
a) Divide
Memilah masalah menjadi sub masalah
b) Conquer
Selesaikan sub masalah tersebut secara rekursif. Jika sub-masalah tersebut cukup
ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif
c) Kombinasi
Mengkombinasikan solusi dari sub-masalah, yang akan membimbing menuju penyelesaian atas
permasalahan utama.

Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah berpola divide-and-conquer. Berikut langkah kerja dari Merge sort:

a) Divide
Memilah elemen – elemen dari rangkaian data menjadi dua bagian.
b) Conquer
Conquer setiap bagian dengan memanggil prosedur merge sort secara rekursif
c) 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.

5. Quick Sorting
Quicksort ditemukan oleh C.A.R Hoare. Seperti pada merge sort, algoritma ini juga berdasar pada pola divide-and-conquer. Berbeda dengan merge sort, algoritma ini hanya mengikuti langkah – langkah sebagai berikut :

a) 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.

b) 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

Untuk mengetahui lebih lanjut tentang metode2 sorting, download artikelnya disini

Jangan lupa isikan data diri Anda disini

Semoga bermanfaat, jangan lupa tinggalkan komentar ;)

0 komentar:

Posting Komentar

Selamat Datang di Blogku