MODUL IV PENCARIAN DAN PENGURUTAN
4.1
Tujuan Tujuan modul IV ini, adalah:
•
Praktikan bisa membuat beberapa program pencarian berdasarkan metode algoritma pencarian
•
Praktikan bisa membuat beberapa program pengurutan berdasarkan metode algoritma pengurutan
•
Praktikan dapat membiasakan diri untuk membuat program secara terstruktur.
•
Praktikan memahami algoritma beberapa metode pencarian dan pengurutan
4.2
Teori
4.2.1 Pencarian Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
4.2.1.1 Metode Pencarian Beruntun (Sequential Search) Metode pencarian beruntun adalah proses membandingkan setiap elemen larik satu persatu secara beruntun, mulai dari elemen pertama, sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. Perhatikan larik di bawah ini : 23 1
45 2
23 3
57 4
12 5
Misalkan nilai yang dicari : x = 57 Elemen yang dibandingkan : 23, 45, 23, 57 (ditemukan) Indeks larik yang dikembalikan : IDX = 4
IV-1
IV-2
Misalkan nilai yang dicari : x = 67 Elemen yang dibandingkan : 23, 45, 23, 57, 12 (tidak ditemukan) Indeks larik yang dikembalikan : IDX = -1 Terdapat 2 bersi algoritma pencarian beruntun, yaitu: 1. Pembandingan Elemen Dilakukan di Awal Pengulangan a. Hasil pencarian: sebuah peubah Boolean yang menyatakan x ditemukan (true) atau tidak ditemukan (false) Contoh Algoritma 1: Procedure SeqSearch(input L : Larikint, input N : integer, input X : integer, output Ketemu : integer) {mencari keberadaan nilai X di dalam larik l[1..N].} {k.awal: X dan larik l[1..N] sudah terdefinisi nilainya} {k.akhir: ketemu bernilai true, jika X ditemukan. Jika x tidak ditemukan, ketemu bernilai false} Deklarasi K : integer
{indeks larik}
Deskripsi K←1 While (K < N) and L[K] ≠ X) do K←K+1 Endwhile {K = N or L[K] = X} If L[K] = X then {X ditemukan} Ketemu ← true Else Ketemu ← false Endif Algoritma Pencarian {program untuk mencari nilai tertentu dengan sequential search} Deklarasi Const NMaks = 100 {jumlah maksimum elemen larik} Type Larikint : array[1..NMaks] of integer L : Larikint X : integer Found : Boolean
{elemen yang dicari} {true jika X ditemukan, false jika X tidak}
Procedure Bacalarik(output L : Larikint, input N : integer) {mengisi elemen larik L[1..N] dengan nilai yang dibaca dari piranti
IV-3
masukan} Procedure SeqSearch(input L : Larikint, input N : integer, input X : integer, output Ketemu : integer) {mencari keberadaan nilai X di dalam larik L[1..N].} Deskripsi Read(N) Bacalarik(L,N) Read(X) SeqSearch(L, N, X, Found) If Found then Write(X, ‘ditemukan’) Else Write(X, ‘tidak ditemukan’) Endif b. Hasil pencarian: indeks elemen larik yang berisi Nilai x. Contoh Algoritma 2: Procedure SeqSearch(input L: Larik, input N : integer, input X : integer, output Idx : integer) {mencari keberadaan nilai X di dalam larik L[1..N]} {k.awal : nilai X dan elemen larik L[1..N] sudah terdefinisi} {k.akhir : idx berisi larik L yang berisi nilai X. jika X tidak ditemukan, maka idx diisi dengan nilai -1} Deklarasi K : integer
{indeks larik}
Deskripsi K←1 While (K
{X ditemukan}
IV-4
2. Aksi Pembandingan dilakukan di dalam badan pengulangan (dengan fungsi). a. Hasil pencarian: sebuah peubah Boolean yang menyatakan x ditemukan (true) atau tidak ditemukan (false) Contoh Algoritma 3: Function SeqSearch(input L : Larikint, input N : integer, input X : integer)→boolean {mengembalikan true jika X terdapat di dalam larik L, atau false jika X tidak ditemukan} Deklarasi X : integer
{indeks untuk pencarian}
Deskripsi K←1 Ketemu ← false While (K ≤ N) and (not Ketemu) do If L[K] = X then Ketemu ← true Else K ← K+1 Endif Endwhile {K > N or Ketemu} return ketemu b. Hasil pencarian: indeks elemen larik yang berisi bilai x. Contoh Algoritma 4: Function SeqSearch(input L : Larikint, input N : integer, input X : integer) → integer {mengembalikan indeks elemen larik L yang elemennya sama dengan X. jika X tidak terdapat di dalam larik L, nilai -1 dikembalikan} Deklarasi K : integer Ketemu : Boolean
{indeks untuk pencarian} {true bila X ditemukan, false bila tidak}
Deskripsi K←1 Ketemu ← false While (K ≤ N) and (not ketemu) do If L[K] = X then
IV-5
Ketemu ← true Else K←K+1 Endif Endwhile {K > N or Ketemu} {simpulkan hasil pencarian} if (L[K] = X) then {X ditemukan} return K {indeks elemen L yang berisi X} else return -1 {X tidak ditemukan, indeks = -1} endif Secara umum metode pencarian beruntun berjalan lambat. Waktu pencarian sebanding dengan jumlah elemen larik. Misalkan larik berukuran n elemen, maka pada kasus di mana x tidak terdapat di dalam larik atau x ditemukan pada elemen yang terakhir. Kita harus melakukan perbandingan dengan seluruh elemen larik, yang berarti jumlah perbandingan yang terjadi sebanyak n kali.
4.2.1.2 Metode Pencarian Beruntun Pada Larik Terurut Larik yang elemennya sudah terurut dapat meningkatkan kinerja algoritma pencarian beruntun. Jika pada larik tidak terurut jumlah perbandingan elemen larik maksimum n kali, maka pada larik terurut (dengan asumsi distribusi elemenelemen larik adalah seragam) hanya dibutuhkan rata-rata n/2 kali perbandingan. Hal ini karena pada larik yang terurut kita dapat segera menyimpulkan bahwa x tidak terdapat di dalam larik bila ditemukan, elemen larik yang lebih besar dari x. Secara singkat, kita akan melakukan proses yang serupa dengan pencarian berurutan. Kita mulai dengan pembandingan dengan elemen yang pertama. Jika kita menganggap larik terurut naik (ascending), maka pencarian akan diteruskan sepanjang data yang dicari masih lebih kecil dari nilai elemen pada larik. Jika elemen larik sudah lebih besar, maka pencarian dihentikan karena pasti data yang dicari tidak akan pernah ditemukan pada larik.
IV-6
Contoh Algoritma 5: Procedure SeqSearch(input L : Larikint, input N : integer, input X : integer, output IDX : integer) {mencari keberadaan nilai X di dalam larik[1..N] yang elemen-elemen sudah terurut menaik} {k.awal : nilai X dan elemen larik L[1..N] sudah terdefinisi elemen-elemen larik L sudah terurut menaik} {k.akhir : IDX berisi indeks larik L yang berisi nilai X. jika X tidak ditemukan, maka IDX diisi dengan nilai -1} Deklarasi K : integer {indeks larik} Deskripsi K←1 While (K < N) and (L[K] < X) do K←1 Endwhile (K = N or L[K] ≥ X) If L[K] = X then {X ditemukan} IDX ← K Else IDX ← -1 Endif Penelitian para ahli menunjukkan bahwa metode ini berjalan dengan sangat efektif dan efisien dibandingkan pencarian berurutan yang tidak terurut, jikaq data yang dicari berada (relatif) pada bagian awal larik. Tetapi, karena kondisi berhenti yang kita tentukan, metode ini kurang lebih berkinerja sama dengan pencarian berurutan jika data yang dicari terletak di bagian akhir larik.
4.2.1.3 Pencarian Bagidua (Binary Search) Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut. Cara kerja metode pencarian biner dapat dijelaskan sebagai berikut: dimisalkan kita memiliki larik terurut seperti di bawah ini:
IV-7
0
5
6
10
11
12
32
34
56
99
Misalkan, kita ingin mencari posisi dari nilai 56. Pertama kali, larik di atas dapat kita bagi menjadi 2 sublarik sebagai berikut: 0
5
6 10 Sublarik 1
11
12
32 34 56 Sublarik 2
99
Kemudian, data (56) dibandingkan dengan elemen terakhir pada sublarik 1 (yang bernilai 11). Jika data tersebut (56) lebih kecil dari elemen terakhir pada sublarik1 (11) maka data akan dicari di subvektor 1. Jika tidak, berarti data akan dicari di sublarik 2 dan sublarik 1 tidak perlu dihiraukan lagi. Proses di atas diulangi lagi. Sublarik 2 dibagi 2 lagi sehingga menghasilkan sublarik dibawah ini: 12 32 34 Sublarik 2.1
56 99 Sublarik 2.2
Kita bandingkan lagi data (56) dengan elemen terakhir sublarik 2.1 (34). Ternyata data (56) lebih besar dari (34), maka pasti data yang dicari ada di sublarik 2.2. terakhir, sublarik 2.2 dipecah lagi. Hasilnya adalah sebagai berikut: 56 Sublarik 2.2.1
99 Sublarik 2.2.2
Demikian dengan 4 iterasi kita sudah menemukan data yang kita cari. Contoh Algoritma 6: Procedure BinarySearch(input L : Larikint, input N : integer, input X : integer, output Idx : integer) {mencari X di dalam larik L[1..N] yang sudah terurut menaik dengan metode pencarian bagidua, keluaran prosedur ini adalah indeks elemen larik yang berisi X. idx diisi 0 jika X tidak ditemukan.} {k.awal: larik L[1..N] sudah berisi data yang sudah terurut menaik, dan X adalah nilai yang akan dicari} {k.akhir: idx berisi indeks larik tempat X ditemukan, idx=0 jika X tidak ditemukan} Deklarasi I, J : integer K : integer Ketemu : Boolean Deskripsi I←1 J←N Ketemu ← false
{indeks kiri dan indeks kanan} {indeks elemen tengah} {flag untuk menentukan apakah X ditemukan}
IV-8
While (not Ketemu) and (I ≤ J) do K ← (I + J) div 2 {bagidua larik L pada posisi X} If L[K] = X then Ketemu ← true Else If (L[K] < X) then {lakukan pencarian pada larik bagian kanan, set indeks ujung kiri larik yang baru} I←K+1 Else {lakukan pencarian pada larik bagian kiri, set indeks ujung kanan larik yang baru} I←J-1 Endif Endwhile 4.2.2 Pengurutan Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Urutan objek tersebut dapat menaik (ascending) atau menurun (descending). Bila N buah objek atau data disimpan di dalam larik L, maka pengurutan menaik berarti menyusun elemen larik sedemikian sehingga: L[1] ≤ L[2] ≤ L[3 ≤ … ≤ L[N] Sedangkan pengurutan menurun berarti menyusun elemen larik sedemikian sehingga: L[1] ≥ L[2] ≥ L[3 ≥ … ≥ L[N] Data yang diurut dapat berupa data bertipe dasar atau tipe terstruktur (record). Jika data bertipe terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan. Field yang dijadikan dasar pengurutan dikenal sebagai field kunci. Adanya kebutuhan terhadap proses pengurutan memunculkan bermacammacam metode pengurutan. Metode tersebut diantaranya adalah: 1) Metode Pengurutan Gelembung (Bubble Sort), 2) Metode Pengurutan Pilih (Selection Sort), 3) Metode Pengurutan Sisip (Insertion Sort), 4) Metode Pengurutan Shell (Shell Sort), 5) Heap Sort, 6) Quick Sort, 7) Merge Sort, 8) Radix Sort dan 9) Tree Sort. Pada modul ini, tidak semua metode pengurutan akan dibahas. Tidak ada metode yang terbaik untuk pengurutan. Kebanyakan metode pengurutan sederhana hanya bagus untuk volume data yang kecil tetapi lambat untuk ukuran data yang besar. Metode pengurutan yang lebih cepat pun (seperti
IV-9
quick sort dan merge sort) memang bagus untuk mengurutkan data yang banyak, tetapi tidak bagus untuk ukuran data yang sedikit karena memerlukan beban tambahan (overhead) yang boros waktu dan memori. Metode pengurutan dapat diklasifikasikan sebagai berikut: a. Metode pengurutan internal, yaitu metode pengurutan untuk data yang disimpan di dalam memori computer. Umumnya struktur internal yang dipakai untuk pengurutan internal adalah larik, sehingga pengurutan internal disebut juga pengurutan larik. b. Metode pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan di dalam disk storage, disebut juga pengurutan arsip (file), karena struktur eksternal yang dipakai adalah arsip.
4.2.2.1 Metode Pengurutan Gelembung (Bubble Sort) Metode ini memiliki prinsip pengapungan. Apabila kita menginginkan larik terurut menaik, maka elemen larik yang berharga paling kecil ‘diapungkan’, artinya diangkat ke atas (atau ke ujung kiri larik) melalui proses pertukaran. Proses pengapungan ini dilakukan sebanyak N-1 langkah dengan N adalah ukuran larik. Pada akhir setiap langkah ke-I, larik L[1..N] akan terdiri atas dua bagian yaitu bagian yang sudah terurut, yaitu L[1..I] dan bagian yang belum terurut L[I+1..N]. Setelah langkah terakhir, diperoleh larik L[1..N] yang terurut menaik. Dimisalkan larik L dengan N=10 sebagai berikut : 25 1
27 2
10 3
8 4
76 5
21 6
maka langkah-langkah pengurutannya adalah: Semula Iterasi 1 Iterasi 2 Iterasi 3 Iterasi 4 Iterasi 5
25 8 8 8 8 8
27 25 10 10 10 10
10 27 25 21 21 21
8 10 27 25 25 25
76 21 21 27 27 27
21 76 76 76 76 76
terurut
IV-10
Contoh Algoritma 1: Procedure BubbleSort(input/output L : Larikint, input N : integer) {mengurutkan larik L[1..N] sehingga terurut menaik dengan metode pengurutan gelembung} {k.awal : elemen larik L sudah terdefinisi nilai-nilainya} {k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤ .. ≤ L[N]} Deklarasi I : integer K : integer
{pencacah untuk jumlah langkah} {pencacah untuk pengapungan pada setiap langkah}
Procedure Tukar(input/output A : integer, input/output B : integer) {mempertukarkan nilai A dan B} Deskripsi For I ← 1 to N – 1 do For K ← N downto I + 1 do If L[K] < L[K-1] then {pertukarkan L[K] dengan L[K-1]} tukar(L[K], L[K-1]) endif endfor endfor Bagaimana dengan algoritma pilih maksimum terurut menurun?
Pengurutan gelembung merupakan metode pengurutan yang tidak efisien. Hal ini disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap langkah pengapungan. Untuk nukuran larik yang besar, pengurutan dengan metode ini membutuhkan waktu yang lama. Karena alasan itu, maka metode ini jarang digunakan dalam praktek. Namun, kelebihan metode ini adalah pada kesederhanaannya dan mudah dipahami.
4.2.2.2 Metode Pengurutan Pilih (Selection Sort) Metode ini memilih elemen maksimum/minimum dari larik, lalu menempatkan elemen itu pada awal atau akhir larik (elemen terujung). Selanjutnya elemen terujung tersebut ‘diisolasi’ dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk elemen larik yang tersisa, yaitu
IV-11
memilih elemen maksimum/minimum berikutnya dan mempertukarkannya dengan elemen terujung larik sisa. Dua varian algoritma pengurutan pilih ditinjau dari pemilihan elemen maksimum/minimum, yaitu: a. Pengurutan Pilih Maksimum Misalkan larik L dengan N=6 sebagai berikut: 29 1
27 2
10 3
8 4
76 5
21 6
maka langkah-langkah pengurutannya adalah: Semula Iterasi 1 Iterasi 2 Iterasi 3 Iterasi 4 Iterasi 5
29 29 21 21 10 8
27 27 27 8 8 10
10 10 10 10 21 21
8 8 8 27 27 27
76 21 29 29 29 29
21 76 76 76 76 76
terurut
Contoh Algoritma 2: Procedure SelectionSort(input/output L : Larikint, input N : integer) {mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan maksimum} {k.awal : elemen larik L sudah terdefinisi harganya} {k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤ ... ≤ L[N]} Deklarasi I : integer J : integer Imaks : integer
{pencacah untuk mencari nilai maksimum} {indeks yang berisi nilai maksimum sementara}
Procedure tukar(input/output A : integer, input/output : B : integer) {mempertukarkan nilai A dan B} Deskripsi For I ← N downto 2 do {jumlah pengulangan sebanyak N-1} {cari elemen maksimum pada elemen L[1..I]} Imaks ← I {elemen pertama diasumsikan sebagai elemen maksimum sementara} For J ← 2 to I do If L[J] > L[Imaks] then Imaks ← J
IV-12
Endif Endfor {pertukarkan L[Imaks] dengan L[I]} Tukar(L[Imaks], L[I]) Endfor Bagaimana dengan algoritma pilih maksimum terurut menurun? b. Pengurutan Pilih Minimum Pada algoritma pengurutan pilih minimum, basis pencarian adalah elemen minimum (terkecil). Elemen minimum ditempatkan di awal larik (agar larik terurut menaik) atau ditempatkan di akhir larik (agar larik terurut menurun). Misalkan larik L dengan N=6 sebagai berikut: 29 1
27 2
10 3
8 4
76 5
21 6
maka langkah-langkah pengurutannya adalah: Semula Iterasi 1 Iterasi 2 Iterasi 3 Iterasi 4 Iterasi 5
29 8 8 8 8 8
27 27 10 10 10 10
10 10 27 21 21 21
8 29 29 29 27 27
76 76 76 76 76 29
21 21 21 27 29 76
terurut
Contoh Algoritma 3: Procedure SelectionSort(input/output L : larikint, input N : integer) {mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan pilih minimum} {k.awal : elemen larik L sudah terdefinisi harganya} {k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤ ... ≤ L[N]} Deklarasi I : integer J : integer Imin : integer
{pencacah untuk mencari nilai maksimum} {indeks yang berisi nilai maksimum sementara}
Procedure Tukar(input/output A : integer, input/output : B : integer) {mempertukarkan nilai A dan B} Deskripsi For I ← 1 to N-1 do
IV-13
{cari indeks dari elemen minimum di dalam larik L[I..N]} Imin ← I For J ← I+1 to N do If L[J] > L[Imin] then Imin ← J Endif Endfor {pertukarkan L[Imin] dengan L[I]} Tukar(L[Imin], L[I]) Endfor Bagaimana dengan algoritma pilih maksimum terurut menurun?
Dibandingkan dengan metode pengurutan gelembung, metode pengurutan pilih memiliki kinerja yang lebih baik. Alasannya, operasi pertukaran elemen hanya dilakukan sekali saja dengan demikian lama pengurutannya berkurang.
4.2.2.3 Metode Pengurutan Sisip (Insertion Sort) Algoritma pengurutan sisip untuk memperoleh elemen larik yang terurut menaik adalah sebagai berikut Misalkan larik L dengan N=6 sebagai berikut: 29 1
27 2
10 3
8 4
76 5
21 6
maka langkah-langkah pengurutannya adalah: Semula Iterasi 1 Iterasi 2 Iterasi 3 Iterasi 4 Iterasi 5 Iterasi 6
29 29 27 10 8 8 8
27 27 29 27 10 10 10
10 10 10 29 27 27 21
8 8 8 8 29 29 27
76 76 76 76 76 76 29
21 21 21 21 21 21 76
terurut
Contoh Algoritma 4: Procedure InsertionSort(input/output L : Larikint, input N : integer) {mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan sisip} {k.awal : elemen-elemen larik L sudah terdefinisi nilainya} {k.akhir : elemen larik L terurut menaik sedemikian sehingga L[1] ≤ L[2] ≤ ... ≤ L[N]}
IV-14
Deklarasi I : integer J : integer Y : integer
{pencacah untuk mencari nilai maksimum} {peubah boolean untuk menyatakan posisi penyisipan ditemukan}
Ketemu : boolean Deskripsi {elemen L[1] dianggap sudah terurut} {mulai dari langkah 2 sampai langkah N} For I ← 2 to N do {sisipkan L[I] ke dalam bagian yang sudah terurut} Y ← L[I] {cari posisi yang tepat untuk Y di dalam L[1..I-1] sambil menggeser} J←I–1 Ketemu ← false While (J≥1) and (not Ketemu) do If Y < L[J] then L[J+1] ← L[J] J←J–1 Else Ketemu ← true Endif Endwhile {J < 1 or Ketemu} L[J+1] ← Y {sisipkan Y pada tempat yang sesuai} Endfor Bagaimana algoritma pengurutan sisip untuk pengurutan menurun?? Kelemahan metode pengurutan sisip terletak pada banyaknya operasi pergeseran yang diperlukan dalam mencari posisi yang tepat untuk elemen larik. Untuk larik dengan N yang besar, jumlah operasi pergeseran meningkat secara kuadratik, sehingga pengurutan sisip kurang bagus untuk volume data yang besar.
4.2.2.4 Metode Pengurutan Shell (Shell Sort) Metode shell sort pertama kali diperkenalkan oleh Donald L. Shell tahun 1959. Metode ini didasarkan pada penukaran sepasang elemen untuk mencapai keadaan urut. Dalam hal ini jarak elemen yang akan dibandingkan (kemudian ditukarkan) ditentukan (biasanya jarak ini ditentukan dengan cacah data = n dibagi 2). Pada langkah pertama, elemen-elemen yang terpisahkan oleh jarak itu dibandingkan dan jika perlu ditukarkan. Kemudian jarak dibagi 2 sehingga
IV-15
bernilai setengah jarak yang semula. Kemudian, pembandingan dan penukaran itu dilanjutkan dengan jarak yang baru. Demikian selanjutnya hingga jarak sama dengan 1. Untuk memperjelas metode pengurutan shell adalah sebagai berikut: Data sebelum diurutkan: 23 1
45 2
12 3
24 4
56 5
34 6
27 7
23 8
16 9
Semula Jarak = 4
23 23 23 23 23 23 23
45 45 45 34 34 34 34
12 12 12 12 12 12 12
24 24 24 24 24 23 23
56 56 56 56 56 56 16
34 34 34 45 34 34 45
27 27 27 27 27 27 27
23 23 23 23 23 24 24
16 16 16 16 16 16 56
Jarak=2
23 12 12 12 12 12 12 12
34 34 23 23 23 23 23 23
12 23 23 16 16 16 16 16
23 23 34 34 34 34 34 34
16 16 16 23 23 23 23 23
45 45 45 45 45 45 24 24
27 27 27 27 27 27 27 27
24 24 24 24 24 24 45 45
56 56 56 56 56 56 56 56
Jarak=1
12 12 12 12 12 12 12 12 12
23 23 16 16 16 16 16 16 16
16 16 23 23 23 23 23 23 23
34 34 34 34 23 23 23 23 23
23 23 23 23 34 34 23 23 23
24 24 24 24 24 34 27 27 27
27 27 27 27 27 27 34 34 34
45 45 45 45 45 45 45 45 45
56 56 56 56 56 56 56 56 56
Contoh Algoritma 5 Procedure ShellSort(input/output A : Larikint, input N : integer) {mengurutkan elemen larik L[1..N] sehingga tersusun menaik dengan metode pengurutan shell} {k.awal: elemen-elemen larik L sudah terdefinisi nilainya} {k.akhir: elemen-elemen larik L terurut menaik}
IV-16
Deklarasi I : integer J : integer Jarak : integer Deskripsi 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 4.2.2.5 Metode Merge Sort Pada metode ini diterapkan pada dua buah larik yang digabungkan kemudian kita ingin mengurutkannya. Larik masukan yang mempunyai N elemen dianggap N buah larik yang masing-masing tersusun oleh 1 elemen. Untuk setiap larik, kita lakukan penggabungan (merging) dengan larik di sebelahnya dengan meletakan elemen yang lebih kecil di sebelah kiri kemudian penggabungan diteruskan hingga mendapatkan kembali 1 larik yang utuh. Ilustrasi merge sort adalah sebagai berikut: Semula
10
5
12
0
32
56
34
Semula
5
10
Semula
0
Semula Semula
6
11
99
0
12
32
56
6
34
11
99
5
10
12
6
32
34
56
11
99
0
5
6
10
12
32
34
56
11
99
0
5
6
10
11
12
32
34
56
99
IV-17
Contoh Algoritma 6: Procedure Merge(input/output A, B : Larik, Output Awal,Tengah,Akhir : integer) Deklarasi I, J, K, T : integer Deskripsi I ← Awal K ← Awal J ← Tengah + 1 Do {elemen sebelah kiri lebih kecil} If A[I] < A[J] then B[K] ← A[I] I←I+1 Else B[K] ← A[J] {elemen sebelah kanan lebih besar} J←J+1 Endif K←K+1 While ((I ≤ Tengah) or (J ≤ Akhir)) {memasukkan sisa elemen saat 2 larik tidak sama panjang} if I > Tengah then {larik kiri lebih dulu habis} for T ← J to Akhir B[K+T-J] ← A[T] Endfor Else {elemen kanan habis lebih dulu} For T ← I to Tengah B[K+T-I] ← A[T] Endfor Endif Procedure Iterasi(input/output A, B : Larik, Input N, Cacah : integer) Deklarasi I, T : integer Deskripsi I←1 While I < (N – 2*Cacah + 1) do Merge(A, B, I, I+Cacah-1, N) I ← I + 2*Cacah Endwhile If (I+Cacah-1) < N then {penggabungan ke sublarik} Merge(A, B, I, I+Cacah-1, N) Else For T ← I to N do B[T] ← A[T]
IV-18
Endfor Endif Algoritma Mergesort {mengurutkan elemen larik sehingga tersusun menaik dengan metode pengurutan merge} {k.awal: elemen-elemen larik yang sudah terdefinisi nilainya} {k.akhir: elemen-elemen larik terurut menaik} Deklarasi Cacah : integer B : Larik Deskripsi Cacah ← 1 While Cacah < N do Iterasi(A, B, N, Cacah) Cacah ← Cacah * 2 Iterasi(B, A, N, Cacah) Cacah ← Cacah * 2 Endwhile
4.3
Kasus
4.3.1 Kasus 1 Buatlah algoritma larik terstruktur data mahasiswa yang terdiri dari Nim, Nama mahasiswa, Jenis Kelamin dan Kelas. Kemudian buatlah algoritma pencarian larik terstruktur tersebut dengan menggunakan 2 metode pencarian diatas. Buatlah programnya dan bandingkan iterasi dari kedua program tersebut! 4.3.2 Kasus 2 Buatlah algoritma
dan program untuk mengurutkan data dengan
menggunakan salah satu metode pengurutan. Ada empat data yang harus diurutkan: •
Nomor Induk, bertipe bilangan bulat
•
Nama, bertipe string
•
Alamat, bertipe string
•
Golongan, bertipe char (dapat bernilai ’A’, ’B’...)
Prosedur pengurutan menerima satu parameter yaitu bilangan bulat yang dapat bernilai 1,2 dan 3. Apabila bernilai 1, maka data diurutkan berdasarkan nomor
IV-19
induk. Apabila bernilai 2, maka data diurutkan berdasarkan nama. Yang terakhir, apabila bernilai 3, maka data diurutkan menurut golongan.
4.4
Tugas – Tugas Pendahuluan Tugas pendahuluan akan dikerjakan selama 30 menit di awal jam
praktikum dengan menggunakan software Self Assessment
4.5
Latihan Praktikum VIII dan IX
4.5.1 Latihan Praktikum VIII (Pertemuan Kedelapan) Buatlah program berdasarkan contoh algoritma yang telah dibahas diatas. 4.5.2 Latihan Praktikum IX (Pertemuan Kesembilan) Buatlah program berdasarkan contoh algoritma yang telah dibahas diatas.
