Sorting
Terdapat 2 katagori dasar dalam tehnik sorting : internal sort dan
external sort. Metoda Internal sort digunakan apabila koleksi data yang akan
diurutkan tidak dalam jumlah besar sehingga proses dapat dilakukan dalam main
memory. Metoda External sort digunakan apabila koleksi data yang akan diurutkan
dalam jumlah besar dimana koleksi data tersebut ada dalam auxiliary memory
device seperti magnetic tape atau disk.
Insertion sort
Misal array A dengan n
elemen A[1], A[2], ..... , A[N] dalam memori. Algoritma Insertion Sort
memeriksa A dari A[1] sampai dengan A[N], menyisipkan setiap elemen A[K] ke
dalam posisi yang seharusnya dalam subarray terurut A[1], A[2], ..... , A[K-1].
Algoritma sorting ini umumnya digunakan apabila jumlah elemennya sedikit (n
kecil). Masalah yang akan muncul dengan metoda ini adalah bagaimana cara
menyisipkan A[K] ke dalam letak yang seharusnya pada subarray terurut A[1],
A[2], ....., A[K-1].
3 10 4 6 8 9 7 2 1 5
- Bagian biru/abu-abu (dua bilangan pertama) sekarang dalam keadaan terurut secara relatif.
3 10 4 6 8 9 7 2 1 5
Berikutnya, kita perlu menyisipkan bilangan ketiga (4) ke dalam bagian biru/abu-abu sehingga
setelah penyisipan tersebut, bagian biru/abu-abu tetap dalam keadaan terurut secara relatif;
CARANYA :
pertama : Ambil bilangan ketiga (4).
4
3 10 6 8 9 7 2 1 5
- Kedua : Geser bilangan kedua (10) shg ada ruang untuk disisipi.
4
3 10 6 8 9 7 2 1 5
- Ketiga : Sisipkan bilangan 4 ke posisi yang tepat
3 4 10 6 8 9 7 2 1 5
- Sekarang, tiga bilangan pertama sudah terurut secara relatif dan kita sisipkan bilangan keempat kepada tiga bilangan pertama tsb. Setelah penyisipan, empat bilangan pertama haruslah dalam keadaan terurut secara relatif.
3 4 6 10 8 9 7 2 1 5
- Ulangi proses tsb sampai bilangan terakhir disisipkan
3 4 6 8 10 9 7 2 1 5
3 4 6 8 9 10 7 2 1 5
7
3 4 6 2 1 5
8 9 10
3 4 6 7 8 9 10 2 1 5
2 3 4 6 7 8 9 10 1 5
1 2 3 4 6 7 8 9 10 5
1 2 3 4 5 6 7 8 9 10
- Proses Sorting Selesai
Selection Sort
Array
A dengan n elemen A[1], A[2], ....., A[N] dalam memori. Algoritma untuk
mengurutkan A sebagai berikut : Pertama, cari elemen terkecil dalam array A dan
letakkan pada posisi pertama dalam array tersebut. Kemudian cari elemen kedua
terkecil dalam array A dan letakkan dalam posisi kedua dari array tersebut, dan
begitu seterusnya.
Proses 1 : Cari
lokasi LOC yang merupakan elemen terkecil dalam array yang
terdiri dari N elemen , A[1], A[2], ...., A[N] dan
kemudian tukar posisi
A[LOC]
dengan A[1].
Proses 2 : Cari
lokasi LOC yang merupakan elemen terkecil dalam array yang
terdiri
dari N-1 elemen , A[2], A[3], ...., A[N] dan tukar posisi A[LOC]
dengan
A[2]. A[1] , A[2] terurut, jika dan hanya jika A[1] A[2].
Dst.................Sehingga A akan terurut
setelah N-1 proses.
Contoh ;
Array A dengan 8
elemen sbb :
77, 33,
44, 11, 88, 22, 66, 55
Proses algoritma
digambarkan dalam Tabel 1.2. Misalkan
LOC berisi nilai lokasi elemen terkecil A[K], A[K+1],...,A[N] selama proses K.
Elemen yang dilingkari merupakan elemen yang akan ditukar posisinya.
|
Iterasi ke
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
A[6]
|
|
Awal
|
23
|
11
|
16
|
4
|
3
|
9
|
|
l = 1 , lok = 5
|
3
|
11
|
16
|
4
|
23
|
9
|
|
l = 2 , lok = 4
|
3
|
4
|
16
|
11
|
23
|
9
|
|
l = 3 , lok = 6
|
3
|
4
|
9
|
11
|
23
|
16
|
|
l = 4 , lok = 4
|
3
|
4
|
9
|
11
|
23
|
16
|
|
l = 5 , lok = 6
|
3
|
4
|
9
|
11
|
16
|
23
|
Merging
Misal A merupakan
himpunan data terurut dengan r buah elemen dan B himpunan data terurut dengan s
buah elemen. Proses yang menggabungkan elemen-elemen dalam A dan B menjadi
himpunan elemen data terurut tunggal, misal C dengan n = r + s buah elemen
disebut dengan proses Merging. Secara
singkat, proses Merging dapat dijelaskan sebagai berikut ; ambil elemen pertama
dari A, A[1] dan B, B[1]. Bandingkan kedua elemen tersebut. Jika A[1] >
B[1], B[1] dimasukkan dalam C, jika tidak A[1] dimasukkan dalam C. Untuk
himpunan data yang elemennya dimasukkan dalam C, elemen yang akan dibandingkan
adalah elemen berikutnya. Dan seterusnya.
Contoh :
A = 11 12
23 33 45
67
Disini A[1] = 11 dan
B[1] = 9 dibandingkan dan A[1] > B[1], B[1] dimasukkan dalam C. Pembandingan
berikutnya A[1] = 11 dibandingkan dengan B[2] = 12, A[1] dimasukkan dalam C,
dan begitu seterusnya.
Merge Sort
Misal : Array A dangan n elemen A[1], A[2], ....., A[N] dalam memori.
Algoritma Merge Sort yang akan mengurutkan A akan digambarkan sebagai berikut :
Contoh :
Array A berisi 6
elemen sbb :
15 12
45 56 13
10
Masing-masing proses
dalam algoritma merge sort akan dimulai dari elemen awal dalam A dan
menggabungkan (merge) pasangan subarray yang terurut sbb :
Shell Sort
Disebut juga dengan
metoda pertambahan menurun (diminishing increment). Metoda ini dikembangkan
oleh Donald L. Shell tahun 1959. Metoda ini memanfaatkan penukaran sepasang
elemen untuk mencapai keadaan urut. Dalam hal ini jarak dua elemen yang
dibandingkan dan ditukarkan tertentu.
Pada langkah pertama,
ambil elemen pertama dan kita bandingkan dengan elemen pada jarak tertentu dari
elemen pertama tersebut. Kemudian elemen kedua dibandingkan dengan elemen lain
dengan jarak yang sama. Demikian seterusnya sampai seluruh elemen dibandingkan.
Pada contoh berikut,
proses pertama kali jarak diambil separoh banyaknya elemen yang akan diurutkan.
Proses kedua jaraknya diambil separuh jarak yang pertama, dst....
Misal terdapat elemen sebagai berikut :
23 11 3 16 4 9
Proses pengurutan menggunakan metoda Shell ada pada tabel 1.3. Dalam
hal ini elemen yang ditulis miring adalah elemen yang dibandingkan dan kemudian
ditukar, jika perlu.
|
Jarak
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
A[6]
|
|
Awal
|
23
|
11
|
16
|
4
|
3
|
9
|
|
Jarak = 3
|
23
|
11
|
16
|
4
|
3
|
9
|
|
|
4
|
11
|
16
|
23
|
3
|
9
|
|
|
4
|
3
|
16
|
23
|
11
|
9
|
|
|
4
|
3
|
9
|
23
|
11
|
16
|
|
Jarak = 1
|
4
|
3
|
9
|
23
|
11
|
16
|
|
|
3
|
4
|
9
|
23
|
11
|
16
|
|
|
3
|
4
|
9
|
23
|
11
|
16
|
|
|
3
|
4
|
9
|
23
|
11
|
16
|
|
|
3
|
4
|
9
|
11
|
23
|
16
|
|
|
3
|
4
|
9
|
11
|
16
|
23
|
|
Akhir
|
3
|
4
|
9
|
11
|
16
|
23
|
Tidak ada komentar:
Posting Komentar