Data dalam struktur data sangat penting untuk data yang bertipe data
numerik ataupun karakter. Pengurutan dapat dilakukan secara ascending (urut naik)
dan descending (urut turun). Pengurutan (Sorting) adalah proses menyusun
kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, sehingga
tersusun secara teratur menurut aturan tertentu.
Contoh:
Contoh:
Data Acak : 5 6 8 1 3 25 10
Descending : 25 10 8 6 5 3 1
Ada beberapa metode pengurutan, yaitu sebagai berikut :
· Bubble Sort Sort
Sorting yang 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. Pengurutan
Ascending : Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua
elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih
kecil dari elemen berikutnya , maka kedua elemen tersebut ditukar. 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 sorta akan mengulangi proses, demikian seterusnya dari 0 sampai dengan
literasi sebanyak n-1. Kapan berhentinya? Bubble sort berhenti jika seluruh
array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta
tercapai perurutan yang telah diinginkan.
Prinsip kerja dari Bubble Sort :
1. Pengecekan mulai dari data ke-1
sampai data ke-n.
2. Bandingkan data ke-n dengan
data sebelumnya (n-1)
3. Jika lebih kecil maka pindahkan
bilangan tersebut dengan bilangan yang ada didepannya (sebelumnya) satu per
satu (n-1,n-2,n-3….dst)
4. Jika lebih besar maka tidak
terjadi pemindahan
5. Ulangi langkah 2 dan 3 s/d sort
optimal
· Exchange Sort
Sangat mirip dengan
Bubble Sort, dan
banyak yang mengatakan
Bubble Sort sama
dengan Exchange Sort. Pebedaan
ada dalam hal
bagaimana membandingkan
antar elemen-elemennya.
Exchange sort membandingkan
suatu elemen dengan
elemen-elemen lainnya dalam
array tersebut, dan melakukan
pertukaran elemen jika
perlu. Jadi ada
elemen yang selalu
menjadi elemen pusat (pivot). Sedangkan Bubble
sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian
elemen sebelum/sesudahnya itu
akan menjadi pusat
(pivot) untuk dibandingkan dengan
elemen sebelumnya/sesudahnya lagi,
begitu seterusnya.
· Selection Sort
Merupakan kombinasi antara sorting dan searching . Untuk setiap
proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai
terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data
ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan
dicari data kedua terkecil, dan akan ditempatkan di indeks kedua
(data[1]). Selama proses, pembandingan
dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data
secara fisik terjadi pada akhir proses. Prinsip
kerja dari Teknik Selection Sort ini adalah :
1. Pengecekan dimulai data ke-1
sampai dengan data ke-n.
2. Tentukan bilangan dengan index
terkecil dari data bilangan tersebut.
3. Tukar bilangan dengan index
terkecil tersebut dengan bilangan pertama (I=1) dari data bilangan tersebut.
4. Lakukan langkah 2 dan 3 untuk
bilangan berikutnya (I=I+1) sampai didapatkan urutan yang optimal.
·
Insertion Sort
Mirip dengan cara orang mengurutkan kartu, selembar demi selembar
kartu diambil dan disisipkan (insert) ke tempat yang seharusnya. Pengurutan
dimulai dari data ke-2 sampai dengan data terakhir, jika ditemukan data yang
lebih kecil, maka akan ditempatkan (diinsert) diposisi yang seharusnya. Pada
penyisipan elemen, maka elemen-elemen lain akan bergeser ke belakang . Prinsip
dasar insertion adalah secara berulang-ulang menyisipkan setiap elemen ke dalam
posisinya / tempatnya yang benar. Prinsip kerja insertion sort adalah :
1. Pengecekan muali dari data ke-1
sampai data ke-n
2. Bandingkan data ke-I (I=data
ke-2 s/d data ke-n)
3. Bandingkan data ke-I tersebut
dengan data sebelumnya (I-10, jika lebih kecil maka data tersebut dapat
disisipkan ked at awal sesuai dengan posisi yang seharusnya.
4.
Lakukan langkah 2 dan 3 untuk
bilangan berikutnya (i=i+1) samapi didapatkan urutan yang optimal.
· QUICKSORT
Ditemukan oleh C.A.R Hoare. 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). Berikut adalah langkah kerja dari quicksort :
a. Devide
Memilah 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 sma dengan A[q] dan
setiap elemen pada A[q+1…r] adalah lebih besar atau sama dengan elemen A[q].
A[q] disebut juga elemen pivot. Perhitungan pada elemen q merupakan salah satu
bagian dari prosedur pemisahan.
b. Conquer
Mengurutkan elemen pada sub-rangkaian secara rekursif.
· MERGESORT
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 :
a. Devide
Memilah elemen – elemen dari data menjadi
dua bagian.
b. Conquer
Menyelesaikan setiap bagian dengan
memanggil prosedur merge sort secara rekursif.
c. Kombinasi
Mengkombinasikan dua bagian tersebut secara
rekursif untuk mendapatkan rangkaian data berurutan.
d. 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.
· SHELLSORT
Ditemukan oleh Donal Shell pada tahun 1959. Merupakan algoritma
paling efisien dari kelas sorting O(n2). 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. Adapula nilai – nilai jarak yang dianjurkan adalah sebagai
berikut :
a.
Shell’s increment
1, 2, 4, 8
b.
Hibbard’s increment
1, 3, 7, 15, …, 2k – 1
c.
Sedgewick’s increment
1, 5, 19, 41, 109
Pada proses sorting, jarak yang diambil dilakukan secara menurun,
sedangkan proses sorting elemennya dilakukan seperti insertion. Pada pengurutan
elemen – elemen jarak lima, pengurutan dilakukan terhadap data ke-9, ke-4,
ke-8, ke-3, dan seterusnya. Dimana jumlah data yang terlibat dalam suatu
rangkaian pengurutan tidak selalu dua tetapi tergantung pada banyak data.
Andaikan jumlah data adalah 11 maka pada rangkaian pengurutan pertama dilakukan
pengurutan terhadap data ke-10, ke-5, dan ke-0.
Sunday, 21 December 2014 at 22:30:00 GMT-8
(y)