Modul Pengurutan
i dalam Bab ini kita sudah membicarakan salah satu algoritma pencarian, yaitu algoritma
pencarian bagi dua. Algoritma pencarian bagi dua hanya dapat diterapkan jika elemen-
elemen larik sudah terurut lebih dahulu. Di dalam Bab 2 ini akan di kemukaan beberapa algoritma
pengurutan data . Masalah pengurutan merupakan persoalan yang menarik, karena terdapat puluhan
algoritma pengurutan yang pernah di kemukaan orang. Sayangnya tidak semua algoritma
pengurutan akan dibahas didalam Bab ini, mengigat beberapa pengurutan sederhana yang akan
dijelaskan . Kelak algoritma pengurutan yang lebih “maju” akan diberikan pada pembahasan
algoritma tingkat lanjut pada seri buku algoritma yang lain.
2.1 Definisi Pengurutan
Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan
tertentu [WIR76]. Urutan objek tersebut dapat menaik (ascending) atau menurut (descending). Bila
n buah objek (atau data) disimpan didalam larik L, maka pengurutan menaik berarti menyusun
elemen larik sedemikian sehimgga :
L[1]≤L[2]≤[3]≤…≤L[n]
Sedangkan pengurutan menurun bearti menyusun elemen larik sedemikian sehingga:
L[1]≥L[2]≥ [3]≥…≥L[n]
Data yang diurut dapat berupa data bertipe dasar atau tipe ter struktur (record). Jika data bertipe
terstruktur, maka harus dispesifikasikan berdasarkan field apa data tersebut diurutkan . Field yang
dijadikan dasar pengurutan dikenal sebagai field kunci.
Contoh 2.1 :Beberapa contoh data terurut
Berikut ini diberikan contoh data terurut:
(i) 23,27,45,67,100,130,501
(data bertipe integer terurut menaik)
(ii) 50.27,31.009,20.3,19.0,-5.2,-10.9
(data bertipe riil terurut menurun)
(iii) ‘Amir’,’Badu’,’Budi’,’Dudi’,’Eno’,’Rudi’,’Zamzani’
(data bertipe string terurut menaik)
(iv) ‘d’,’e’,’g’,I’,x’
D(data bertipe karakter terurut menaik)
(v) <13596001,’Eko’,’A’,>, <13596006,’Rezal’,’C’,’>,
<13596007,’Hamdi’,’D’,’>, <13596010,’Rezal’,C’>,
<13596012,’Ratna’,’B’>
(data mahasiswa bertipe terstruktur terurut menaik berdasarkan field NIM)
Dalam kehidupan sehari-hari, entry di dalam buku telepon, kata didalam kamus bahasa/istilah, dan
entry di dalam ensiklopedi selalu terurut secara alfabetik. Kita juga sering melakukan pengurutan
seperti mencatat alamat teman berdasarkan nama, menyusun tumpukan Koran berdasarkan tanggal,
mengantri di pasar swalayan berdasarkan urutan waktu kedatangan dikasir, dan sebagainya.
Data yang sudah terurut memiliki beberapa keuntungan. Selain memercepat waktu pencarian, dari
data yang terurut kita dapat langsung memperoleh nilai maksimum dan nilai minimum. Untuk data
numeric yang terurut menurun, nilai maksimum adalah elemen pertama larik, dan nilai minimum
adalah elemen terakhir larik. Hal ini bermangfaat untuk mengetahui juara kelas misalnya, atau
mengetahui peserta ujian Seleksi penerimaan Mahasiswa Baru (SPMB) yang memperoleh skor
tertinggi.
Pengurutan dikatakan stabil jika dua atau lebih data yang sama (atau diidentik) tetap pada urutan
yang sama setelah pengurutan: Misalnya di dalam sekelompok data integer berikut terdapat 3 buah
nilai 12 (di beri tanda petik’.”,dan”’ untuk meng identifikasi urutannya.
70,12’,45,10,12”,60,12”’,33,50
Jika suatu metode pengurutan menghasilkan susunan data terurut seperti berikut:
10,12’,12”,12”’,33,45,50,60,70
Maka pengurutannya dikatakan stabil dan metode pengurutannya disebut metode stabil. Tetapi jika
suatu metode pengurutan menghasilkan susunan data terurut seperti contoh berikut:
10,12”,12’,12”’,33,45,50,60,70
Maka pengirutan dan metodenya kita katakana tidak stabil.
Kestabilan pengurutan mungkin penting atau tidak penting [PAR 95]. Misalnya kita ingin
menyusun data buku yang terurut secara alfabetik berdasarkan nama pengarang sekaligus terurut
berdasarkan judul buku oleh pengarang tersebut (pengarang bias menulis lebih dari satu buku). Jika
kita menggunakan pengurutan yang stabil, maka kita urut berdasarkan judul buku lebih dahulu baru
kemudian kita urut berdasarkan nama pengarang. Jika kita menggunakan metode pengurutan yang
kita inginkan.
2.2 Metode-metode Pengurutan
Adanya kebutuhan terhadap proses pengurutan memunculkan bermacam-macam metode
pengurutan. Banyak metode pengurutan yang telah di temukan. Hal ini menunjukkan bahwa
persoalan pengurutan adalah persoalan yang kaya dengan solusi algorimik. Metode yang ditemukan
di dalam leteratur-leteratur computer antara lain:
1. Bubble Sort
2. Selection Sort (maksimum sort atau minimum sort)
3. Insertion Sort
4. Heap Sort
5. Shell Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Tree Sort
Didalam Bab ini kita tidak membahas semua metode pengurutan tersebut, tetapi hanya empat buah
metode pengurutan yang sederhana saja, yaitu;
1. Metode Pengurutan Apung (Bubble Sort)
2. Metode Pengurutan Seleksi (Selection Sort)
3. Metode Penrutan Sisipan (Insertion Sort)
4. Metode Pengurutan Shell (Shell Sort)
Untuk setiap metode pengurutan akan kita tuliskan algoritmanya. Dua metode pertama (bubble dan
selectinon sort) melakukan prinsip pertukaran elemen dalam pross pengurutan sehingga keduannya
dinamakan pengurutan dengan pertukaran (exchange sorth), sedangkan dua metode terakhir
melakukan prinsip geser dan sisip elemen dalam proses pengurutan (shift and insert sort). Semua
metode p;engurutan selalu melakukan operasi perbandingan elemen larik untuk menemukan posisi
urutan yang tepat.
Metode pengurutan yang lain membutuhkan beberapa konsep pengetahuan pendahuluan yang tidak
dicakup didalam buku ini. Misalnya Help Sort dan Tree Sort memerlukan pengetahuan konsep
pohon (tree), Quick Sort dan Marge Sort membutuhkan pengetahuan konsep divide and conquer
dan algoritma rekursif. Untuk pemahaman konsep pengurutan, empat buah algoritma sederhana di
atas sudah cukup untuk diketahui.
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 (sep;rti Quick Sort dan M erge Sort) memang bagus untuk
pengurutan data yang banyak tetapi tidak bagus untuk ukuran data yang sedikit karma memerlukan
beban tambahan (overhead) yang boros waktu dan memori [PAR 95].
Seperti halnya pada pencarian, metode pengurutan juga dapat diklasifikasikan sebagai metode
pengurutan internal dan metode pengurutan eksternal.
1. Metode pengurutan internal, yaitu metode p;engurutan untuk ada yang disimpan di dalam
memori komputer, umumnya struktur internal yang dipakai untuk pengurutan internal
adalah larik, sehingga pengurutan internal disebut juga pengurutan larik.
2. Metode pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan didalam
disk storage, disebut juga pengurutan arsip (file),karena struktur eksternal yang dipakai
adalah arsip.
Di dalam Bab 2 ini kita hanya membicarakan metode pengurutan internal saja. Metode pengurutan
eksternal merupakan bahasan tersendiri yang tidak di cakup didalam buku ini.
Untuk semua algoritma pengurutan yang akan dijelaskan di dalam bab ini kita menggunakan tipe
data larik yang didefinisikan sebagai berikut:
DEKLARASI
Const N maks = 1000 {jumlah maksimum elemen larik}
Type Larikint = array [1..Nmaks] of integer
Algoritma 2.1 Deklarasi larik integer yang digunakan di dalam bab ini
Metode Pengurutan Apung
Metode pengurutan apung (bubble sort) diinspirasikan oleh gelembung sabun yang berada diatas
permukaan air. Karena berat jenis gelembung sabun lebih ringan dari pada berat jenis air, maka
gelembung sabun selalu terapung keatas permukaan. Secara umum, benda-benda yang berat akan
terbenam dan benda-benda yang ringan akan terapung keatas permukaan.
Prinsip pengapungan diatas juga digunakan pada pengurutan apung. Apabila kita mengiginkan larik
terurut menaik, maka elemen larik yang berharga paling kecil ”di apungkan”, artinya diangkat “ke
atas” (atau keujung kiri larik) melalui proses pertukaran. Proses pengapungan ini dilakukan
sebanyak n-1 langkah (satu langkah disebut juga satu kali pass) 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] (Gambar 2.1). setelah langkah terakhir, di
peroleh larik L [1..n] yang terurut menaik.
1 I i+1 n
Sudah terurut Belum terurut
Gambar 2.1 Bagian larik yang terurut pada metode pengurutan apung
Algoritma Pengurutan Apung
Untuk mendapatkan larik yang terurut menaik, algoritma pengurutan apung secara global sebagai
berikut:
Untuk setiap pass i = 1,2,….,n-1, lakukan:
Mulai dari elemen k = n,n-1, …, i+1, lakukan:
1.1. Bandingkan L[k] dengan L[k-1].
1.2. Pertukaran L[k] dengan L[k-1] jika L[k] < L[k-1].
Rincian seriap pass adalah sebagai berikut:
Pass 1: Mulai dari elemen ke-k = n,n-1, …,2, bandingkan L[k] dengan L[k-1]. Jika L[k] <
L[k-1], pertukaran L[k] dengan L[k-1].
Pada akhir langkah 1, elemen L[1] berisi harga minimum pertama.
Pass 2: Mulai dari elemen ke-k = n,n-1, …, 3, bandingkan L[k] dengan L[k-1].
Pada akhir langkah 2, elemen L[2] berisi harga minimum kedua,larik L[1..2] terurut,
Sedangkan L[3..1] belum terurut.
Pass 3: Mulai dari elemen ke-k = n,n-1, …, 4, bandingkan L[k] dengan L[k-1]. Jika L[k] <
L[k-1], perukaran L[k] dengan L[k-1].
Pada akhir langkah 3, elemen L[3] berisi harga minimum ketiga, larik L[1..3]
Terurut, sedangkan L[4,,n] belum terurut.
Pass n-1: Mulai dari elemen ke-k = n, bandingkan L[k] dengan L[k-1. Jika L[k] < L[k-1]
Pertukaran L[k] dengan L[k-1].
Pada akhir pass n-1, elemen L[n-1] berisi nilai minimm ke-(n-1) dan larik L[1..n-1]
Terrut menaik (elemen yang tersisa adalah L[n], tidak erlu diurut karena hanya
satu-satunya.
Contoh 2.2 : P;engurutan Apung
Tinjau larik L dengan n = 6 buah elemen di bawah ini yang belum terrut. Larik ini akan diurut
menaik: 25 27 10 8 76 21
1 2 3 4 5 6
← arah pembandingan
Pass 1:
K Elemen yang di bandingkan Pertukaran? Hasil Sementara
K = 6 L[6] < L[5]? (21 < 76?) Ya 25,27,10,8,21,76
K = 5 L[5] < L[4]? (21 < 8?) Tidak 25,27,10,8,21,76
K = 4 L[4] < L[3]? (10 < 27?) Ya 25,27,10,8,21,76
K = 3 L[3] < L[2]? (8 < 27?) Ya 25,27,10,8,21,76
K = 2 L[2] < L[2]? (10 < 25?) Ya 25,27,10,8,21,76
Hasil akhir pass 1:
8 25 27 10 21 76
1 2 3 4 5 6
Pass 2: (berdasarkan hasil akhir pass 1)
K Elemen yang di bandingkan Pertukaran? Hasil Sementara
K = 6 L[6] < L[5]? (76 < 21?) Tidak 8,25,27,10,21, 76
K = 5 L[5] < L[4]? (21 < 10?) Tidak 8,25,27,10,21, 76
K = 4 L[4] < L[3]? (10 < 27?) Ya 8,25,27,10,21, 76
K = 3 L[3] < L[2]? (8 < 27?) Ya 8,25,27,10,21,76
Hasil akhir pass 2:
8 10 25 27 21 76
1 2 3 4 5 6
Pass 3: (berdasarkan hasil akhir pass 2)
K Elemen yang di bandingkan Pertukaran? Hasil Sementara
K = 6 L[6] < L[5]? (76 < 21?) Tidak 8,10,25,27, 21, 76
K = 5 L[5] < L[4]? (21 <27?) Ya 8,10,25,27, 21, 76
K = 4 L[4] < L[3]? (21 < 25?) Ya 8,10,25,27, 21, 76
Hasil akhir pass 3:
8 10 21 25 27 76
1 2 3 4 5 6
Pass 4: (berdasarkan hasil akhir pass 3)
K Elemen yang di bandingkan Pertukaran? Hasil Sementara
K = 6 L[6] < L[5]? (76 < 27?) Tidak 8,10,21,25, 27, 76
K = 5 L[5] < L[4]? (27 <25?) Tidak 8,10,21,25, 27, 76
Hasil akhir pass 4:
8 10 21 25 27 76
1 2 3 4 5 6
Pass 5: (berdasarkan hasil akhir pass 4)
K Elemen yang di bandingkan Pertukaran? Hasil Sementara
K = 6 L[6] < L[5]? (76 < 27?) Tidak 8,10,21,25, 27, 76
Hasil akhir pass 5:
8 10 21 25 27 76
1 2 3 4 5 6
Hasil akhir pass 5 menyisakan satu elemen (yaitu 76) yang tidak perlu diurutkan, maka pengurutan
selesai. Larik L sekarang sudah terurut menaik!
Procedure Bubble Sort (input/output L : Larikint, input n : integer)
{Mengurutkan Larik L[1..N] sehingga terurut menaik dengan metode pengurutan apung}
{K.Awal : Elemen Larik L sudah terdefinisi nilai-nilainya.}
{K.Akhir :Elemen Larik L terurut menaik sedemikian sehingga L[1] ≤ …≤ L[n] . }}
DEKLARASI
I : integer {pencacah untuk jumlah langkah}
J: integer {pencacah untuk pengapungan p;ada setia langkah}
Temp : integer {peubah Bantu untuk pertukaran}
ALGORITMA
For i ← 1 to n – 1 do
For k ← n downto i+1 do
If L[k] < L [k-1] then
{Pertukaran L[k] dengan L [k-1]}
Temp ← L[k]
L[k] ← L[k-1]
L[k-1] ← temp
Endif
Endif
Endfor Algoritma 2.2 pengurutan apung (menaik)
Kita dapat menuliskan proses pertukaran (temp ←L[k] , L[k], L[k-1], L[k-1] ← temp) sebagai
sebuah procedure Tukar sebagai berikut:
Procedure Tukar (input/outut a : integer, input/output b : integer )
{Memp;ertukarkan nilai a dan b.
{K. Awal : a dan b sudah terdefinisi nilai-nilainya.
{K.Akhir : b berisi nilai a sebelum pertukaran, dan b berisi nilai a.
Sebelum pertukaran.}
DEKLARASI
Temp : integer {peubah Bantu untuk pertukaran}
ALGORITMA
Temp ← a
a ← b
b ← temp
Algoritma 2.3 Prosedure memp;ertukarkan nilai a dan b.
Dengan manfaat procedure Tukar, algoritma pengurutan apung dapat disederhanakan penulisannya
sebagai berikut:
Procedure Bubble Sort1 (input/output L : Larikint, input n : integer)
{Mengurutkan Larik L[1..n] sehingga terurut menaik dengan metode pengurutan apung}
{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 {pencacah untuk jumlah langkah}
k: integer {pencacah untuk pengapungan pada setiap langkah}
Procedure Tukar (input/output) a: integer, input/output b : integer)
{Mempertukarkan nilai a dan b}
ALGORITMA
For i ← 1 to n – 1 do
For k ← n downto i+1 do
If L[k] < L [k-1] then
{Pertukaran L[k] dengan L [k-1]}
Tukar (L[k], L[k-1]}
L[k] ← L[k-1]
Endif
Endfor
Endfor
Algoritma 2.4 Pengurutan apung (menaik) dengan menggunakan procedure Tukar
Procedure Bubble Sort2 (input/output L : Larikint, input n : integer)
{Mengurutkan Larik L[1..n] sehingga terurut menurun dengan metode pengurutan apung}
{K.Awal : Elemen Larik L sudah terdefinisi nilai-nilainya.}
{K.Akhir :Elemen Larik L terurut menurun sedemikian sehingga L[1] ≥… L[2] ≥.. . ≥L[n].
}}DEKLARASI
I : integer {pencacah untuk jumlah langkah}
k: integer {pencacah untuk pengapungan pada setiap langkah}
Procedure Tukar (input/output) a: integer, input/output b : integer)
{Mempertukarkan nilai a dan b}
ALGORITMA
For i ← 1 to n – 1 do
For k ← n downto i+1 do
If L[k] >L [k-1] then
{Pertukaran L[k] dengan L [k-1]}
Tukar (L[k], L[k-1]}
L[k] ← L[k-1]
Endif
Endfor
Endfor
Algoritma 2.5 Pengurutan apung (menurun):
Komentar Mengenai Pengurutan Apung
Pengurutan apung merupakan metode pengurutan yang tidak mangkus (efficient). Hal ini
disebabkan oleh banyaknya operasi pertukaran yang dilakukan pada setiap langkah pengapungan.
Untuk ukuran larik yang besar, pengurutan dengan metode ini membutuhkan waktu yang lama.
Karena alas an itu, maka metode pengurutan apung jarang digunakan dalam praktek pemograman.
Namun, kelebihan metode ini adalah pada kesederhanaanya sederhana dan mudah dipahami.
Metode Pengurutan Seleksi
Metode pengurutan ini disebut pengurutan seleksi (selection sort) karena gagasan dasarnya adalah
memilih elemen maksimum/minimum dari larik, lalu menempatkan elemen maksimum/minimum
itu pada awal atau akhir larik (elemen terujung) (lihat gambar 2.2. Selanjutnya elemen terujung
tersebut “diisolasi”dan tidak disertakan pada proses selanjutnya. Proses yang sama diulang untuk
elemen yang tersisa. Yaitu memilih elemen maksimum/minimum berikutnya dan
mempertukarkannya dengan elemen terujung larik sisa. Sebagai mana halnya pada algoritma
pengurutan gelembung, prose memilih nilai maksimum/minimum dilakukan pada setiap pass. Jika
larik berukuran n, maka jumlah pass adalah n-1.
Sebelum:
1 n
Belum terurut
Sesudah:
1 n
Belum terurut
Terurut
Gambar 2.2 Bagian larik yang terurut dan belum terurut pada metode pengurutan seleksi.
Ada dua varian algoritma pengurutan seleksi di tinjau dari pemilihan elemen maksimum/minimum
yaitu:
1. Algoritma pengurutan seleksi-maksimum, yaitu memilih elemen maksimum sebagai basis
pengurutan.
2. Algoritma pengurutan seleksi-minimum, yaitu memilih elemen minimum sebagai basis
pengurutan.
Algoritma Pengurutan Seleksi Maksimum
Untuk mendapatkan larik yang terrut menaik, algoritma pemgurutan seleksi-maksimum ditulis
secara garis besar sebagai berikut:
1. Jumlah pass = n-1
2. Untuk setiap pass i= 1,2 …, Jumlah pass lakukan:
cari elemen terbesar (maks) mulai dari elemen ke-1 samp;ai elemen ke-n;
pertukarkan maks dengan elemen ke-n;
kurang n satu (karena elemen ke n sudah terurut).
Rincian aksi pada setiap pass adalah seperti dibawah ini:
Pass 1: Cari elemen maksimum di dalam L[1..n].
Pertukaran elemen maksimum dengan elemen L[n].
Ukuran larik yang belum terurut = n-2.
Pass2: Cari elemen maksimum didalam L[1..n-1].
Pertukarkan elemen maksimum dengan elemen L[n-1].
Ukuran larik yang belum terurut = n-2.
Pass 3: Cari elemen maksimum didalam L[1..n-2].
Pertukarkan elemen maksimum dengan elemen L[n-2].
Ukuran larik yang belum terurut = n-3.
Pass n-1: Tentukan elemen maksimum didalam L[1.. 2].
Pertukarkan elemen maksimum dengan elemen L[n-2].
Ukuran larik yang belum terurut = 1.
Setelah Pass n-1, elemen tersisa adalah L[1], tidak perlu diurutkan karena hanya satu-satuny
Contoh 2.3 : Pengurutan Seleksi-Maksimum
Tinjau larik dengan n =6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut menaik
dengan metode pengurutan seleksi-maksimum:
29 27 10 8 76 21
1 2 3 4 5 6
Pass 1:
Cari elemen maksimum didalam larik L[1..6] =>hasilnya:maks = L[5] = 76
Pertukaran maks dengan L[n],diperoleh:
29 27 10 8 21 76
1 2 3 4 5 6
Pass 2:
(berdasarkan susunan larik hasil pass1)
Cari elemen maksimum di dalam larik L[1..5] => hasilnya: maks = L[1] = 29
Pertukaran Maks dengan L[5], di peroleh:
21 27 10 8 29 76
1 2 3 4 5 6
Pass 3:
(berdasarkan susunan larik hasil pass 2)
Cari elemen maksimum didalam larik L[1..4] => hasilnya: maks =L[2] = 27
Perukarkan maks dengan L[4],diperoleh:
21 8 10 27 29 76
1 2 3 4 5 6
Pass 4:
(berdasarkan susunan larik hasil pass 3)
Cari elemen maksimum di dalam larik L[1..3] => gasilnya: maks = L[1] = 21
Pertukarkan maks dengan L[3], diperoleh:
10 8 21 27 29 76
1 2 3 4 5 6
Pass 5:
(berdasarkan susunan larik hasil pass 4) Cari elemen maksimum di dalam larik L[1..2] => gasilnya: maks = L[1] = 10
Pertukarkan maks dengan L[2], diperoleh:
8 10 21 27 29 76
1 2 3 4 5 6
Tersisa satu elemen (yaitu 8), maka pengurutan selesai. Larik L sudah terurut menaik!
Jadi, pada setiap pass pengurutan terdapat proses mencari harga maksimum dan proses pertukaran
dua buah elemen larik. Ingat, algoritma mencari elemen maksimum sudag pernah kita bicarakan di
dalam Buku 1 (Bab Larik).
Algoritma p;engurutan seleksi-maksimum selengkapnya adalah sebagai berikut:
Procedure Selection Sort 1 (inp;ut/output L : Larikint, input n : integer)
{Mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menaik dengan metode pengurutan
seleksi-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 {pencacah pass}
J : integer {pencacah untuk mencari nilai maksimum}
I maks : integer {indeks yang berisi nilai maksimum sementara}
Maks : integer {elemen maksimum}
Temp : integer {p;eubah Bantu untuk ertukaran}
ALGORITMA
For i ← n downto 2 do {jumlah pass sebanyak n – 1]
{cari elemen maksimum pada elemen L[1..i]} }
I maks ← 1 {elemen pertama diasumsikan sebagai elemen maksimum
sementara}
maks ← l[1] {elemen maksimum}
for j ← 2 to i do
if L[j] > maks then
I maks ← j
Maks ← L[j]
Endif
Endfor
{pertukaran maks dengan L[1]}
Temp ← L[j]
L[I] ← maks
L{maks] ← tem
Endfor
Algoritma 2.6 Pengurutan seleksi-maksimum (menaik)
Perhatikan bahwa pada algoritma Selection Sort 1 diatas kita dapat menghilangkan pengguanaan
peubah maks, karena yang kita perlukan sebenarnya adalah indeks elemen larik yang mengandung
nilai maksimum tersebut. Jika indeks tersebut kita catat maka elemen lariknya dapat diacu melalaui
indeks tersebut. Dengan demikian, algoritme pengurutan seleksi-maksimm dapat dibuat menjadi
lebih elegan sebagai berikut:
Procedure Selection Sort 1 (inp;ut/output L : Larikint, input n : integer)
{Mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menaik dengan metode pengurutan
seleksi-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 {pencacah pass}
J : integer {pencacah untuk mencari nilai maksimum}
I maks : integer {indeks yang berisi nilai maksimum sementara}
Temp : integer {p;eubah Bantu untuk ertukaran}
ALGORITMA
For i ← n downto 2 do {jumlah pass sebanyak n – 1]
{cari elemen maksimum pada elemen L[1..i]} }
I maks ← 1 {elemen pertama diasumsikan sebagai elemen maksimum
sementara}
for j ← 2 to i do
if L[j] > L [I maks] then
I maks ← j
Endif
Endfor
{pertukaran L[i maks] dengan L[i]}
Temp ← L[i]
L[i] ← L[I maks]
L[imaks] ← temp
Endfor
Algoritma 2.7 Pengurutan pilih maksimum tanpa peubah Maks
Untuk seterusnya, pada pencarian elemen maksimum/minimum yang kita catat hanya indeks
elemen larik saja.
Seperti halnya pada pengurutan gelembung, procedure Tukar dapat digunakan untuk mengganti
runtunan aksi pertukaran pada procedure Selection Sort 1 tadi.
Procedure Selection Sort 1 (inp;ut/output L : Larikint, input n : integer)
{Mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menaik dengan metode pengurutan
seleksi-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 {pencacah pass}
J : integer {pencacah untuk mencari nilai maksimum}
I maks : integer {indeks yang berisi nilai maksimum sementara}
ALGORITMA
For i ← n downto 2 do {jumlah pass sebanyak n – 1]
{cari elemen maksimum pada elemen L[1..i] }
I maks ← 1 {elemen pertama diasumsikan sebagai elemen maksimum
sementara}
for j ← 2 to i do
if L[j] > L [I maks] then
I maks ← j
Endif
Endfor
{pertukaran L[i maks] dengan L[i]}
Tukar (L[imaks], L[i])
endfor
Algoritma 2.8 Pengurutan seleksi-maksimum dengan procedure Tukar
Apabila diinginkan larik yang terurut menurun, maka algoritma pengurutan seleksi-maksimum
adalah sebagai berikut:
Untuk setiap pass i = 1,2 …,n-1 lakukan;
1. cari elemen terbesar(maks) mulai dari elemen ke-I sampai elemen ke-n;
2. pertukaran maks dengan elemen ke-I.
Rincian setiap pass adalah sebagai berikut:
Pass ke-1: Cari elemen maksimum di dalam L[1..n].
Pertukaran elemen maksimum dengan elemen L[1]
Pass ke-2: Cari elemen maksimum di dalam L[2..n].
Pertukaran elemen maksimum dengan elemen L[2]
Pass ke-3: Cari elemen maksimum di dalam L[3..n].
Pertukaran elemen maksimum dengan elemen L[3].
Pass n-1: Cari elemen maksimum di dalam L[n-1..n].
Pertukaran elemen maksimum dengan elemen L[n-1].
Ukuran larik yang belum terurut = 1.
Setelah pass n – 1, elemen yang tersisa adalah L[n], tidak perlu diurut karena hanya satu-satunya.
Contoh 2.4 : Pengurutan Seleksi-Minimum Tinjau larik dengan n = 6 buah elemen dibawah ini yang belum terurut. Larik ini akan diurut
menurun dengan metode pengurutan seleksi-maksimum.
29 27 10 8 76 21
1 2 3 4 5 6
Pass 1:
Cari elemen maksimum didalam larik L[1..6] => hasilnya: maks = 5, L[imaks] =76
Pertukarkan L[imaks] dengan L[1],diperoleh:
76 27 10 8 29 21
1 2 3 4 5 6
Pass 2:
(berdasarkan susunan larik hasil pass 1)
Cari elemen maksimum didalam larik L[2..6] => hasilnya: maks = 5, L[imaks] =29
Pertukarkan L[imaks] dengan L[2],diperoleh:
76 29 10 8 27 21
1 2 3 4 5 6
Pass 3:
(berdasarkan susunan larik hasil pass 2)
Cari elemen maksimum didalam larik L[3..6] => hasilnya: maks = 5, L[imaks] =27
Pertukarkan L[imaks] dengan L[3],diperoleh:
76 29 27 8 10 21
1 2 3 4 5 6
Pass 4:
(berdasarkan susunan larik hasil pass 3)
Cari elemen maksimum didalam larik L[4..6] => hasilnya: maks = 6, L[imaks] =21
Pertukarkan L[imaks] dengan L[4],diperoleh:
76 29 27 21 10 8
1 2 3 4 5 6
Pass 5:
(berdasarkan susunan larik hasil pass 4)
Cari elemen maksimum didalam larik L[5..6] => hasilnya: maks = 6, L[imaks] =10 Pertukarkan L[imaks] dengan L[5] (sebenarnya tidak perlu dilakukan sebab 10 sudah berada pada
posisi yang tepat),diperoleh:
76 29 27 21 10 8
1 2 3 4 5 6
Tersisa satu elemen (yaitu 8), maka pengurutan selesai. Larik L sudah terurut menurun!
Procedure Selection Sort 1 (inp;ut/output L : Larikint, input n : integer)
{Mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menurun dengan metode pengurutan
seleksi-maksimum. }
{K.Awal :Elemen larik L sudah terdefinisi nilainya. }
{K.Akhir :Elemen larik L terurut menurun sedemikian sehingga
L[1] ≤ l[2] ≤ …≤ L[n]} }
DEKLARASI
I : integer {pencacah pass}
J : integer {pencacah untuk mencari nilai maksimum}
I maks : integer {indeks yang berisi nilai maksimum sementara}
Procedure Tukar (input/output a : integer, input/output b : integer)
{Mempertukarkan nilai a dan b}
ALGORITMA
For i ← 1 to n-1 do
{cari indeks elemen maksimum maksimum di dalam L[1..n] }
I maks ← i
for j ← I +1 to n do
if L[j] > L [I maks] then
I maks ← j
Endif
Endfor
{pertukaran L[i maks] dengan L[i]}
Tukar (L[imaks], L[i])
Endfor
Algoritma 2.9 Pengurutan Seleksi-Maksimum (menurun)
Algoritma Pengurutan Seleksi-Minimum
Berbeda dengan algoritma pengurutan seleksi-maksimum, maka pada algoritma pengurutan seleksi-
minimum, basis pencarian adalah elemen minimum (terkecil). Elemen minimum ditempatkan
diawal larik (agar larik terurut menaik) atau ditempatkan diakhir larik (agar larik terurut menurun).
Algoritma seleksi-minimum untuk memperoleh larik terurut menaik secara garis besar ditulis
sebagai berikut:
Untuk setiap pass i = 1,2, …,n -1 lakukan
1. cari elemen terbesar(min) mulai dari elemen ke-i sampai elemen ke-n;
2.pertukaran min dengan elemen ke-i.
Rincian setiap pass adalah sebagai berikut:
Pass 1: Cari elemen minimum di dalam L[1..n].
Pertukaran elemen terkecil dengan elemen L[1]
Pass 2: Cari elemen minimum di dalam L[2..n].
Pertukaran elemen terkecil dengan elemen L[2]
Pass 3: Cari elemen minimum di dalam L[3..n].
Pertukaran elemen terkecil dengan elemen L[3].
Pass n-1: Cari elemen minimum di dalam L[n-1..n].
Pertukaran elemen terkecil dengan elemen L[N-1].
(elemen yang tersisa adalah L[n], tidak perlu diurut karena hanya satu-satunya).
Contoh 2.5 : Pengurutan seleksi-Minumum
Tinjau larik dengan n = 6 buah elemen di bawah ini yang belum terurut Larik ini
akan diurut manaik dengan algoritma pengurutan seleksi-minimum:
29 27 10 8 76 21
1 2 3 4 5 6
Pass 1:
Cari elemen terkecil di dalam larik L[1..6]B hasilnya:imin = 4, L[imin] = 8
Pertukaran L[imin] dengan L[1], diperoleh:
8 27 10 29 76 21
1 2 3 4 5 6
Pass 2:
(berdasarkan susunan larik hasil pass 1)
Cari elemen terkecil di dalam larik L[2..6]B hasilnya: imin = 3, L[imin] = 10
Pertukaran L[imin] dengan L[2], diperoleh:
8 10 27 29 76 21
1 2 3 4 5 6
Pass 3:
(berdasarkan susunan larik hasil pass 2)
Cari elemen terkecil di dalam larik L[3..6]B hasilnya: imin = 6,L[imin] = 21
Pertukaran L[imin] dengan L[3], diperoleh:
8 10 21 29 76 27
1 2 3 4 5 6
Pass 4:
(berdasarkan susunan larik hasil pass 3)
Cari elemen terkecil di dalam larik L[4..6]B hasilnya: imin =6,L[imin] = 27
Pertukaran L[imin] dengan L[4], diperoleh:
8 10 21 27 76 29
1 2 3 4 5 6
Pass 5:
(berdasarkan susunan larik hasil pass 4)
Cari elemen terkecil di dalam larik L[5..6]B hasilnya:imin =6,L[imin] = 29
Pertukaran L[imin] dengan L[5], diperoleh:
8 10 21 27 29 76
1 2 3 4 5 6
Tersisa satu elemen (yaitu 76), maka pengurutan selesai. Larik L sudah terurut
Menaik!
Procedure SelectionSort 3 (input/output :L : LarikInt, input n : integer)
{mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menaik dengan
metode pengurutan seleksi – minimum.}
{K. Awal : Elemen larik L sudah terdefinisi nilainya . }
{K. Akhir : Elemen larik L terurut menaik sedemikian sehingga
L [1] ≤ L [2] ≤ … ≤ L [n] }
DEKLARASI
i : integer { pencacah pass}
j : integer ( pencacah untuk mencari nilai maksimum}
imin : integer { indeks yang berisi nilai maksimum sementara}
procedure Tukar (input/output a : integer, input/output b : integer)
{ Mempertukarkan nilai a dan b}
ALGORITMA
for i I 1 to n- 1 do
{cari indeks dari elemen minimum di dalam larik L [I..N]}
imin I i
for j I i + 1 to n do
if L[j] < L [imin] then imin I j
endif
endfor
{pertukaran L[imin] dengan L[i] }
Tukar (L[imin], L[i])
endfor
Algoritma 2.10 Pengurutan seleksi-minimum (menaik)
Apabila diinginkan elemen-elemen larik berurut menurun, maka algoritma
pengurutan seleksi-minimum adalah sebagai berikut:
procedure SelectionSort4 (input/output L : LarikInt, input n: integer)
{mengurutkan elemen-elemen larik L[1..n] sehingga tersusun menurun
dengan metode pengurutan seleksi – minimum.}
{ K. Awal : Elemen larik L sudah terdenifinisi nilainya.}
{ K. Akhir : Elemen larik L terurut menurun sedemikian sehingga
L[1] ≥ L[2] ≥ … ≥ L[n] }
DEKLARASI
i : integer { pencacah pass}
j : integer ( pencacah untuk mencari nilai maksimum}
imin : integer { indeks yang berisi nilai maksimum sementara}
procedure Tukar (input/output a: integer, input/output b : integer)
{ Mempertukarkan nilai a dan b}
ALGORITMA
for i I n downto 2 do {jumlah pass sebanyak n – 1 kali}
{cari elemen terkecil di dalam L[1. .i]}
imin I 1
for j I 2 to I do
if L [j] < L [imin] then
imin I L[l]
endif
endfor
{pertukaran L[imin] dengan L[i]}
Tukar (L[imin] , L[i]) ;
endfor
Algoritma 2.11 Pengurutan seleksi-minimum (menurun)
Contoh 2.6 : Pengurutan Seleksi-Minimum (menurun)
Tinjau larik dengan n = 6 buah elemen di bawah ini yang belum terurut. Larik ini
akan diurut menurun dengan pengurutan seleksi-minimum:
29 27 10 8 76 21
1 2 3 4 5 6
Pass 1:
Cari elemen terkecil di dalam larik L[1..6] B imin = 4, L[imin] = 8
Pertukaran L[imin] dengan L[n], diperoleh:
29 27 10 21 76 8
1 2 3 4 5 6
Pass 2:
(berdasarkan susunan larik hasil pass 1)
Cari elemen terkecil di dalam larik L[1..5] B imin = 3, L[imin] = 10
Pertukaran L[imin] dengan L[n],diperoleh:
29 27 76 21 10 8
1 2 3 4 5 6
Pass 3:
(berdasarkan susunan larik hasil pass 2)
Cari elemen terkecil di dalam larik L[1..4] B imin = 4, L[imin] = 21
Pertukaran L[imin] dengan L[4] (sebenarnya tidak perlu dilakukan, karena 21
sudah berada pada posisi yang tepat) diperoleh:
29 27 76 21 10 8
1 2 3 4 5 6
Pass 4:
(berdasarkan susunan larik hasil pass 3)
Cari elemen minimum di dalam larik L[1..3] B imin =2, L[imin] = 27
Pertukaran L[imin] dengan L[3], diperoleh:
29 76 27 21 10 8
1 2 3 4 5 6
Pass 5:
(berdasarkan susunan larik hasil pass 4)
Cari elemen minimum di dalam larik L[1..2] B imin =1, L[imin] = 29 Pertukaran L[imin] dengan L[2], diperoleh:
76 29 27 21 10 8
1 2 3 4 5 6
Tersisa satu elemen (yaitu 76), maka pengurutan selesai. Larik L sudah terurut
Menurun!
Komentar Mengenai Metode Pengurutan Seleksi
Dibanding dengan metode pengurutan apung, metode pengurutan seleksi
memiliki kinerja yang lebih baik. Alasannya, operasi pertukaran elemen hanya
dilakukan sekali saja pada setiap pass, dengan demikian lama pengurutannya
berkurang dibandingkan dengan metode gelembung.
2.5 Metode Penguruan Sisipan
Dari namanya, pengurutan sisipan (insertion sort) adalah metode pengurutan
Dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi
yang tepat dilakukan dengan menyisir larik.Selama penyisiran dilakukuan pergeseran larik. Metode
pengurutan sisip cocok untuk persoalan menyisipkan elemen baru kedalam sekumpulun elemen
yang sudah terurut.
Alogaritma pengurutan sisipan untuk pengurutan menaik
Untuk mendapatkan larik yang terurut menaik,alogaritma pengurutan sisipan secara garis besar
ditulis sebagai berikut:
Untuk setiap pass i = 2, …,n lakukan:
1. y I L[i]
2. sisipkan y pada tempat yang sesuai antara L[1] … L[i]
Rincian setiap pass adalah sebagai berikut:
Asumsikan: L[1] dianggap sudah pada tempatnya
Pass2: Elemen y = L[2] harus dicari tempatnya yang tepat di dalam
L[1..2] dengan cara menggeser elemen L[1..1] ke kanan (atau ke
bawah, jika anda membayangkan larik terentang vertikal) bila
L[1..1] lebih besar daripada L[2]. Misalkan posisi yang tepat
adalah k. Sisipkan L[2] pada L[k].
Pass3: Elemen y = L[3] harus di cari tempatnya yang tepat di dalam
L[1..3] dengan cara menggeser elemen L[1..2] ke kanan (atau ke
bawah) bila L[1..2] lebih besar daripada L[3]. Misalkan posisi yang
tepat adalah k. Sisipkan L[3] pada L[k].
Pass n: Elemen y = L[n] harus di cari tempatnya yang tepat di dalam
L[1..n] dengan cara menggeser elemen L[1..n - 1] ke kanan (atau
Ke bawah) bila L[1..n-1] lebih besar daripada L[n]. Misalkan posisi
Yang tepat adalah k. Sisipkan L[n] pada L[k].
Hasil dari Pass n: Larik L[1..n] sudah terurut menaik, yaitu L[1] ≤ L[2] ≤ … ≤
L[n].
Contoh 2.7 :Pengurutan Sisipan (menaik)
Tinjau larik dengan n = 6 buah elemen di bawah ini yang belum terurut. Larik ini
Akan diurutkan menaik dengan metode pengurutan sisispan:
29 27 10 8 76 21
1 2 3 4 5 6
Asumsikan : Elemen y = L[1] = 29dianggap sudah terurut.
29 27 10 8 76 21
1 2 3 4 5 6
Pass 2:
(berdsarkan susunan larik pada akhir pass 1)
Cari posisi yang tepat untuk y = L[2] = 27 di dalam L[1..2],diperoleh:
27 29 10 8 76 21
1 2 3 4 5 6
Pass 3:
(berdasarkan susunan larik pada akhir pass2)
Cari posisi yang tepat untuk y =L[3]= 10 di dalam L[1..3],diperoleh:
10 27 29 8 76 21
1 2 3 4 5 6
Pass 4:
(berdasarkan susunan larik pada akhir pass3)
Cari posisi yang tepat untuk y =L[4] = 8 di dalam L[1..4], diperoleh:
8 10 27 29 76 21
1 2 3 4 5 6
Pass 5:
(berdasarkan susunsn larik pada akhir pass 4)
Cari posisi yang tepat untuk y =L[5] = 76 di dalam L[1..5],diperoleh:
8 10 27 29 76 21
1 2 3 4 5 6
Pass 6:
(berdasarkan susunan larik pada akhir pass 5)
Cari posisi yang tepat untuk y =L[6] = 21 di dalam L[1..6],diperoleh:
8 10 21 27 29 76
1 2 3 4 5 6
Alogaritma pengurutan sisipan selengkapnya adalah sebagai berikut:
procedure insertionSort1 (input/output L : LarikInt, input n : integer)
{mengurutkan elemen elemen larik L[1..n] sehingga tersusun menaik dengan
metode pengurutan sisipan. }
{ k.Awal : Elemen - elemen larik L sudah terdefinisi nilainya.}
{ k. Akhir : Elemen - elemen larik L terurut menaik sedemikian sehingga.
L[1] ≤ L [2] ≤ L[n] }
DEKLARASI
i : integer { pencacah pass}
j : integer { pencacah untuk penelusuran larik}
y : integer { peubah bantu agar L[k] tidak ditimpa selama
pergeseran}
ketemu : boolean { untuk menyatakan pisisi penyisipan ditemukan}
ALGORITMA: { elemen L[1] dianggap sudah terurut } for i I 2 to n do {mulai dari pass 2 sampai pass N }
y I L[i]
{ cari posisi yang tepat untuk y di dalam L[1..i-1] sambil
Menggeser}
j I i – 1
ketemu I false
while ( j ≥ 1 ) and (not ketemu) do
if y < L[j] then
L [j + 1] I L[j] {geser}
j I j – 1
else
ketemuItrue
endif
endwhile
{ j < 1 or ketemu }
L [j+1] I y {sisipkan y pada tempat yang sesuai }
endfor
Algoritma 2.12 Pengurutan sisip (menaik)
Algoritma Pengurutan Sisipan Untuk Pengurutan Menurun
Algoritma penurutan sisipan untuk memperoleh elemen larik yang terurut
menurun adalah seperti berikut ini:
procedure insertionSort2 (input/output L : LarikInt, input n : integer)
{mengurutkan elemen larik L[1..n] sehingga tersusun menurun dengan
metode pengurutan sisipan. }
{ k.Awal : Elemen - elemen larik L sudah terdefinisi nilainya.
{ k. Akhir : Elemen - elemen larik L terurut menaik sedemikian sehingga.
L[1] ≤ L [2] ≤ L[n] }
DEKLARASI
i : integer { pencacah pass}
j : integer { pencacah untuk penelusuran larik}
y : integer { peubah bantu agar L[k] tidak ditimpa selama
pergeseran}
ketemu : boolean { untuk menyatakan pisisi penyisipan ditemukan}
ALGORITMA:
{ elemen L[1] dianggap sudah terurut }
for i I 2 to n do {mulai dari langkah 2 sampai langkah n }
y I L[i]
{ cari posisi yang tepat untuk y di dalam L[1..i-1] sambil
Menggeser}
j I i – 1
ketemu I false
while ( j ≥ 1 ) and (not ketemu) do
if y > L[j] then
L [j + 1] I L[j] {geser}
J I j – 1
else
ketemuItrue
endif
endwhile
{ j < 1 or ketemu }
L [j+1] I y {sisipkan y pada tempat yang sesuai }
endfor
Algoritma 2.13 Pengurutan sisip (menurun)
Komentar Mengenai Metode Pengurutan Sisipan
Kelemahan metode pengurutan sisipan terletak pada banyaknya operasi
pergeseran yang diperlukan dalam mencarian posisi yang tepat untuk elemen larik.
Pada setiap pass I, operasi pergeseran yang diperlukan maksimim i-1 kali. Untuk
larik yang berukuran besar, jumlah operasi pergeseran meningkat secara
kuadratik, sehoingga penguratan sisip kurang untuk volume data yang
besar.
2.6 Metode Pengurutan Shell
Metode pengurutan shell di beri nama sesuai nama penemunya (Donald Shell tahun
1959) [PAR95]. Metode ini merupakan perbaikan terhadap metode pengurutan
sisipan. Kelemahan metode pengurutan sisipan sudah disebutkan pada
bagian sebelum ini di atas. Jika data pada posisi ke-1000 ternyata posisi yang
tepat adalah sebagai elemen kedua, maka dibutuhkan kira-kira 998 kali
pergeseran elemen.
Untuk mengurangi pergeseran terlalu jauh, kita mengurutkan larik setiap k elemen
dengan metode pengurutan sisip, misalkan kita urutkan setiap k elemen ( k kita
namakan juga step atau increment). Selanjutnya, kita gunakan nilai step yang
lebih kecil, misalnya k = 3, lalu kita urut setiap 3 elemen. Begitu seterusnya
sampai nilai k = 1. karena nilai step selalu berkurang maka metode pengurutan
shell kadang-kadang dinamakan juga metode pengurutan kenaikan yang
berkurang (diminishing increment sort)
Contoh 2.8 : Pengurutan Shell
Untuk memperjelas metode pengurutan Shell, tinjau pengurutan data integer
berikut:
Data sebelum pengurutan
81 94 11 96 12 35 17 95 28 58 41 75 15
1 2 3 4 5 6 7 8 9 10 11 12 13
Pass 1 (step = 5):Urutkan setiap lima elemen
81 94 11 96 12 35 17 95 28 58 41 75 15
1 2 3 4 5 6 7 8 9 10 11 12 13
│ │ │
35……………………………41……………………………...81
17………………………………75…………………………….94
11……………………………..15…………………………….95
28……………………………..96
Baris pertama menyatakan elemen yang sudah terurut pada 1, 6, dan 11.
Baris kedua menyatakan elemen yang terurut pada posisi 2, 7, dan 12
Baris ketiga menyatakan elemen yang terurut pada posisi 3, 9, dan 13
Baris keempat menyatakan elemen yang terurut pada posisi 4 dan 9
Hasil pass pertama: 35, 17, 11, 28, 12, 41, 75, 15, 96, 58, 81, 94, 95
Pass 1 (step = 3): Urutkan setiap tiga elemen
35 17 11 28 12 41 75 15 96 58 81 94 95
1 2 3 4 5 6 7 8 9 10 11 12 13
│ │ │ │ │
28………………..35……………….58………………..75…………… ….95
12…………………15……………….17…………………81
11………………..41…………………94………………96
Hasil kedua pass:28, 12, 11, 35, 15, 41, 58, 17, 94, 75, 81, 96, 95
Pass 3 (step = 1):Urutkan setiap satu elemen
35 17 11 28 12 41 75 15 96 58 81 95 95 1 2 3 4 5 6 7 8 9 10 11 12 13
│ │ │ │ │ │ │ │ │ │ │ │ │
11 12 15 17 28 35 41 58 75 81 94 95 96
Hasil pass ketiga: 11, 12, 15, 17, 28, 35, 41, 58, 75, 81, 94, 95, 96
Perhatikanlah bahwa pada pass yang terakhir (step = 1), pengurutan Shell
Menjadi sama dengan pengurutan sisipan biasa.
Nilai-nilai step seperti 5, 3, dan 1 bukanlah angka “sihir” (magic). Kita dapat
memilih nilai-nilai step yang lain bukan kelipatan dari step yang lain.
Pemilihan step yang merupakan perpangkatan dari dua (seperti 8, 4, 2, 1) dapat
mengakibatkan perbandingan elemen yang sama pada suatu pass akan terulang
kembali pada pass berikutnya. Meskipun beberapa penelitian telah dibuat pada
metode Shell, namun tidak seorang pun yang dapat membuktikan bahwa
pemilihan step tertentu paling bagus di antara pemilihan step yang lain [KRU91].
Secara garis besar, algoritma pengurutan Shell dituliskan sebagai berikut:
1. step I n { n
2. While step > 1 do
a. step I step div 3 + 1
b. For i I 1 to step do
Insertion Sort setiap elemen ke-step mulai dari elemen ke-i
Algoritma pengurutan Shell dibuat dengan pertama-tama memodifikasi algoritma
pengurutan sisipan sedemikian sehingga kita dapat menspesifikasikan titik awal
pengurutan dan ukuran step (pada algoritma pengurutan sisipan yang asli, titik
awal pengurutan adalah elemen pertama dan ukuran step = 1). Modifikasi
algoritma pengurutan sisip ini kita beri nama InsSort. Algoritma InsSort dan
ShellSort selengkapnya kita tulis berikut ini.
procedure InsertionSort (input/output L : LarikInt, input n, star,
step : integer)
{mengurutkan elemen larik L[star ..n] sehingga tersusun menaik dengan
metode pengurutan sisipan yang dimodifikasikan untuk Shell Sort. }
{ k.Awal : Elemen - elemen larik L sudah terdefinisi nilainya. }
{ k. Akhir : Elemen - elemen larik pada kenaikan sebesar step terurut menaik}
DEKLARASI
i : integer { pencacah step}
j : integer { pencacah untuk penelusuran larik}
y : integer { peubah bantu yang menyimpan nilai L[k]}
ketemu : boolean { untuk menyatakan pisisi penyisipan ditemukan}
ALGORITMA
{ elemen L [start] dianggap sudah terurut }
i I star + step
while i ≤ n do
y I L[i]
{ sisipkan L[i] ke dalam bagian yang sudah terurut }
{ cari posisi yang tepat untuk y di dalam L[start ..i-1] sambil
menggeser}
j I i – step
ketemuIfalse
while ( j ≥ 1 ) and (not ketemu) do
if y > L[j] then
L [j + step] I L[j]
j I j – step
else
ketemu I true
endif
endwhile
{ j < 1 or ketemu }
L [j + step] I y {sisipkan y pada tempat yang sesuai }
i I i + step
endwhile
Algoritma 2.14 Modifikasi pengurutan sisip untuk pengurutan Shell
Perhatikan Algoritma 2.14 di atas, jika star = 1 dan step = 1, maka algoritma
InsSort menjadi sama dengan algoritma pengurutan sisipan biasa
procedure ShellSort (input/output L : 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}
DEKLARASI
step, star : integer
DESKRIPSI
step I n
while step > 1 do
step I step div 3 + 1
for start I 1 to step do
InsSort (L, n, start, step)
endfor
endwhile
Algoritma 2.15 Pengurutan Shell
Komentar Mengenai Metode Pengurutan Shell
Sebagaimana sudah dijelaskan sebelumnya, metode pengurutan Shell merupakan
perbaikan terhadap metode pengurutan sisipan. Namun, tidak seorangpun yang
pernah dapat menganalisis metode pengurutan Shell secara tepat, karena
pemilihan ukuran step (seperti 5, 3, 1, atau pendefinisian ukuran step dengan
pernyataan step I step div 3 + 1) dudasarkan pada pertimbangan sugesti.
tidak ada aturanyang diketahui untuk menemukan ukuran step yamg optimum.
Jika step dipilih yang berdekatan, semakin banyak jumlah pass yang dihasilkan,
tapi setiap pass mungkin lebih cepat. Jika ukuran step menurun dengan cepat,
jumlah pass akan berkurang tetapi setiap pass menjadi lebih panjang (lama).
Manun yang pasti, ukuran step terakhir adalah 1, sehingga pada akhir proses,
larik diurutkan dengan pengurutan sisipan biasa.
2.7 Penggabungkan Dua Buah Larik Terurut
Misalkan kita memiliki dua buah larik, L1 dan L2, yang masing-masing sudah
terurut menaik. Kita ingin membentuk sebuah larik baru, L3, yang merupakan
gabungan dari dua buah larik tersebut sedemikian sehingga L3 juga terurut
menaik.
Contoh 2.9 : Penggabungan dua buah larik terurut
Misalkan elemen-elemen larik L1 dan L2 masing-masing adalah
Larik L1: Larik L2:
Penghubungan L1 dan L2 menghasilkan L3 yang tepat terurut menaik:
Larik L3:
2152730 1 13 24 1 2 13 15 24 27 30
Proses penghubungan duikerjakan dengan cara menbandingkan satu elemen pada
larik L1 dengan satu elemen pada larik L2. Jika elemen pada L1 lebih dari
elemen pada L2, maka salin elemen dari L1 ke L3. elemen berikutnya pada L1
maju satu elemen, sedangkan elemen L1 tetap. Hal yang sama juga berlaku bila
elemen dari L2 lebih kecil dari elemen L1, maka salin elemen dari L2 ke L3. Larik
L2 maju satu elemen, larik L1 tetap. Dengan cara seperti ini, akan ada larik yang
elemennya sudah duluan habis disalin, sedangkan larik yang lain masih tersisa.
Salin seluruh elemen yang tersisa ke L3.
Hal lain yang harus diperhatikan adalah ukuran larik L3. Jumlah elemen larik L3
adalah banyaknya elemen larik /l1 ditambah dengan banyaknya elemen larik L2.
jumlah elemen larik /l3 ini harus lebih kecil dari jumlah maksimim elemen larik
yang disediakan (Nmaks)
Penggabungan L1 dan L2 pada Contoh 2.9 dilaksanakan sebagai berikut
L1 L3
1 13 24 2 15 27 30 1 < 2→ 11
1 13 24 2 15 27 30 2<13 →212
1 13 24 2 15 27 30 13 < 15 →13 1 2 13
113 24 2 15 27 30 15<24→15 1 2 13 15
113 24 215 27 30 24<27→24 1 2 13 15 24
11324 215 27 30 27→ 1 2 13 15 24 27
1 13 24 2 15 27 30 30→ 1 2 13 15 24 27 30
L2
Algoritma penggabungan dua buah larik terurut selengkapnya adalah sebagai
berikut:
procedure TableMerge (input L1 : LarikInt, input n1 : integer,
input L2 : LarikInt, input n2 : integer,
output L3 : LarikInt, output n3 : integer)
{ Penggabungan dua buah larik terurut, L1 dan L2, menghasilakan larik baru
L3 yang terurut menaik. }
{ K. Awal :Larik L1{1..n1] sudah terdefisi elemen-elemennya dan terurut
menaik. Larik L2[1..n2] sudah terdefinisi elemen-elemennya dan
terurut menaik. }
{ K. Akhir :Larik L3[1..n3] berisi hasil penggabungan larik L1 dan larik L2
dan elemen-elemenya terurut menaik. n3 = n1 + n2 adalah ukuran
larik L3. }
DEKLARASI
k1, k2, k3 : integer
Algoritma:
n3 I n1 + n2 {ukuran larik L3}
k1 I 1
k2 I 1
k3 I 1
while (k1 ≤ n1) and (k2 ≤ n2) do
if L1 [k1] ≤ L2 [k2] then
L3[k3] I L1 [k1]
k1 I k1 + 1 { L1 maju satu elemen}
else
L3 [k3] I L2 [k2]
k2 I k2 + 1 { L2 maju satu elemen}
endif
k3 I k3 + 1
endwhile
{ k1 > n1 or k2 > n2 }
{ salin sisa L1, jika ada}
while (k1 ≤ n1) do
L3 [k3] I L1 [k1]
k1 I k1 + 1
k3 I k3 + 1 endwhile
{ k1 > n1 }
{ salin sisa L2, jika ada }
while (k2 ≤ n2) do
L3 [k3] I L2 [k2]
k2 I k2 + 1
k3 I k3 + 1
end
{ k2 > n2}
Algoritma 2.16 Penggabungan dua buah larik terurut
2.8 Pengurutan pada Larik Terstruktur
Metode pengurutan yang dibahas sebelum ini menggunakan larik dengan
elemen-elemen bertipe sederhana. Pada kebanyakan kasus, elemen larik sering
bertipe terstruktur. Contoh , misalkan TabMhs adalah sebuah larik yang
elemenya menyatakan nilai ujian seorang mahasiswa untuk suatu mata kuliah
(MK) yang ia ambil. Data setiap mahasiswa adalah NIM (Nomor Induk
Mahasiswa), nama mahasiswa, mata kuliah yang ia ambil, dan nilai mata kuliah
tersebut. Deklarasi nama tipe adalah sebagai berikut:
DEKLARASI
const Nmaks = 100
type Mahasiswa : record <Nim : integer {Nomor Induk Mahasiswa}
NamaMhs : string, {nama mahasiswa}
KodeMk : string, { kode mata kuliah }
Nilai : char { indeks nilai MK (A/B/C/D/E) _
>
type TabMhs : array [1..Nmaks] of Mahasiswa
M : TabMhs
Algoritma 2.17 Deklarasi larik terstruktur
Struktur lojik larik M ditunjukan pada Gambar 1.2 di dalam Bab 1. Pada proses
entry data mahasiswa, data dimasukkan secara acak (tidak terurut berdasarkan
NIM). Kita dapat mengurutkan sekumpulan data mahasiswa tersebut dengan
metode pengurutan yang sudah dibicarakan di atas.
Procedure berikut menggunakan metode pengurutan pilih maksimum untuk
mengurutkan sekumpulan data mahasiswa berdasarkan kunci NIM.
procedure ShellDataMhs (input/output M : TabMhs, input n : integer}
{mengurutkan elemen larik M[1..n] sehingga tersusun menaik dengan metode pengurutan pilih
maksimum. }
{ k.Awal : Elemen - elemen larik M sudah terdefinisi. }
{ k. Akhir : Elemen - elemen larik M terurut menaik sedemikian sehingga
M[1] ≤ M[2] ≤ … ≤ M[n] }
DEKLARASI
i : integer { pencacah pass}
j : integer { pencacah untuk mencari nilai maksimum}
imaks : integer { indeks yang berisi nilai maksimum sementara}
procedure Tukar (input/output a : Mahasiswa,
input/output b: Mahasiswa)
{ Mempertemukan elemen a dan b }
ALGORITMA
for i I n downto 2 do {jumlah pass sebanyak n – 1}
{cari NIM terbesar pada elemen M[1..i]}
imaksI 1 { elemen pertama diasumsikan sebagai elemen
terbesar sementara }
for j I 2 to i do
if M[j] . NIM > M [imaks] .NIM then
imaks I j
endif endfor
{pertukaran M[imaks] dengan M[i]}
Tukar (M[imaks], M[i])
endfor
Algoritma 2.18 Pengurutan larik terstruktur
Procedure Tukar:
procedure Tukar (input/output a : Mahasiswa}
input/output b : Mahasiswa}
{ mempertukar niali a dan b.
{ k.Awal : a dan b sudah terdefinisi nilai-nilainya. }
{ k. Akhir : b berisi nilai a sebelum pertukaran, dan b berisi nilai a
Sebelum pertukaran. }
DEKLARASI
temp : Mahasiswa { peubah bantu untuk pertukaran }
ALGORITMA
temp I a
a I b
b I temp
Algoritma 2.19 Prosedur Tukar
2.9 Algoritma Pengurutan dalam Bahasa PASCAL
dan Bahasa C
Dengan asumsi bahwa pembaca sudah memahami konversi dari notasi algoritmik
ke notasi bahasa PASCAL dan bahasa C (liat Buku 1), di bawah ini disajikan algoritma pengurutan yang telah dikemukakan di atas dalam kedua bahasa’
tersebut
PASCAL
(* DEKLARASI nama *)
const Nmaks = 1000; {jumlah elemen larik}
type LarikInt = array [1..NMaks] of integer;
1.Metode Pengurutan Apung
Procedure BubleSort1 (var L : LarikInt; n : integer)
{ Mengurutkan larik L[1..n] sehingga terurut menaik dengan metode
pengurutan gelembung. }
{ K. Awal : Elemen larik L sudah terdefinisi. }
{ K. Akhir : Elemen larik L terurut menaik sedemikian sehingga
L [1] <= L[2] < … <= L [n]
var
i : integer; { pencacah untuk jumlah langka}
k : integer; { pencacah, untuk pengapungan pada setiap langkah }
temp : integer; { peubah bantu untuk pertukaran }
begin
for i : = 1 to n – 1 do
for k := n downto I + 1 do
if L[k] < L [k-1] then
begin
{ pertukaran L[k] dengan L[k-1] }
temp : = L[k]
L [k] : = L [ k-1] ;
L [ k-1] : = temp ;
end; {if} { endfor }
{ endfor }
end ;
2. Metode Pengurutan Seleksi – Maksimum
procedure SelectionSort1 (var L : LarikInt; n : integer) ;
{ Mengurutkan elemen larik L [1….n] sehingga tersusun menaik dengan metode pengurutan seleksi
maksium }
{ K.Awal : Elemen larik L sudah terdefinisi harganya }
{ K.Akhir : Elemen larik L sudah menaik sedemikian sehingga }
L[1] < = …… < = L[n] }
var
i : integer ; { pencacah untuk jumlah langkah }
j : integer ; { pencacah untuk mencari nilai maksimum }
imaks : integer ; { indeks yang berisi nilai maksimum sementara }
temp : integer ; { peubah bantu untuk pertukaran }
begin
for i : = n downto 2 do { jumlah pass sebanyak n – 1 }
begin
{ cari elemen maksimum pada elemen L[1…i] }
imaks : = 1; { elemen pertama diasumsikan sebagai elemen maksimum
sementara }
for j := 2 to i do
if L[j] > L[maks] then
imaks : = j;
{end if}
{endfor}
{ pertukarkan L[imaks] dengan L[i] }
temp : = L[imaks] ;
L[imaks] : = L[i]
L[i] : = temp;
end; {for}
end;
3. Metode Pengurutan Seleksi-Minimum
procedure SelectionSort3 (var L : LarikInt; n : integer) ;
{ Mengurutkan elemen larik L [1….N] sehingga tersusun menaik dengan metode pengurutan seleksi-
minimum }
{ K.Awal : Elemen larik L sudah terdefinisi nilainya }
{ K.Akhir : Elemen larik L terurut menaik sedemikian sehingga }
L[1] ≤ L[2] ≤ …< = L[n] }
var
i : integer ; { pencacah pass }
j : integer ; { pencacah untuk mencari nilai maksimum }
imin : integer ; { indeks yang berisi nilai maksimum sementara }
temp : integer ; { peubah bantu untuk pertukaran }
begin
for i : = 1 to n – 1 do
begin
{ cari indeks dari elemen minimum di dalam larik L[1…i] }
imin : = 1;
for j := 1 to n – 1 do
if L[j] < L[imin] then
imin : = j;
{end if}
{endfor}
{ pertukarkan L[imin] dengan L[i] }
temp : = L[imaks] ;
L[imin] : = L[i]
L[i] : = temp;
end;
end;
4. Metode Pengurutan Sisipan procedure InsertionSort1 (var L : LarikInt; n : integer) ;
{ Mengurutkan elemen larik L [1….n] sehingga tersusun menaik dengan metode pengurutan sisipan }
{ K.Awal : Elemen larik L sudah terdefinisi nilaianya }
{ K.Akhir : Elemen larik L sudah menaik sedemikian sehingga }
L[1] ≤ L[2] ≤ …… ≤ L[n] }
var
i : integer ; { pencacah pass }
j : integer ; { pencacah untuk penelusuran larik }
y : integer ; { peubah bantu agar L[K] tidak ditimpa selama pergeseran }
ketemu : boolean ; { peubah Boolean untuk menyatakan posisi penyisipan di
ditemukan }
begin
{ elemen L[1] dianggap sudah terutut }
for i : = 2 to n do { mulai dari langkah 2 sampai langkah n }
begin
{ 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
begin
if y < L[j] then
begin
if y < L[j] then
begin
L[j + 1] : = l[j];
j : = j – 1;
end
else
ketemu : = true;
end; {while}
{ j < 1 or ketemu }
L[j+1] : = y; { sisipkan y pada tempat yang sesuai }
end; {for}
end;
5. Metode Pengurutan Shell
procedure ShellSort1 (var L : LarikInt; n : integer) ;
{ Mengurutkan elemen larik L [1….n] sehingga tersusun menaik dengan metode pengurutan shell }
{ K.Awal : Elemen-elemen larik L sudah terdefinisi nilaianya }
{ K.Akhir : Elemen-elemen larik L terurut menaik sedemikian sehingga }
L[1] ≤ L[2] ≤ …… ≤ L[n] }
var
step, start : integer ;
begin
step : n;
while step > 1 do
begin
step : = step div 3 + 1;
for start : = 1 to step do
InsSort (L, N, start, step);
{endfor}
end; {while}
end;
procedure InsSort1 (var L : LarikInt; n, start, step : integer) ;
{ Mengurutkan elemen larik L [start….n] sehingga tersusun menaik dengan metode pengurutan sisip
yang dimodifikasi untuk shell sort }
{ K.Awal : Elemen-elemen larik L sudah terdefinisi nilaianya }
{ K.Akhir : Elemen-elemen larik pada kenaikan sebesar step terurut menaik }
var
i : integer ; { pencacah pass }
j : integer ; { pencacah untuk penelusuran larik }
y : integer ; { peubah bantu agar yang menyiapkan nilai L[i] }
ketemu : boolean ; { peubah Boolean untuk menyatakan posisi penyisipan di
ditemukan }
begin
{ elemen L[start] dianggap sudah terurut }
i : = start + step
while i <= n do
begin
y : = L[i]; { sisipkan L[i] ke dalam bagian yang sudah terurut }
{cari posisi yang tepat untuk y di dalam L[start…I-1] sambil menggeser}
j : = 1 – step;
ketemu := false ;
while (j >= 1) and (not ketemu) do
begin
if y < L[j] then
begin
L[j + step] : = L[j];
j : = j – step
end
else
ketemu : = true;
{end if}
end; {while}
{ j < 1 or ketemu }
L[j + step] : = y; {sisipkan y pada tempat yang sesuai}
i : = i + step ;
end; {while}
C
/* DEKLARASI nama */
#define Nmaks 1000; /* jumlah elemen larik */
Typedef int LarikInt [Nmaks + 1]
1. Metode Pengurutan Apung
void BubbleSort1 {Larik L, int n)
/* Mengurutkan larik L[1…n] sehingga terurut menaik dengan metode pengurutan
/* K.Awal : Elemen larik L sudah terdefinisi */
/* K.Akhir : Elemen larik L terurut menaik sedemikian sehingga
L[1] <= L[2] < ….< = L[n] */
{
int i; */ pencacah untuk jumlah angka */
int k; */ pencacah untuk pengapungan pada setiap langkah */
int temp; */ peubah bantu untuk pertukaran */
for (i = 1; i < = n – 1; i ++)
for (k = n; k >= i + 1; k --)
if (L[k] < L[k–1] )
{
*/ pertukarkan L[k] dengan L[k-1] */
temp = L[k];
L[k] = L [k-1];
L[k-1] = temp;
}
*/ endfor */
*/ endfor */
}
2. Metode Pengurutan Seleksi-Maksimum
void SelectionSort1 {LarikInt L, int n)
/* Mengurutkan elemen larik L[1…n] sehingga tersusun menaik dengan menggunakan 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] */
{
int i; */ pencacah untuk jumlah angka */
int j; */ pencacah untuk mencari nilai maksimum */
int imaks; */ indeks yang berisi nilai maksimum sementara */
int temp; */ peubah bantu untuk pertukaran */
for (i = n; i >= 2; i--) /* jumlah pass sebanyak n – 1 */
{
*/ cari elemen maksimum pada elemen L[1…i] */
imaks = 1; */ elemen pertama diasumsikan sebagai elemen maksimum sementara */
for (j = 2; j >= i; j++)
if (L[j]} > L [imaks])
imaks = j;
*/endif*/
*/endfor*/
/* pertukarkan L[imaks] dengan L[i] */
temp = L[imaks];
L[imaks] = L[i];
L[i] = temp;
}
}
3. Metode Pengurutan Seleksi-Minumum
void SelectionSort3 {LarikInt L, int n)
/* Mengurutkan elemen larik L[1…n] sehingga tersusun menaik dengan menggunakan metode
pengurutan pilih minimum */
/* K.Awal : Elemen larik L sudah terdefinisi nilainya */
/* K.Akhir : Elemen larik L terurut menaik sedemikian sehingga
L[1] ≤ L[2] < ….< = L[n] */
{ int i; */ integer pass */
int j; */ pencacah untuk mencari nilai maksimum */
int imin; */ indeks yang berisi nilai maksimum sementara */
int temp; */ peubah bantu untuk pertukaran */
for (i = 1; i <= n-1; i++)
{
*/ cari indeks dari elemen minimum di dalam larik L[I…n] */
imin = 1;
for (j = i+1; j <= n; j++)
if (L[j]} > L [imin])
imin = j;
*/endif*/
*/endfor*/
/* pertukarkan L[imin] dengan L[i] */
temp = L[imin];
L[imin] = L[i];
L[i] = temp;
}
}
4. Metode Pengurutan Sisipan
void InsertionSort1 {LarikInt L, int n)
/* Mengurutkan elemen larik L[1…n] sehingga tersusun menaik dengan menggunakan metode
pengurutan sisipan */
/* K.Awal : Elemen-elemen larik L sudah terdefinisi nilainya */
/* K.Akhir : Elemen-elemen larik L terurut menaik sedemikian sehingga
L[1] ≤ L[2] ≤ ….≤ = L[n] */
{
int i; */ pencacah pass */
int j; */ pencacah untuk penelusuran larik */
int y; */ peubah bantu agar L[i] tidak ditimpa selama pergeseran */
boolean ketemu; */ peubah boolean untuk menyatakan posisi penyisipan ditemukan */
*/ elemen L[1] dianggap sudah terurut */
for (i = 2; i <= n; i++) */ mulai dari langkah 2 sampai n */
{
*/ sisipkan L[i] ke dalam bagian yang sudah terurut */
y = L[i];
*/ cari posisi yang tepat untuk x di dalam L[1…i-1] sambil menggeser */
j = 1 – 1;
ketemu = false;
while (j >= 1) && (!ketemu)
{
if (y < L[j] )
{
L[j+1] = L[j];
j--;
}
else
ketemu = true;
}
*/ j < 1 or ketemu */
L[j+1] = y; */ sisipkan y pada tempat yang sesuai */
}
}
5. Metode Pengurutan Shell
void ShellSort (LarikInt L, int n) ;
*/ Mengurutkan elemen larik L [1….n] sehingga tersusun menaik dengan
metode pengurutan shell */
*/ K.Awal : Elemen-elemen larik L sudah terdefinisi nilaianya */
*/ K.Akhir : Elemen-elemen larik L terurut menaik sedemikian sehingga
L[1] ≤ L[2] ≤ …… ≤ L[n] */
{
int step, start;
step = n;
while (step > 1)
{
step = step/3 + 1;
for (start = 1; start <= step; start++)
InsSort (L, n, start, step);
*/ endfor */
} */ while */
}
void InsSort (LarikInt L; int n, int start, int step) ;
*/ Mengurutkan elemen larik L [start….n] sehingga tersusun menaik dengan metode pengurutan
sisip yang dimodifikasi untuk shell sort */
*/ K.Awal : Elemen-elemen larik L sudah terdefinisi nilaianya */
*/ K.Akhir : Elemen-elemen larik pada kenaikan sebesar step terurut menaik */
{
typedef enum {true = 1, false = 0} boolean; */ tipe boolean */
int i; */ pencacah step */
int j; */ pencacah untuk penelusuran larik */
int y; */ peubah bantu agar yang menyimpan nilai L[i] */
boolean ketemu; */ peubah Boolean untuk menyatakan posisi penyisipan ditemukan */
*/ elemen L[start] dianggap sudah terurut */
i = start + step;
while (i <= n)
{
y : = L[i]; */ sisipkan L[i] ke dalam bagian yang sudah terurut */
*/ cari posisi yang tepat untuk y di dalam L[start…I-1] sambil menggeser */
j = 1 – step;
ketemu = false ;
while (j >= 1 && ! ketemu)
{
if (y < L[j] )
{
L[j + step] = L[j]; */ geser */
j = j – step
}
else
ketemu = true;
*/end if*/
{ */while*/
*/ j < 1 or ketemu */
L[j + step] = y; */ sisipkan y pada tempat yang sesuai */
i = i + step ;
} {while}
}
MODUL
PENCARIAN
I. Pencarian
Pencarian atau (searching) merupakan proses yang fundamental dalam
pengolahan data.proses pencarian adalah menemukan nilai (data) atau bertipe
bentukan).Di dalam buku 1 Algoritma dan pemograman telah disebutkan bahwa
aktivitas yang berkaitan dengan pengolahan data sering di dahului dengan proses
pencarian.sebagai contoh,untuk mengunah(update) data tertentu,langkah pertama
yang harus dilakukan adalah mencari keberadaan data tersebut didalam
kumpulannya.Jika data yang dicari ditemukan,maka data tersebut dapat diubah
nilainya dengan data yang baru.
Aktivitas awal yang sama juga dilakukan pada proses penambahan (insert)data
baru.proses penambahan data dimulai apakah data yang akan di ditambahakan sudah
terdapat dikumpulan.jika sudah ada dan mengasumsikan tidak boleh ada duplikasi
data maka data tersebut tidak boleh ditambahkan,tetapi jika belum ada,maka
tambahkan.
Data dapat disimpan secara temporer dalam memori utama atau disimpan
secara permanen didalam memori sekunder (tape atau disk). Di dalam memori
utama,struktur penyimpanan data yang umum adalah berupa larik atau table ( array),
sedangkan didalam memori sekunder berupa arsip (file). Bab 1 ini dititikberatkan
pada algoritma pencarian data didalam larik.Algoritma pencarian yang akan
dibicarakan dimulai dengan Algoritma pencarian yang paling sederhana ( yaitu
pencarian beruntun atau sequential search ) sampai pada Algoritma pencarian yang
lebih maju yaitu pencarian bagi dua ( binary search ).
1.1 Tinjauan Singkat Larik
Di dalam Buku 1 kita sudah membicarakan mengenal larik atau table. Untuk
menygarkan ingatan,upabab 1.1 ini meninjau ( review ) kembali secara singkat
mengenai larik Larik merupakan tipe data terstruktur.
Sebuah larik dapat dibayangkan sebagai sekumpulan kotak yang menyimpan
sekumpulan elemen yang bertipe sama secara berturutan ( sequential ) didalam memori computer ( didalam gambar 1.1 elemen - elemen larik disusun horizontal.
Anda juga dapat membayangkan elemen – elemen larik disusun secara vertical
sehingga dinamai table). Setiap elemen larik data diacu melalui indeksnya. Karena
elemen disimpan secara berturutan,indeks larik haruslah suatu tipe yang juga
mempunyai suatu keterurutan ( memiliki suksesor dan ada predesor ),misalnya tipe
integer atau karakter. Jika indeksnya adalah integer maka kerurutan indeks sesuai
dengan urutan karakter. Tiap elemen larik langsung diakses dengan menspesifikasikan
nama larik berikut dengan indeksnya.
Untuk contoh –contoh larik pada gambar 1.1 kita mendefinisikan nama dan
tipenya di bagian deklarasi dari Algoritma sebagai berikut:
Deklarasi
D : array[1…11] of integer { larik pada gambar 1.1(a) }
Kar : array[1…8] of character { larik pada gambar 1.1(b) }
Const n = 5 {jumlah data siswa }
Type Data = record <nama:String, Usia : Integer>
Siswa : array[1..n] of Data { larik pada gambar 1.1 (c)}
Algoritma 1.1 Contoh pendeklarasian larik
(a) D
(b) kar
( c) Siswa
21 36 8 7 10 36 68 32 12 10 36
K M T A F M * #
1 Ali 18
2 Tono 24
3 Amir 30
4 Tuti 21
5 Yani 22
Gambar 1.1 ( a) Larik bertipe integer
(b) Larik bertipe karakter
(c) Larik bertipe struktur
Anka 1,2,3,………menyatakan indeks lariks
Contoh – contoh cara mengacu elemen larik pada gambar 1.1 :
D [2]
D [k] {mengacu elemen ke-k,dengan syarat k sudah terdefinisi nilainya}
Kar[5]
Siswa [1].Nama
Siswa [1]..Usia
Siswa [j].Nama { mengacu elemen ke-j,dengan syarat j sudah terdefinisi nilainya }
Di dalam Buku 1 telah dijelaskan beberapa proses sekunsial terhadap
larik.Proses sekuensial terhadap larik anatara lain menginisialisasi larik,mengisi
elemen – elemen larik dengan data dari piranti masukan.Menuliskan elemen –elemen
larik ke piranti tentu di dalam larik keluaran.mencari elemen maksimum atau
minimum, serta mencari elemne tertentu di dalam larik.
Di dalam buku 2 ini, Algoritma pencarian elemen tertentu didalam larik akan
dibahas lebih mendalam.Karena larik adalah struktur internal ( yaitu,struktur yang
direalisasikan di dalam memori utama ).maka pencarian elemen utama di dalama larik
di sebut juga pencarian internal. Sedangkan pada pencarian eksternal,pencarian
dilakukan pada sekumpulan data yang disimpam di dalam memori sekunder seperti
tape atau disk. Penyimpana data di dalam storage bersipat permanent dengan tujuan
data agar dapat di baca kembali untuk pemrosesan lebih lanjut. Bab 1 ini hanya
membicarakan pencarian internal saja. Metode pencarian eksternal di luar bahasan
buku ini.
1.2 Persoalan pencarian
Pertma tama kita spesifikasikan persoalan pencarian elemen di dalam larik. Di dalam
bab ini kita mendefinikasikan persoalan pencarian sebagai berikut :
Persoalan ( umum )
Di berikan larik L yang sudah terdefinisi elemen – elemennya, dan x adalah elemen
yang bertipe sama dengan elemen larik L . Carilah x di dalam larik L.
Hasil atau keluaran dari hasil persoalan pencarian dapat bermacam – macam
bergantung pada spesifikasi (spek) rinci dari persoalan tersebut,misalnya :
a) Pencarian hanya untuk memeriksa keadaan x. Keluaran yang diinginkan
misalnya pesan (messege) bahwa x ditemukan atau tidak di temukan di dalam
larik.
Contoh 1.1 : keluaran hasil pencarian berupa pesan
write ( x, ‘ditemukan!’) atau
write ( x, ‘ tidak ditemukan!’)
b) Hasil pencarian adalah indeks elemen larik. Jika x ditemukan,maka indeks
elemen
Larik tempat x berada disikan kedalam idx. Jika x tidak terdapat di dalam larik
L
Maka idx diisi dengan harga khusus,misalnya -1.
Contoh 1.2 : keluaran hasil pencarian berupa indeks larik
Perhatikan larik pada gambar 1.1(a).
Misalkan x = 68, maka idx = 7, dan bila x = 100 ,maka idx = -1
C) Hasil pencarian adlah sebuah nilai Boolean yang menyatakan status hasil Pencarian . jika x ditemukan ,maka sebuah peubah bertipe Boolean,
misalnya ketemu ,disis dengan nilai true sebaiknya “ketemu” diisi dengan
nilai false . hasil pencarian ini selanjutnya disimpulkan pada bagian
pemanggilan prosedur.
Contoh 1.3 : keluaran hasil pencarian berupa nilai Boolean
Perhatikan larik pada gambar 1.1(a)
Misalnya x = 68.maka ketemu = true, dan bila x = 10 0,maka ketemu = false.
Untuk kedua macam keluaran b dan c di atas kita ,kita mengkonsultasi hasil
pencarian setelah proses pencarian selesai dilakukan,bergantung pada kebutuhan
misalnya menampilkan bahwa x ditemukan ( atau tidak ditemukan ) atau
memanipulasi nilai x.
Contoh 1.4 konsultasi hasil pencarian
1) if ketemu then { artinya ketemu atau = true }
write ( x, ‘tidak ditemukan ‘)
else
write ( x, ‘ditemukan’)
endif
2) if idx ≠ -1 then {berarti x ditemukan }
L [idx ] ← L [idx] = 1 { manipulasi nilai x }
edif
Hal lain yang harus diperjelas dalam perspesifikasi persoalan pencarain adalah
mengenai duplikasi data. Apabila x yang di cari lebih dari satu banyaknya didalam
larik L, maka hanya x yang pertama kali di temukan saja dan diacu dan pencarian
Algoritma selesai. Sebagai contoh, larik pada gambar 1.1 (a) memiliki tga buah nilai
36. Bila x = 36, maka Algoritma pencarian selseai ketika x ditemukan pada elemen
ke- 2 dan menghsilkan idx = 2 ( atau menghsilkan ketemu = true jika mengacu pada
pengeluaran pencarian jenis b ). Elemen 36 lainnya tidak dipertimbangkan lagi.
Metode pencarian yang akan di bahas di dalam Bab ini adalah :
1. Metode pencarian beruntun ( sequential search )
2. Metode pencarian bagi dua ( binary search ).
Untuk masing – masing Algoritma dari kedua metode pencarian di atas,larik
yang digunakan deklarasikan di dalam bagian deklarasi global seperti di bawah ini.
Larik L adalah bertipe Larikint.
{ kamus data global }
Deklarasi
const Nmaks = 100 { junlah maksimum elemen larik }
type larikint = array [1….Nmaks] of integer
Algoritma 1.2 deklarasi larik integer yang digunakan di dalam bab ini
1.3 metode pencarian beruntun
Di dalam buku 1 kita telah mempelajari metode pencarian yang paling
sederhana ,yaitu metode paencarian beruntun ( sequntial search ). Di dalam bab ini
kita kemukakan kembali metode pencarian beruntun.Nama lain metode pencarian
beruntun adalah pencarian lurus ( linear search ).
Pada dasarnya, metode pencarian beruntun adalah proses membandingkan setipa
elemen larik satu persatu secara beruntun,mulai dari elemen pertama,sampai elemen
pertama di temukan,atau seluruh elemen sudah diperiksa.
Contoh 1.5 : pencarian pada sebuah larik
Perhatikan larik L di bawah ini dengan n = 6 elemen:
13 16 14 21 76 15
Misalkan nilai yang dicari adalah : x = 21
Elemen yang di bandingkan { berturut-turut } : 13,16,14,21 { ditemukan}
Indeks larik yang dikembalikan : id x = 4
Misalkan nilai yang dicari adalah : x= 13
Elemen yang di bandingkan { berturut-turut } :13 { ditemukan }
Indeks larik yang dikembalikan : id x = 1
Misalkan nilai yang dicari adalah : x= 15
Elemen yang di bandingkan { berturut-turut } :13,16,14,21,76,21 {tidak
ditemuka
n }
Indeks larik yang dikembalikan : id x = -1
Terdapat dua versi algoritma pencarian beruntun. Pada algoritma versi
pertama, aksi pembandingan dilakukan di awal pengulangan,tepatnya pada kondisi
pengulangan,sedangkan algoritma versi kedua,aksi pembandingan dilakukan di dalam
badan pengulangan.Versi pertama tidak menggunakan peubah Boolean dalam proses
pencarian,sedangkan proses kedua menggunakan peubah Boolean. UNtuk masing –
masing versi kita tuliskan dua macam algoritmanya berdasarkan hasil yang diinginkan
: indeks larik atau nilai boolean. selain itu,kita asumsikan jumlah elemen di dalam
larik adlah n buah.
(a) Versi 1 ( Pembandingan elemene dilakukan di awal pengulangan )
1.Hasil pencarian : sebuah peubah boolean yang bernilai true bila x di
temukan atau bernilai false bila x tidak di temukan.
Setipa elemen larik L dibandingkan dengan x mulai dari elemen pertama ,L [1].
Aksi perbandingan dilakukan selam indeks larik i belum melebihi n dan L[i]
tidaksama dengan x. Aksi perbandingan dihentikan bila L [i] = x atau I = n . Elemen
terakhir,L [ n] ,diperiksa secara khusus.keluaran yang dihasilkan oleh porsedure pencarian adalah sebuah peubah Boolean ( missal nama peubahnya ketemu ) yang
bernilai true jika x ditemukan,atau bernilai false jika x tidak ditemukan.
Algoritma pencarian beruntun versi 1 untuk kategori hasil berupa nilai Boolean
dapat kita tulis sebagai prosedur atau sebagai fungsi.
(i) Prosedur pncarian beruntun:
procedure seqSearch1 (input L : LarikIntInt, input n : integer,
input x : integer, output ketemu : boolean)
{ Mencari keberadaan nila 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
i : integer { pencatat indeks larik }
ALGORITMA
i ←1
while ( i < n ) and ( L[i] ≠ x ) do
i ←i + 1
endwhile
{ i = n or L[i] = x }
if L[i] = x then {x ditemukan }
ketemu ← true
else
ketemu ← false { x tidak ada dalam larik L}
endif
(ii) Fungsi pencarian beruntun
function seqSearch1 (input L : LarikInt, input n : integer,
input x : integer) ← Boolean
{ Mengembalikan nilai true jka x ditemukan di dalam larik L[1..n], atau
nilai false jika x tidak ditemukan. }
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
i← 1
while ( i < n ) and (L [i] ≠ x ) do
i← i + 1
endwhile
{ i = n or L[i] = x }
if L[i] = x then { x ditemukan }
return true
else
return false
endif
Perhatikan bahwa pada algoritma SeqSearch1 di atas, pembandingan x dengan
elemen larik dilakukan di awal (bagian kondisional) kalang while-do. Apabila elemen
larik yang ke-i tidak sama dengan x dan i belum sama dengan n, aktivitas
pembandingan diteruskan ke elemen berikutnya (i← i + 1).
Pembandingan dihentikan apabila L[i] = x atau indeks i sudah mencapai akhir
larik (i=n). perhatikan juga bahwa jika i sudah mencapai akhir larik, eleman terakhir
ini belum dibandingkan dengan x. pembndingan elemen terakhir dilakukan bersama-
sama dengan penyimpulan hasil pencarian. Hasil pencarian disimpulkan di luar
kalang while-do dengan pernyataan if (L[i] = x) then…
Pernyataan if-then ini juga sekaligus memeriksa apakah elemen terakhir, L[n], sama
dengan x. jadi, pada algoritma SeqSearch1 di atas, elemen terakhir diperiksa secara
khusus.
Procedure SeqSearch1 dapat dipanggil dari program utama atau dari prosedur
lain. Missal kita asumsikan prosedur SeqSearch1 dipanggil dari program utama.
Misalkan program utama bertujuan untuk memeriksa keberadaan x di dalam larik.
Jika x terdapat di dalam larik maka ditampilkan pesan “ditemukan!”, sebaliknya jika x
tidak terdapat di dalam larik maka ditampilkan pewsan “tidak ditemukan!”.
Contoh program utama yang memanggil procedure SeqSearch1:
PROGRAM Pencarian
{ Program untuk mencari nilai di dalam larik }
DEKLARASI
const Nmaks = 100 { jumlah maksimum elemen larik }
type LarikInt : array [1..Nmaks] of integer
L : LarikInt
x : integer { elemen yang dicari }
found : boolean { true jika x ditemukan, false jika tidak }
n : integer { ukuran larik }
procedure Baca Larik ( output L : LarikInt, input n : integer )
{ Mengisi elemen larik L[1..n] dengan nilai yang dibaca dari piranti
masukan }
procedure SeqSearch1 (input L : LarikInt, input n : integer, input x : integer,
output ketemu : boolean )
{ Mencari keberadaan nilai x di dalam larik L[1..n]. }
ALGORITMA
read (n) { tentukan banyaknya elemen larik }
BacaLarik (L, n) { baca elemen-elemen larik L }
read (x) { baca nilai yang dicari }
SeqSearch1 (L, n, x, found) {cari} if sound then { found = true }
write ( x, ‘ ditemukan ! ‘ )
else
write ( x, ‘ tidak ditemukan ! ‘ )
endif
prosedur BacaLarik yang disebabkan di dalam program utama di atas algoritmanya
adalah seperti di bawah ini:
procedure BacaLarik (output L : LarikInt, input n : integer )
{ Mengisi elemen larik L[1..n] dengan nilai yang dibaca dari piranti masukan. }
{ K.Awal : larik L belum terdefinisi elemen-elemennya, n sudah berisi jumlah elemen
efektif, n diasumsikn tidak lebih besar dari ukuran maksimum larik (Nmaks). }
{ K.Akhir : setelah pembacaan, sebanyak n buah elemen larik L berisi nilai-nilai yang
dibaca dari piranti masukan }
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
for i← 1 to n do
read (L[i])
endfor
Untuk pencarian beruntun yang berupa fungsi, contoh cara pemanggilan fungsi
SeqSearch1:
read (x)
if not SeqSearch1 (L, n, x) then
write (x, ‘ tidak ditemukan ! ‘ )
else
{ proses terhadap x }
endif 2. Hasil pencarian: indeks elemen larik yang mengandung nilai x.
Algoritma pencarian beruntun versi 1 untuk kategori hasil berupa indeks elemen larik
dapat kita tulis sebagai prosedur atau sebagai berikut:
(i) Prosedur pencarian beruntun
procedure SeqSearch2 (input L : larik, input n : integer, input x : integer, output idx :
integer)
{ Mencari keberadaan nilai x di dalam larik L[1..n] }
{ K.Awal : x dan elemen-elemen larik L[1..n] sudah terdefinisi. }
{ K.Akhir : idx berisi indeks larik L yang berisi nilai x. jika x tidak ditemukan, maka
idx diisi dengan nilai -1. }
DEKLARASI
i : integer
ALGORITMA
i←1
While (I < n) and (L[i]) ≠ x) do
i← i + 1
Endwhile
{ I = n or L[i] = x }
if L[i] = x then {x ditemukan}
idx← i
else
idx← -1
endif
(ii) Fungsi pencarian beruntun:
function SeqSearch2 (input L: larik, input n : integer, input x : integer) → integer
{ Mengembalikan indeks larik L[1..n] yang berisi x. Jika x tidak ditemukan, maka
indeks yang dikembalikan adalah -1.}
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
i←1
while (i < n) and (L[i] ≠ x) do
i←i + 1
endwhile
{i = n or L[i] = x}
if L[i] = x then { x ditemukan }
return i
else
return -1
endif
Misalkan program yang memanggil prosedur SeqSearch2 bertujuan untuk
menambahkan (append) nilai x ke dalam larik, namun sebelum penambahan itu harus
ditentukan apakah x sudah terdapat di dalam larik. Jika x belum terdapat di dalam
larik, maka x ditambahkan pada elemen ke-n+1. karena itu kita harus memastikan
bahwa penambahan satu elemen baru tidak melampaui ukuran maksimum larik
(Nmaks). Setelah penambahan elemen baru ukuran larik efektif menjadi n+1.
PROGRAM TambahElemenLarik
{ Program untuk menambahkan elemen baru pada ke dalam larik. Elemen baru
dibaca dari pirnti masukan, lalu dicari apakah sudah terdapat di dalam larik. Jika
belum ada, tambahkn elemen baru setelah elemen terakhir. }
DEKLARASI
Const Nmaks = 100 { jumlah maksimum elemen larik }
Type LarikInt : array [1..Nmaks] of integer
L : LarikInt
N : integer { untuk larik L } X : integer { elemen yang akan dicari }
Idx : integer { mencatat indeks elemen larik yang berisi x }
Procedure BacaLarik (output L : LarikInt, input n : integer, input x : integer,
output idx : integer)
{ Mencari keberadaan nilai x di dalam larik L[1..n] }
ALGORITMA
Read (n) { tentukan banyaknya elemen larik }
BacaLarik (L, n) { baca elemen-elemen larik L }
Read (x)
SeqSearch2 (L, n, x, idx) { cri x sebelum ditambahkan ke dalam L }
If idx ≠ -1 then
Write (x, ‘ sudah terdapat di dalam larik’ )
else { x belum terdapat di dalam larik L, tambahkan x pada posisi ke-n+1 }
n ← n + 1 { naikkan ukuran larik }
L[n] ← x { sisipkan x }
Endif
Untuk pencarian beruntun yang berupa fungsi, contoh cara pemanggilan fungsi
SeqSearch2:
Read(x)
Idx ← SeqSearch2 (L, n, x)
If idx = -1 then
Write (x, ‘ tdak ditemukan ! ‘ )
Else
{ instruksi manipulasi terhadap L[idx] }
…
endif
(b) Versi 2 ( Pembandingan elemen dilakukan di dalam badan pengulangan )
Pada versi yang kedua ini, aksi pembandingan dilakukan di dalam badan pengulangan
( jadi bukan di awal pengulangan seperti pada varian pertama). Untuk itu, kita
memerlukan sebuah peubah boolen yang akan berfungsi untuk menyatakan apakah x
sudah ditemukan. Misalkan peubah tersebut bernama ketemu yang pada mulanya diisi
nilai false. Bila x ditemukan pada elemen ke-i, yaitu L[i] = x, maka ketemu diisi
dengan nilai true. Pengulangan dihentikan bila ketemu = true. Hasil pencarian
disimpulkan di luar badan pengulangan.
Algoritma pencarian beruntun versi 2 lebih elegan dibandingkan dengan algoritma
versi 1 karena semua elemen dibandingkan dengan cara yang sama. Algoritma
pencariannya kita buat dua macam, yang pertama untuk hasil pencarian berupa
peubah Boolean, dan algoritmakedua untuk hasila pencarian berupa indeks elemen
larik.
1. Hasil pencarian : sebuah peubah Boolean yang bernilai true bila x ditemukan
atau bernilai false bila x tidak ditemukan.
Pada versi ini, peubah Boolean ketemu diinisialisasi dengan nilai false dan indeks
larrik i diisi dengan 1 (karena pembandingan dimulai dari elemen pertama). Setiap
elemen L dibandingkan dengan x mulai dari elemen pertama. Jika L[i] sama dengan
x, peubah ketemu diisi nilai true dan pengulangan dihentikan. Sebaliknya, jika L[i]
tidak sama dengan x, pembandingan dilanjutkn untuk elemen berikutnya (i← i + 1).
Pada versi 2 ini, setiap elemen larik, termasuk elemen terakhir, diperiksa dengan cara
yang sama. Keluaran yang dihasilkan adalah nilai yang disimpan di dalam peubah
ketemu.
Algoritma pencarian beruntun versi 2 untuk kategori hasil berupa nilai Boolean dapat
kita tulis sebagai prosedur atau sebagai fungsi.
(i) Prosedur pencarian beruntun:
procedure SeqSearch3 (input L : LarikInt, input n : integer, input x : integer, output
ketemu : boolean)
{ Mencari keberadaan nilai x di dalam larik L[1..n] }
{ K.Awal : nilai x, n, dan elemen larik L[1..n] sudah terdefinisi. }
{ K.Akhir : ketemu bernilai true jika x ditemukan. Jik x tidak ditemukan, ketemu
bernilai false. }
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
i←1
Ketemu←false
While (i ≤ n ) and ( not ketemu ) do
if L[i] = x then
Ketemu←true
Else
i←i+ 1
Endif
Endwhile
{ i > n or ketemu }
(ii) Fungsi pencarian beruntun:
function SeqSearch3 ( input L : LarikInt, input n : integer, input x : integer ) →
Boolean
{ Mengembalikan nilai true jika x ditemukan di dalam larik L[1..n]. jika x tidak
ditemukan, nilai yang dikembalikan adalah false. )
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
i← 1
Ketemu←false
While (i ≤ n ) and (not ketemu) do
If L[i] = x then Ketemu←true
Else
i←i + 1
Endif
Endwhile
{ I > n or ketemu }
return ketemu
2. Hasil pencarian: indeks elemen larik yang mengandung nilai x.
Algoritmanyasama seperti SeqSearch3 di atas, hanya saja setelah kalang while-do
ditambahkan pernyataan if-then untuk memberikan hasil pencarian berupa indeks
elemen larik (idx) yang berisi nilai x. Jika x tidak ditemukan maka idx diisi nilai -1.
Algoritma pencarian beruntun versi 2 untuk kategori hasil berupa indeks elemen larik
dapat kita tulis sebagai prosedur atau sebagai fungsi.
(i) Prosedur pencarian beruntun:
procedure SeqSearch4 (input L : LarikInt, input n : integer, input x : integer, output
idx: integer)
Mencari keberadaan nilai x di dalam larik L[1..n] }
{ K.Awal : nilai x, n, dan elemen larik L[1..n] sudah terdefinisi. }
{ K.Akhir : idx berisi indekslarikL tempat x berada. Jika x tidak ditemukan, maka idx
bernilai -1.}
DEKLARASI
i : integer { pencatat indeks larik }
ketemu : Boolean {true bila x ditemukan, false bila tdak}
ALGORITMA
i← 1
Ketemu←false
While (i ≤ n ) and (not ketemu) do
If L[i] = x then Ketemu←true
Else
i←i + 1
Endif
Endwhile
{ i > n or ketemu }
if ketemu then { x ditemukan }
idx ←i
else
idx ← -1
endif
(i) Fungsi pencarian beruntun:
function SeqSearch4 ( input L : LarikInt, input n : integer, input x : integer ) →
integer
{ Mengembalikan nilai true jika x ditemukan di dalam larik L[1..n]. jika x tidak
ditemukan, nilai yang dikembalikan adalah -1e. )
DEKLARASI
i : integer { pencatat indeks larik }
ketemu : Boolean {true bila x ditemukan, false bila tidak }
ALGORITMA
i← 1
Ketemu←false
While (i * n ) and (not ketemu) do
If L[i] = x then
Ketemu←true
Else
i←i + 1
Endif
Endwhile
{ i > n or ketemu }
if ketemu then { x ditemukan }
return i else { x tidak ditemukan }
return -1
endif
Kinerja Metode Pencarian Beruntun
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, yng
berarti jumlah perbandingan yang terjadi sebanyak n kali. Kita katakana bahwa waktu
pencarian dengan algoritma pencarian beruntun sebanding dengan n. bayangkan bila
larik berukuran 100.000 buah elemen, maka kita harus melakukan perbandingan
sebanyak 100.000 buah elemen. Andaikan satu operasi perbandingan elemen larik
membutuhkan waktu 0.01 detik, maka untuk 100.000 buah perbandingan diperlukan
waktu sebesar 1000 detik atau 16.7 menit. Semakin banyak elemen larik, semakin
lama pula waktu pencariannya. Karena itulah metoda pencarian beruntun tidak bagus
untuk volume data yang besar.
Metode pencarian Beruntun Pada Larik Terurut
Larik yang elemen-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 elemen-elemen
larik adalah seragam atau uniform) hanya dibutuhkan rata-rata n/2 kali perbandingan.
Hal ini karena pada laik yang terurut kita dapat segera menyimpulkan bahwa x tidak
terdapat di dalam larik bila ditemukan elemen larik yang lebih besar dari x (pada larik
yang terurut menaik) [TEN86].
CONTOH 1.6: Pencarian pada larik terurut
(a) Diberikan larik L tidak terurut:
13 16 14 21 76 15
1 2 3 4 5 6
Maka, untuk mencari 15, dibutuhkan perbandingan sebanyak 6
kali.
(b) Misalkan larik L di atas sudah diurut menaik:
maka, untuk mencari 15, dibutuhkan perbandingan hanya 3 kali
(secara rata-rata).
Prosedur SeqSearch7 berikut adalah algoritma pencarian beruntun pada larik yang
terurut menaik, yang mana merupakan modifikasi dari algoritma SeqSearch1 dengan
perubahan pada ekspresi kondisi L[i] * x menjadi L[i] < x.
procedure SeqSearch7 (input L : LarikInt, input n : integer, input x : integer, output
idx: integer)
{Mencari keberadaan nilai x di dalam larik L[1..n]yang elemen-elemennya sudah
terurut menaik }
{ K.Awal : nilai x, dan elemen-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
i : integer { pencatat indeks larik }
ALGORITMA
i← 1
While (i < n ) and (L[I ] < x ) do
i←i + 1
Endwhile
{ i =N or L[i] = x }
if L[i] = x then { x ditemukan }
idx ←i
13 14 15 16 21 76
1 2 3 4 5 6
else
idx ← -1
endif
Metode Pencarian Beruntun dengan Sentinel
Jika pencarian bertujuan untuk menambahkan elemen terakhir larik, maka terdapat
sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x yang akan
dicari sengaja ditambahkan terlebih dahulu pada elemen ke-n+1. data yang
ditambahkan setelah elemen terakhir larik ini disebut sentinel. Selanjutnya, pencarian
beruntun ilakukan di dalam larik L[1..n+1]. Akibatnya, proses pencarian selalu
menjamin bahwa x pasti berhasil ditemukan. Untuk menyimpulkan apakah x
ditemukan pada elemen sentinel atau bukan, kita dapat mengetahuinya dengan
melihat nilai idx. Jika idx = n +1 (yang berarti x ditemukan pada elemen sentinel),
maka hal itu berarti bahwa x tidak terdapat di dalam larik L semula (sebelum
penambahan sentinel). Keuntungannya, elemen sentinel otomatis sudah menjadi
elemen yang ditambahkan ke dalam larik. Sebaliknya, jika idx < n + 1 (yang berarti x
ditemukan sebelum sentinel), maka hal itu berarti bahwa x sudah ada di dalam larik L
semula.
Contoh 1.7 : Pencarian beruntun dengan menggunakan sentinel
(a) x=18
←sentinel
1 2 3 4 5 n=6 7
18 ditemukan pada elemen ke-n+1. sentinel otomatis sudah
ditambahkan ke dalam larik. Ukuran larik sekarang = 7.
(b) x=21
←sentinel
1 2 3 4 5 N=6 7
13 16 14 21 76 15 18
13 16 14 21 76 15 2121 ditemukan pada elemen ke-5. sentinel batal menjadi elemen yang
ditambahkan ke dalam larik. Ukuran larik tetap 6.]
Algoritma pencarian beruntun dengan sentinel kita tuliskan sebagai berikut:
procedure SeqSearchWithSentinel (input L : LarikInt, input n : integer, input x :
integer, output idx: integer)
{Mencari keberadaan nilai x di dalam larik L[1..n] dengan menggunakan sentinel }
{ K.Awal : nilai x, dan elemen-elemen larik L[1..n] sudah terdefinisi nilainya. }
{ K.Akhir : idx berisi indeks larik L yang berisi nilai x. Jika x tidak ditemukan, maka
idx diisi dengan nilai -1.}
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
L[n + 1] ← x { sentinel }
i ← 1
While (L[I ] ≠ x ) do
i←i + 1
Endwhile
{ L[i] = x } { pencarian selalu berhasil menemukan x }
{ Kita harus menyimpulkan apakah x ditemukan pada elemen sentinel
atau bukan }
if idx = n + 1 then { x ditemukan pada elemen sentinel }
idx ← -1 { berarti x belum ada pada larik L semula }
else { x ditemukan pada indeks < n + 1 }
idx ← i
endif
Program utama yang memanggil prosedur SeqSearchWithSentinel kira-kira
algoritmanya sebagai berikut:
ALGORITMA
… { instruksi-instruksi sebelumnya}
read (x)
SeqSearchWithSentinel (L, n, x, idx)
If idx ≠ -1 then
Write ( x, ‘ sudah terdapat di dalam larik’ )
Else ( x belum terdapat di dalam larik L semula, sentinel otomatis menjadi elemen
yang ke-n+1.)
n ← n + 1 { Naikkan ukuran efektif larik }
endif
1.4 Metode Pencarian Bagidua
Pencarian pada data yang terurut menunjukan kinerja yang lebih baik daripada
pencarian data yang belum terurut. Hal ini sudah kita bicarakan pada metode
pencarian beruntun untuk dat yang sudah terurut. Data yang terurut banyak ditemukan
dalam kehidupan sehari-hari. Data nomor telepon di dalam buku telepon misalnya,
sudah terurut berdasarkan nama/instansi pelanggan telepon dari A sampai Z. Data
karyawan diurut berdasarkan nomor induknya dari nomor kecil ke nomor besar. Data
mahasiswa diurut berdasarkan NIM (Nomor Induk Mahasiswa), kata-kat (entry) di
dalam kamus bahasa Inggris/Indonesia telah terurut dari A sampai Z, dan sebagainya.
Terdapat metode pencarian pada data terurut yang paling mangkus (efficient), yaitu
metode pencarian bagidua atau pencarian biner (binary search). Metode ini
digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Sebenarnya, dalam
kehidupan sehari-hari kita sering menerapkan pencarian bagidua. Untuk mencari arti
kata tertentu di dalam kamus (misalnya kamus Bahasa Inggris), kita tidak membuka
kamus itu dari halaman awal sampai halaman akhir satu persatu, namun kita
mencarinya dengan cara membelah atau membagi dua buku itu. Jika kata yang dicari
tidak terletak di halaman pertengahan itu, kita mencari lagi di belahan bagian kiri atau belahan bagian kanan dengan cara membagi dua belahan yang dimaksud. Begitu
seterusnya sampai kata yang dicari ditemukan. Hal ini hanya bias dilakukan jika kata-
kata di dalam kamus sudah terurut.
Prinsip pencarian dengan membagi data dengan dua bagian mengilhami metode
pencarian bagidua. Data yang disimpan di dalam larik harus sudah terurut. Untuk
memudahkan pembahasan, selanjutnya kita misalkan elemen larik sudah terurut
menurun. Dalam proses pencarian, kita memerlukan dua buah indeks larik, yaitu
indeks terkecil dan terbesar. Kita menyebut indeks terkecil sebagai indeks ujung kiri
larik dan indeks terbesar sebagai indeks ujung kanan larik. Istilah “kiri” dan “kanan”
dinyatakan dengan membayangkan elemen larik terentang horizontal.
Misalkan indeks kiri adalah i dan indeks kanan adalah j. pada mulanya, kita
inisialisasi i dengan 1 dan j dengan n.
Langkah 1 : Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah
elemen dengan indeks k=(I + j) div 2.
(Elemen tengah, L[k], membagi larik menjadi dua bagian, yaitu bagian
kiri L[i..j] dan bagian kanan L[k+1..j])
Langkah 2 : Periksa apakah L[k] = x. Jika L[k] = x, pencarian selesai sebab x sudah
ditemukan. Tetapi, jika L[k]*x, harus ditentukan apakah pencarian akan
dilakukan di larik bagian bagian kiri atau bagian kanan. Jika L[k] < x,
maka pencarian dilakukan lagi pada larik bagian kiri. Sebaliknya, jika
L[k] > x, pencarian dilakukan lagi pada larik bagian kanan.
Langkah 3 : Ulangi langkah 1 hingga x ditemukan atau i > j (yaitu, ukuran larik
sudah nol!)
Contoh 1.8 : Pencarian elemen dengan metode bagidua
Ilustrasi pencarian bagidua: Misalkan diberikan larik L dengan delapan buah elemen
yang sudah terurut menurun seperti di bawah ini:
81 76 21 18 16 13 10 7 i=1 2 3 4 5 6 7 8=j
(i) Misalkan elemen yang dicari adalah x = 18.
Langkah 1:
i = 1 dan j = 8
indeks elemen tengah k = (1 + 8) div 2= 4 (elemen yang
diarsir
)
i=1 2 3 4 5 6 7 8=j
kiri kanan
Langkah 2:
Pembandingan : L[4] = 18? Ya! (x ditemukan, proses pencarian
selesai)
(ii) Misalkan elemen yang dicari adalah x = 16.
Langkah 1:
i = 1 dan j = 8
indeks elemen tengah k = (1+8) div 2 = 4 (elemen yang
diarsir)
1 2 3 4 5 6 7 8
kiri kanan
Langkah 2:
Pembandingan : L[4] = 16? Tidak! Harus diputuskan apakah
pencarian akan dilakukan di bagian kiri atau di bagian kanan
dengan pemeriksaan sebagai berikut:
81 76 21 18 16 13 10 7
81 76 21 18 16 13 10 7 Pembandingan: L[4] > 16? Tidak! Lakukan langkah pencarian pada
larik bagian kanan dengan i = k + 1 = 5 dan j = 8 (tetap)
i=5 6 7 8=j
Langkah 1:
i = 5 dan j = 8
indeks elemen tengah k = (5 + 8) div 2 = 6 (elemen yang diarsir)
5 6 7 8
kiri kanan
Langkah 2:
Pembandingan : L[6] = 16? Tidak! Harus diputuskan apakah
pencarian akan dilakukan di bagian kiri atau bagian kanan dengan
pemeriksaan sebagai berikut:
Pembandingan: L[6] > 16? Tidak! Lakukan pencarian pada larik
bagian kiri dengan i=5 (tetap) dan j= k-1 = 5
5
Langkah 1”:
i = 5 dan j = 5
indeks elemen tengah k = (5+5) div 2 = 5 (elemen yang diarsir)
5
Langkah 2”:
16 13 10 7
16 13 10 7
16
16 L[5] = 16? Ya! (x ditemukan, proses pencarian selesai)
(iii) Misalkan elemen yang dicari adalah x =100
Lagkah 1:
i = 1 dan j = 8
indeks elemen tengah k = (1+8) div 2 = 4 (elemen yang diarsir)
1 2 3 4 5 6 7 8
kiri kanan
Langkah 2:
Pembandingan: L[4] = 100? Tidak! Harus diputuskan apakah
pencarian akan dilakukan di bagian kiri atau di bagian kanan
dengan pemeriksaan sebagai berikut:
Pembandingan: L[4] = 100? Tidak! Lakukan pencarian pada larik
bagian kiri dengan i = 1 (tetap) dan j =k – 1
i= 1 2 3
Langkah 1’:
i = 1 dan j = 3
indeks elemen tengah k = (1+3) div 2 = 2 (elemen yang diarsir)
1 2 3
kiri’ kanan’
Langkah 2’:
81 76 21 18 16 13 10 7
81 76 21
81 76 21Pembandingan : L[2] = 100? Tidak! Harus diputuskan apakah
pencarian akan dilakukan di bagian kiri atau di bagian kanan
dengan pemeriksaan sebagai berikut:
Pembandingan: L[2] > 100? Tidak! Lakukan pencarian pada larik
bagian kiri dengan i = 1 dan j = k-1 = 1
1
Langkah 2”:
i = 1 dan j=1
indeks elemen tengah k= (1+1) div 2 = 1 (elemen yang diarsir)
1
Langkah 2”:
Pembandingan: L[1] = 100? Tidak! Harus diputuskan apakah
pencarian akan dilakukan di bagian kanan dengan pemeriksaan
sebagai berikut:
Pembandingan: L[1] > 100? Tidak! Lakukan pencarian pada larik
bagian kiri dengan i = 1 dan j = k – 1= 0
Karena i > j , maka tidak ada lagi bagian larik yang tersisa. Dengan
demikian, x tidak ditemukan di dalam larik. Proses pencarian
dihentikan.
Algoritma pencarian bagidua pada larik integer yang sudah terurut menurun kita
tuliskan di bawah ini, masing-masing sebagai prosedur dan sebagai fungsi.
(i) Procedure pencarian bagidua
81
81
procedure BinarySearch1 (input L : LarikInt, input n : integer, input x : integer, output
idx: integer)
{Mencari x di dalam larik L[1..n] yang sudah terurut menurun dengan metode
pencarian bagidua. Keluaran prosedur ini adalah indeks elemen larik yang
mengandung nilai x; idx diisi 0 jika x tidak ditemukan. }
{ K.Awal : L[1....n] sudahberisi data yang sudah terurut menurun, dan x adalah nilai
yang akan dicari. }
{ K.Akhir : idx berisi indekselemen larik yang mengandung nilai x;tetapi bila x tidak
ditemukan, maka idx diisi dengan nilai -1.}
DEKLARASI
i, j : integer { indeks larik dan indeks kanan larik }
k : integer { indeks elemen larik }
ketemu : Boolean { flag untuk menentukan apakah x ditemukan }
ALGORITMA
i ← 1 { ujung kiri larik }
j ← n { ujung kanan larik }
ketemu ← false { asumsikan x belum ditemukan }
While ( not ketemu ) and ( i ≤ j) do
k ← (i + j ) div 2 { bagidua larik L pada posisi k }
if ( L[k] = x ) then
ketemu ← true
else {L[k] ≠ x }
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 }
j←k – 1
endif endif
Endwhile
{ ketemu = true or i > j }
if ketemu then { x ditemukan }
idx ← k
else { x tidak ditemukan di dalam larik }
idx ← -1
endif
(ii) Fungsi pencarian bagidua
function BinarySearch1 (input L : LarikInt, input n : integer, input x : integer )→
integer
{ Mengembalikan indeks elemen larik L[1…n] yang mengandung nilai x; bila x tidak
ditemukan, maka indeks yang dikembalikan adalah -1 }
DEKLARASI
i, j : integer { indeks larik dan indeks kanan larik }
k : integer { indeks elemen tengah }
ketemu : Boolean { flag untuk menentukan apakah x ditemukan }
ALGORITMA
i ← 1 { ujung kiri larik }
j ← n { ujung kanan larik }
ketemu ← false { asumsikan x belum ditemukan }
While ( not ketemu ) and ( i ≤ j) do
k ← (i + j ) div 2 { bagidua larik L pada posisi k }
if ( L[k] = x ) then
ketemu ← true
else {L[k] ≠ x }
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 }
j←k – 1
endif
endif
Endwhile
{ ketemu = true or i > j }
if ketemu then { x ditemukan }
return k
else { x tidak ditemukan di dalam larik }
return -1
endif
Untuk algoritma pencarian bagidua pada larik yang sudah terurut menaik, kita hanya
perlu mengganti pernyataan if (L[k] > x) dengan if L[k] < x).
Kinerja Metode Pencarian Bagidua
Pembaca dapat melihat bahwa pada setiap kali pencarian, larik dibagidua menjadi dua
bagian yang berukuran hampir sama. Pada setiap pembagian, elemen tengah
dibandingkan apakah sama dengan x (if (L[k] = x). pada kasus terburuk, yaitu pada
kasus x tidak terdapat di dalam lrik atau x ditemukan setelah ukuran larik 1 elemen,
larik akan dibagi sebanyak *log(n) kali, sehingga jumlah pembandingan yang
dibutuhkan adalah sebanyak *log(n) kali. Kita katakana bahwa waktu pencarian
sebanding dengan *log(n)[WIR76]. Untuk n = 256 elemen misalnya, kasus terburuk
menghaslkan pembagian larik sebanyak *log(256) = 8 kali, yang berarti jumlah
pembandingan elemen adalah 8 kali (bandingkan dengan metode pencarian beruntun
yang pada kasus terburuk melakukan pembandingan sebanyak 256 kali). Jadi, untuk
larik yang terurut, algoritma pencarian bagidua jauh lebih cepat daripada algoritma
pencarian beruntun.
1.5 Pencarian pada Larik Terstruktur
Metode pencarian yang dibahas sebelum ini menggunakan larik dengan elemen-
elemen bertipe sederhana. Pada kebanyakan kasus, elemen larik sering bertipe
terstruktur. Contoh, misalkan M adalah sebuah larik yang elemennya menyatakan
nilai ujian mahasiswa untuk suatu mata kuliah (MK) yang ia ambil. Data setiap
mahasiswa adalah NIM (Nomor Induk Mahasiswa), nama mahasiswa, mata kuliah
yang ia ambil, dan nilai mata kuliah tersebut. Deklarasi nama dan tipe adalah sebagai
berikut:
DEKLARASI
Const Nmaks = 100
Type Mahasiswa : record < NIM : integer, { Nomor Induk Mahasiswa }
NamaMhs : string, {nama Mahasiswa}
KodeMK : string { kode mata kuliah }
Nila : char {indeks nilai MK (A/B/C/D/E)}
>
type TabMhs : array [ 1…Nmaks] of Mahasiswa
M : TabMhs
Struktur lojik larik M ditujukan pada gambar 1.2.
TabMhs
NIM NamaMhs Kode MK Nilai
1 29801 Heru Satrio MA211 A
2 29804 Amirullah Satya FI51 B
3
.
.
100 29887 Yanti Siregar TL21 C
Gambar 1.2 Larik M dengan 100 elemen. Setiap elemen larik bertipe terstruktur (record). Tipe record terdiri atas
field NIM, field MK, dan field Nilai.
Misalkan pencarian data didasarkan pada NIM, maka proses pembandingan dilakukan
terhadap field NIM saja. Algoritma pencarian beruntun dan algoritma pencarian
bagidua untuk larik terstruktur diberikan di bawah ini (untuk algoritma pencarian
beruntun, kita gunakan algoritma versi 2 dengan hasil pencarian adalah indeks larik,
sedangkan untuk algoritma pencarian bagidua kita gunakan pencarian pada larik yang
terurut menaik).
(a) Algoritma Pencarian Beruntun
procedure CariNIM (input M : TabMhs, input n : integer, input NIMmhs : integer,
output idx: integer)
{Mencari keberadaan NIMmhs di dalam larik M[1…n] sudah terdefinisi. }
{ K.Awal : nilai NIMmhs, n, dan elemen larik M[1…n] sudah terdefinisi. }
{ K.Akhir : idx berisi indekselemen larik tempat NIMmhs ditemukan, idx = -1 jika
NIMmhs tidak ditemukan.}
DEKLARASI
i, : integer {pencatat indeks larik }
ketemu : Boolean
ALGORITMA
i ← 1
ketemu ← false
While (i ≤ n ) and ( not ketemu) do
if M[i]. NIM = NIMmhs then
ketemu ← true
else
i←i + 1
endif
Endwhile
{ i > n or ketemu }
if ketemu then { NIMmhs ditemukan }
idx ← i
else {NIMmhs tidak ditemukan } idx ← -1
endif
(b) Algoritma Pencarian Bagidua
procedure CariNIM_2 (input M : TabMhs, input n : integer, input NIMmhs : integer,
output idx: integer)
{Mencari NIMmhs di dalam larik M[1…n] yang sudah terurut menaik berdasarkan
NIM dengan metode pencarian bagidua. }
{ K.Awal : larik M[1…n] sudah berisi data yang terurut menaik, dan NIMmhs
adalah nilai yang akan dicari. }
{ K.Akhir : idx berisi indeks larik tempat NIMmhs ditemukan, idx = -1 jika NIMmhs
tidak ditemukan.}
DEKLARASI
i, j : integer { indeks larik dan indeks kanan larik }
k : integer { indeks elemen larik }
ketemu : Boolean { flag untuk menentukan apakah x ditemukan }
ALGORITMA
i ← 1 { ujung kiri larik }
j ← n { ujung kanan larik }
ketemu ← false { asumsikan x belum ditemukan }
While ( not ketemu ) and ( i ≤ j) do
k ← (i + j ) div 2 { bagidua larik L pada posisi k }
if ( M[k].NIM = NIMmhs ) then
ketemu ← true
else {M[k].NIM ≠ NIMmhs }
if ( M[k]. NIM < NIMmhs ) 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 }
j←k – 1
endif
endif
Endwhile
{ ketemu = true or i > j }
if ketemu then { NIMmhs ditemukan }
idx ← k
else { NIMmhs tidak ditemukan di dalam larik }
idx ← -1
endif
1.6 Menggunakan Metode Pencarian Beruntun atau Metode Pencarian Bagidua?
Kedua metode pencarian ini mempunyai kelebihan dan kekurangan masing-masing.
Metode pencarian beruntun dapat digunakan baik untuk data yang belum terurut
maupun untuk data yang sudah terurut. Sebaliknya, metode pencarian bagidua hanya
dapat digunakan untuk data yang sudah terurut saja.
Ditinjau dari kinerja pencarian, kita sudah mengetahui bahwa untuk kasus terburuk
(yaitu jika pencarian gagal menemukan x), algoritma pencarian beruntun memerlukan
waktu yang sebanding dengan n (banyaknya data), sedangkan algoritma pencarian
membutuhkan waktu yang sebanding dengan *log(n). Karena *log(n) < n untuk n > 1,
maka n semakin besar pencarian dengan algoritma beruntun. Karena itulah, algoritma
pencarian bagidua lebih baik untuk mencari data pada sekumpulan nilai yang terurut
ketimbang algoritma pencarian beruntun.
Sebagai perbandingan antara algoritma pencarian beruntun dengan pencarian bagidua,
tinjaulah kasus di mana x tidak ditemukan di dalam larik yang sudah terurut.
Misalkan,
(a) untuk larik yang berukuran n = 256
• Algoritma pencarian beruntun melkukan pembandingan elemen larik sebanyak
256 kali,
• Algoritma pencarian bagidua melakukan pembandingan sebanyak *log(256) =
8 kali,
(b) untuk larik yang berukuran n = 1024 elemen
• Algoritma pencarian beruntun melakukan pembandingan larik sebanyak 1024
kali,
• Algoritma pencarian bagidua melakukan pembandingan sebanyak *log(1024)
= 10 kali.
1.7 Penacarian pada Larik yang Tidak Bertipe Numerik
Meskipun algoritma-algoritma pencarian yang sudah dkemukakan di atas diterapkan
pada larik integer, mereka tetap benar untuk larik data yang bertipe bukan numeric
misalnya data bertipe karakter, maupun string. Aculah kembali dari Buku 1 bahwa
operasi perbandingan (dengan operator <, >, *) juga berlaku pada tipe data karakter
maupun string. Jadi, pembandingan karakter seperti ‘a’ < ‘b’ atau pembandingan
string seperti ‘budi’ < ‘iwan’ adalah eksperesi relasional yang sah.
1.8 Algoritma Pencarian Beruntun dan Pencarian Bagidua dalam Bahasa
PASCAL dan Bahasa C
Dengan asumsi bahwa pembaca buku ini sudah memahami konversi dari notasi
algoritmik ke notasi Bahasa Pascal dan Bahasa C (baca Buku 1), di bawah ini
disajikan algoritma pencarian yang telah dikemukakan di atas dalam kedua bahas
tersebut.
ALGORITMIK
DEKLARASI
Const Nmaks = 100 { jumlah maksimum elemen larik }
Type LarikInt : array [1….Nmaks] of integer
PASCAL
(* DEKLARASI*)
const Nmaks = 100; { jumlah maksimum elemen larik }
type LarikInt = array [1…Nmaks] of integer
C
/*DEKLARASI*/
#define Nmaks 100 /* jumlah elemen larik*/
typedef int LarikInt [Nmaks+1]; /* indeks larik dimulai dari 0 sampai Nmaks,
tetapi elemen ke 0 tidak akan digunakan*/
1. Agoritma Pencarian Beruntun
ALGORITMIK
procedure seqSearch2 (input L : LarikIntInt, input n : integer,
input x : integer, output idx : integer)
{ Mencari keberadaan nila x di dalam larik L[1..n]. }
{ K.Awal : x dan elemen-elemen larik L[1..n] sudah terdefinisi nilainya. }
{ K.Akhir : idx berisi indeks larik L yang berisi nilai x . Jika x tidak ditemukan, maka
idxdiisi dengan nilai -1 }
DEKLARASI
i : integer { pencatat indeks larik }
ALGORITMA
i ←1
while ( i < n ) and ( L[i] ≠ x ) do
i ←i + 1
endwhile
{ i = n or L[i] = x }
if L[i] = x then {x ditemukan }
idx ← i
else
idx ← -1
endif
PASCAL
procedure seqSearch2 ( L : LarikIntInt; n : integer; x : integer; var idx : integer)
{ Mencari keberadaan nila x di dalam larik L[1..n]. }
{ K.Awal : x dan elemen-elemen larik L[1..n] sudah terdefinisi. }
{ K.Akhir : idx berisi indeks larik L yang berisi nilai x . Jika x tidak ditemukan, maka
idxdiisi dengan nilai -1 }
var
i : integer; { pencatat indeks larik }
begin
i :=1;
while ( i < n ) and ( L[i] < > x ) do
i :=i + 1;
endwhile}
{ i = n or L[i] = x }
if L[i] = x then {x ditemukan }
idx := i
else
idx := -1; { x tidak ditemukan }
(endif) end;
C
void seqSearch2 ( LarikInt L, Int n, int x, int * idx)
/* Mencari keberadaan nila x di dalam larik L[1..n]. */
/* K.Awal : x dan elemen-elemen larik L[1..n] sudah terdefinisi nilainya. */
/* K.Akhir : idx berisi indeks larik L yang berisi nilai x . Jika x tidak ditemukan,
maka idxdiisi dengan nilai -1 */
{
int i; /* pencatat indeks larik*/
i =1;
while ( i < n && L[i] != x )
i ++;
/*endwhile*/
/* i== n or L[i] == x */
if (L[i] == x ) /*x ditemukan */
*idx = i;
else /* x tidak ditemukan*/
*idx = -1;
/*endif*/
}
2. Algoritma Pencarian Beruntun
ALGORITMIK
procedure BinarySearch2 (input L : LarikInt, input n : integer, input x : integer, output
idx: integer) {Mencari x di dalam larik L[1..n] yang sudah terurut menurun dengan metode
pencarian bagidua. Keluaran prosedur ini adalah indeks elemen berisi nilai x. }
{ K.Awal : L[1....n] sudahberisi data yang sudah terurut menurun, dan x adalah nilai
yang akan dicari. }
{ K.Akhir : idx berisi indekselemen larik tempat x ditemukn, idx = -1jika x tidak
ditemukan.}
DEKLARASI
i, j : integer { indekskiri larik dan indeks kanan larik }
k : integer { indeks elemen larik }
ketemu : Boolean { pertanda untuk menentukan apakah x ditemukan }
ALGORITMA
i ← 1 { ujung kiri larik }
j ← n { ujung kanan larik }
ketemu ← false { asumsikan x belum ditemukan }
While ( not ketemu ) and ( i ≠ j) do
k ← (i + j ) div 2 { bagidua larik L pada posisi k }
if ( L[k] = x ) then
ketemu ← true
else {L[k] * x }
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 }
j←k – 1
endif
endif
Endwhile
{ ketemu = true or i > j }
if ketemu then { x ditemukan } idx ← k
else { x tidak ditemukan di dalam larik }
idx ← -1
endif
PASCAL
procedure BinarySearch2 ( L : LarikInt; n : integer; x : integer; var idx: integer);
{Mencari x di dalam larik L[1..n] yang sudah terurut menurun dengan metode
pencarian bagidua. Keluaran prosedur ini adalah indeks elemen berisi nilai x. }
{ K.Awal : L[1....n] sudahberisi data yang sudah terurut menurun, dan x adalah nilai
yang akan dicari. }
{ K.Akhir : idx berisi indekselemen larik tempat x ditemukn, idx = -1jika x tidak
ditemukan.}
var
i, j : integer; { indekskiri larik dan indeks kanan larik }
k : integer; { indeks elemen larik }
ketemu : Boolean; { pertanda untuk menentukan apakah x ditemukan }
begin
i :=1 { ujung kiri larik }
j := n { ujung kanan larik }
ketemu := false; { asumsikan x belum ditemukan }
While ( not ketemu ) and ( i <= j) do
k := (i + j ) div 2 { bagidua larik L pada posisi k }
if ( L[k] = x ) then
ketemu := true
else {L[k] < > x }
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 }
j : = k – 1;
{endif}
{endif}
End {while};
{ ketemu = true or i > j }
if (ketemu) then { x ditemukan }
idx : = k
else { x tidak ditemukan di dalam larik }
idx : = -1;
end;
C
void BinarySearch2 ( L : LarikInt, int n, int x, int * idx)
/*Mencari x di dalam larik L[1..n] yang sudah terurut menurun dengan metode
pencarian bagidua. Keluaran prosedur ini adalah indeks elemen berisi nilai x. */
/* K.Awal : L[1....n] sudahberisi data yang sudah terurut menurun, dan x adalah nilai
yang akan dicari. */
/* K.Akhir : idx berisi indekselemen larik tempat x ditemukn, idx = -1jika x tidak
ditemukan.*/
{
typedef enum { true = 1, false = 0 } Boolean; /* deklarasi tipe Boolean*/
int i, j; /* indekskiri larik dan indeks kanan larik */
int k; /* indeks elemen larik */ Boolean ketemu; /* pertanda untuk menentukan apakah x ditemukan */
i =1; /* ujung kiri larik */
j = n; /* ujung kanan larik */
ketemu = false; /* asumsikan x belum ditemukan */
While ( ! ketemu && i < = j)
{
k = (i + j ) / 2 /* bagidua larik L pada posisi k */
if ( L[k] == x )
ketemu = true;
else /* L[k] != x */
if ( L[k] > x )
/* 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
*/
j = k – 1;
/*endif*/
/*endif*/
}
/*endwhile*/
/* ketemu = true or i > j */
if (ketemu) /* x ditemukan */
*idx = k;
else /* x tidak ditemukan di dalam larik */
*idx = -1;
/*endif*/
}
0 komentar:
Posting Komentar