Materi kuliah
ALGORITMA PENGURUTAN & PENCARIAN
Ir. Roedi Goernida, MT. (
[email protected])
Program Studi Sistem Informasi – Fakultas Rekayasa Industri Institut Teknologi Telkom Bandung 1
2011
Pengelompokan Pengurutan
Pengurutan internal → dilakukan terhadap sekumpulan data yang disimpan dalam media internal komputer yang dapat diakses secara langsung pada setiap elemennya. Pengurutan eksternal → dilakukan terhadap data yang disimpan di dalam memori sekunder dan digunakan pada data yang cukup besar. 2 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 1
Metoda Pengurutan Pengurutan didasarkan kepada: ●
Perbandingan (comparison-based sorting) → Bubble sort, exchange sort
●
Prioritas (priority queue sorting) → Selection sort, heap sort (menggunakan tree) Penyisipan & penjagaan terurut (insert & keep sorted ) → Insertion sort, tree sort
●
●
Pembagian & penguasaan (devide and conquer) conquer → Quick sort, merge sort
●
Berkurang menurun (diminishing increment sort ) → Shell sort (pengembangan insertion) 3
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 2
Bubble sorting (1/2) ●
Merupakan proses pengurutan secara bergerak atau berpindah ke posisi yang tepat → diibaratkan gelembung yang keluar dari sebuah gelas bersoda.
●
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. A[1] ≤ A[2] ≤ A[3] ≤ A[4] ≤ … ≤ A[n] 4
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 3
Bubble sorting (2/2) ●
Pengurutan Descending: → Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar. D[1] ≥ D[2] ≥ D[3] ≥ D[4] ≥ … ≥ D[n]
●
Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau sebaliknya
●
Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses tersebut, dan seterusnya sampai dengan iterasi sebanyak n-1.
●
Proses pengurutan berakhir jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan. 5
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 4
Ilustrasi (1/2) Proses 1 67 25
Proses 2 38
13
16
9
9
67
25
38
13
16
67
25
38
13
9
16
9
67
25
38
13
16
67
25
38
9
13
16
9
67
25
13
38
16
67
25
9
38
13
16
9
67
13
25
38
16
67
9
25
38
13
16
9
13
67
25
38
16
9
67
25
38
13
16
9
13
67
25
38
16
Proses 3 9
13
67
25
38
9
13
67
25
16
38
9
13
25
16
25
38
9
13
16
67
25
38
9
13
16
67
25
38
9
13
16
67
25
38
`
16
6 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 5
Ilustrasi (2/2) Proses 4 9 13
16
67
25
38
9
13
16
67
25
38
9
13
16
25
67
38
9
13
16
25
67
38
9
13
16
25
67
38
9
13
16
25
67
38
Proses 5 9 13
16
25
67
38
9
13
16
25
38
67
9
13
16
25
38
67
9
13
16
25
38
67
9
13
16
25
38
67
9
13
16
25
38
67 7
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 6
Algoritma Bubble sort
ba := n i := 1 if A[i] < temp A[i] A[i+1]
A[i+1] then := A[i] := A[i+1] := temp
8 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 7
Selection sorting
●
Merupakan kombinasi antara sorting & searching.
●
Cara pengurutannya yaitu membandingkan elemen sekarang dengan elemen berikutnya sampai elemen yang terakhir.
●
Untuk setiap proses akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar untuk dipertukarkan ke posisi yang tepat.
●
Selama proses berlangsung, pembandingan dan pengubahan hanya dilakukan pada index pembanding saja, pertukaran data secara fisik terjadi pada akhir proses. 9
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 8
Ilustrasi (1/2)
13 0
67 1
38 2
Pembanding 13 < 67 13 < 38 13 < 25 13 > 9 * 9 < 30
25 3
9 4
30 5
9 0
Posisi 0 0 0 4 4
0
67 1
38 2
25 3
13 4
38 2
Pembanding 67 > 38 38 > 25 25 > 13 13 < 30
25 3
13 4
30 5
Posisi 2 3 4 4
Penukaran data idx-1 (67)→ idx-4 (13)
Penukaran data idx-0 (13)→ idx-4 (9)
9
67 1
30 5
9
13
0
1
38 2
25 3
67 4
30 5
10 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 9
Ilustrasi (2/2) 9
13
0
1
38 2
Pembanding 38 > 25 25 < 67 * 67 > 30
25 3
67 4
30 5
Posisi 3 4 4
9
13
0
1
25 2
Pembanding 38 < 67 67 > 30 *
38 3
67 4
30 5
Posisi 4 5
Penukaran data idx-3 (38)→ idx-5 (30) Penukaran data idx-2 (38)→ idx-3 (25)
9
13
0
1
25 2
38 3
67 4
30 5
9
13
0
1
25 2
Pembanding 67 > 38 *
30 3
9
13
0
1
67 4
25 2
30 3
67 4
38 5
38 5
Posisi 5
Penukaran data idx-4 (67)→ idx-5 (38)
9
13
0
1
Hand-out: Algoritma Sorting & Searching
25 2
30 3
38 4
67 5
IS1313 - 06
11 Hal. 10
Algoritma Selection sorting
min ← A1 max ← Ai for I ← 2 to n do if Ai < min then min ← Ai endif if Ai > max then maks ← Ai endif endfor
12 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 11
Insertion sorting ●
Dapat digambarkan seperti melakukan pengurutan kartu, dimana selembar demi selembar kartu diambil dan kemudian 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 (di-insert) pada posisi yang seharusnya.
●
Pada penyisipan elemen tersebut, maka elemen-elemen lain akan bergeser ke belakang
●
Keuntungan: - Implementasi yang sederhana. - Efesien untuk ukuran data yang kecil. - langsung melakukan pengurutan ketika ada data baru. 13
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 12
Ilustrasi Iterasi
Data Data Data Data Data Data Data Data Data [0] [1] [2] [3] [4] [5] [6] [7] [8]
Data [9]
Awal
90
30
80
10
40
99
50
70
20
60
i=1
30
90
80
10
40
99
50
70
20
60
i=2
30
80
90
10
40
99
50
70
20
60
i=3
10
30
80
90
40
99
50
70
20
60
i=4
10
30
40
80
90
99
50
70
20
60
i=5
10
30
40
80
90
99
50
70
20
60
i=6
10
30
40
50
80
90
99
70
20
60
i=7
10
30
40
50
70
80
90
99
20
60
i=8
10
20
30
40
50
70
80
90
99
60
i=9
10
20
30
40
50
60
70
80
90
99 14
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 13
Algoritma insertion sorting for i ← 2 to n do y ← A[i] j ← i – 1 found ← false while j ≥ i ← i and (not found) do if y < A[j] then A[j + 1] ← A[j] j ←j – 1 else found ← true endif endwhile A[j + 1] ← y endfor 15 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 14
Shell sorting ●
●
●
●
●
Merupakan pengurutan yang paling efesien & memiliki algoritma yang kompleksitas, tetapi sederhana. Pengurutan dengan metoda perbandingan dan pertukaran. Membandingkan jarak elemen yang telah ditentukan dan selanjutnya dipertukarkan. Penukaran dilakukan terhadap sepasang elemen untuk mencapai keadaan urut. Melakukan pass atau traversal berkali-kali & setiap kali pass mengurutkan sejumlah nilai yang sama dengan ukuran set menggunakan insertion set. 16
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 15
Algoritma shell sorting
jarak ← n div 2 while jarak > 0 do for I ← 1 to n – jarak do J ← I + jarak if A[I] > A[J] then tukar(A[I],A[J]) endif jarak ← jarak div 2 endfor endwhile 17 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 16
Ilustrasi
Pass 1 (step = 5)
90
30
80
10
40
99
50
70
20
60
1
2
3
4
5
6
7
8
9
10
90 .......................................................... 99 30 .......................................................... 50 70 .......................................................... 80 10 .......................................................... 20 40 .......................................................... 60
90
30
70
10
40
99
50
80
20
60
1
2
3
4
5
6
7
8
9
10
Pass 2 (step = 3)
Pass 3 (step = 1)
10 ............................ 50 ............................ 60 ............................90 30 ............................ 40 ............................ 80 20 ............................ 70 ............................ 99
10
30
20
50
40
70
60
80
99
90
1
2
3
4
5
6
7
8
9
10
10
20
30
40
50
60
70
80
90
99 18
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal.17
Penggabungan tabel Penggabungan secara terurut dilakukan dengan memeriksa elemen isi tabel-1 & tabel-2 yang selanjutnya dibandingkan agar isi tabel-3 (tabel baru) menjadi terurut. T1
T2
T3
1
13
24
2
15
27
30
1
1
13
24
2
15
27
30
1
2
1
13
24
2
15
27
30
1
2
13
1
13
24
2
15
27
30
1
2
13
15
1
13
24
2
15
27
30
1
2
13
15
24
1
13
24
2
15
27
30
1
2
13
15
24
27
1
13
24
2
15
27
30
1
2
13
15
24
27
30
19 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 18
Perbandingan waktu sorting
N 5000 7000 9000 11000 13000 15000
Bubble 0.52 0.98 1.66 2.47 3.50 4.55
Waktu (detik) Selection Insertion 0.22 0.17 0.44 0.34 0.72 0.56 1.05 0.83 1.47 1.17 1.97 1.55
Shell 0.02 0.02 0.02 0.03 0.05 0.05
20 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 19
Pencarian ●
●
●
Data seringkali dibutuhkan dalam pembacaan kembali informasi (retrieval information). Pencarian/searching → cara untuk mendapat data yang diinginkan dengan cara menelusuri data-data tersebut. Pencarian elemen data pada Java terbagi atas: Linier / sequential searching → melakukan pengujian setiap item. → digunakan pada data yang masih acak & berurut. Binary searching → dengan membagi dua data: (N+1) div 2 → digunakan pada data yang berurut 21
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 20
Pencarian data pada array ●
Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage
●
Searching terbagi atas: Internal searching – algoritma pencarian yang dilakukan dalam memori komputer. External searching – algoritma pencarian yang melibatkan external media dan menambahkan ke memori utama.
22 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 21
Pencarian sequential
Proses pencarian dilakukan dengan membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa serta dapat dilakukan dalam kondisi data apapun.
23 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 22
Algoritma Pencarian sequential (1/2) 52
87
93
28
76
21
1
2
3
4
5
6
Nilai yang dicari: 28 Elemen yang diperiksa : 52 87 93 28 Index : 4 Nilai yang dicari: 52 Elemen yang diperiksa : 52 Index : 1 Nilai yang dicari: 55 Elemen yang diperiksa : 52 87 93 28 76 21 Index : 0 24 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 23
Algoritma Pencarian sequential (2/2)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11.
begin index 1 while index <= n if key(cari) = key(index) result index goto 11 end if index index + 1 end while hasil not found end 25
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 24
Pencarian biner Pencarian Biner (Binary Search) dilakukan untuk : ● memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya. ●
Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulangulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut. 26 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 25
Algoritma Pencarian biner (1/3) Elemen yang dicari 18 81
76
21
18
16
13
10
7
1 Low
2
3
4
5
6
7
8 High
81 1 Low
76 2
21 3
18 4 Middle
16 5
13 6
10 7
7 8 High
Langkah 1: Low = 1 dan High = 8 Elemen tengah Middle = (1+8) div 2 = 9 div 2 = 4 Langkah 2: Array[4] = X ? (18 = 18) true X ditemukan dan pencarian dihentikan. 27 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 26
Algoritma Pencarian biner (2/3) Elemen yang dicari 16 81
76
21
18
16
13
10
7
1
2
3
4
5
6
7
8
Low
High
Iterasi 1: Langkah 1: Low = 1 dan High = 8 Elemen tengah (Middle) = (1+8) div 2 = 9 div 2 = 4 Langkah 2: Array[4] = X ? (18 = 16) FALSE, sehingga diputuskan pencarian di kiri atau dikanan. Jika Array[4] > 16 ?, (18 > 16) TRUE, lakukan pencarian disebelah kanan dengan Low = middle+1 ( 4+1 = 5) dan High = 8.
28 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 27
Algoritma Pencarian biner (3/3) 16
13
10
7
5
6
7
8
Low
Middle
High
16 5 Low
Iterasi 2: Langkah 1: Low = 5 dan High=8 Elemen tengah Middle = (5+8) div 2 = 13 div 2 = 6 Langkah 2: Array[6] = X ? (13 = 16) FALSE untuk memutuskan pencarian di kiri atau di kanan. Jika Larik[6] > 16 ?, (13 > 16) FALSE, lakukan pencarian di sebelah KIRI --> low = 5 (TETAP) dan High = middle-1 = 5 Iterasi 3: Langkah 1: Low = 5 dan High=5 Elemen tengah Middle = (5+5) div 2 = 10 div 2 = 5 Langkah 2: Array[5] = X ? (16 = 16) TRUE (X ditemukan , pencarian dihentikan) 29 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 28
Algoritma Pencarian biner (3/3) 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.
Mulai Awal 1 Akhir n while Awal <= Akhir Tengah (Awal + Akhir) / 2 if Kunci(Cari) = Kunci(Tengah) Hasil Tengah goto 15 else if Kunci(Cari) > Kunci(Tengah) Awal Tengah + 1 else Akhir Tengah - 1 end if end while Hasil tidak ketemu Selesai 30
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 29
Pencarian dengan Sentinel Proses pencarian dengan Sentinel selalu menjamin bahwa elemen data yang dicari (x) pasti berhasil ditemukan. Untuk menyimpulkan apakah x ditemukan pada elemen sentinel atau bukan, yaitu dengan melihat nilai idx. Jika idx = n+1, x ditemukan pada sentinel → x tidak terdapat di dalam array semula (sebelum penambahan sentinel). jika idx < n +1, x ditemukan sebelum sentinel → x sudah ada di dalam larik L semula. 31 Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 30
Ilustrasi Pencarian Sentinel Elemen data dicari 35 & 28: 52
87
93
28
76
21
21
1
2
3
4
5
6
6 Untuk Sentinel
Di isi data sentinel sesuai dengan elemen yang dicari: 52
87
93
28
76
21
35
1
2
3
4
5
6
7
●
35 ditemukan pada elemen ke-n+1. Sentinel otomatis sudah ditambahkan ke dalam larik. Ukuran larik menjadi = 7.
●
28 ditemukan pada elemen ke-4. Sentinel batal menjadi elemen yang ditambahkan ke dalam larik. Ukuran larik tetap 6. 32
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 31
Algoritma Pencarian Sentinel (1/2)
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.
Mulai L[n + 1] ← x i ← 1 while (L[i] ≠ x) do i ← i + 1 endwhile if idx = n + 1 then idx ← -1 else idx ← i Endif Selesai 33
Hand-out: Algoritma Sorting & Searching
IS1313 - 06
Hal. 32
Selesai
34