SEARCHING & SORTING

Pendahuluan
Sorting dan searching merupakan salah satu operasi dasar dalam ilmu
komputer. Sorting merupakan suatu proses (operasi) yang mengurutkan data
dalam suatu urutan yang diberikan (increasing atau decreasing). Searching
merupakan suatu proses (operasi) untuk mencari lokasi dari data yang diberikan
dalam suatu urutan data.
Secara tidak langsung sorting dan searching menunjuk pada operasi file
yang merupakan kumpulan suatu dari record. Masing-masing record dalam file F
dapat berisi banyak field, tetapi terdapat 1 buah field yang memiliki nilai unique
atau merupakan key yang unique dalam record tersebut. Misal field K
merupakan key unique yang disebut primary key, maka proses sorting file F
akan berdasarkan key unique tersebut dan proses searching untuk mencari
record tertentu berdasarkan nilai key unique yang diberikan.

Sorting
Terdapat 2 katagori dasar dalam tehnik sorting : internal sort dan
external sort. Metoda Internal sort digunakan apabila koleksi data yang akan
diurutkan tidak dalam jumlah besar sehingga proses dapat dilakukan dalam
main memory. Metoda External sort digunakan apabila koleksi data yang akan
diurutkan dalam jumlah besar dimana koleksi data tersebut ada dalam auxiliary
memory device seperti magnetic tape atau disk.
(Yang akan di bahas adalah Internal Sort).

Misal A merupakan suatu daftar dari n elemen A1, A2, ..., An dalam
memori. Sorting A merupakan operasi yang mengatur elemen dalam A sehingga
ada dalam urutan yang terurut, misal dalam increasing order sehingga :

A1 A2 A3 ..... An

Contoh :
Misal suatu array DATA berisi 8 elemen sebagai berikut :

DATA : 77, 33, 44, 11, 88, 22, 66, 55

Setelah diurutkan :

DATA : 11, 22, 33, 44, 55, 66, 77, 88

Insertion Sort

70
 Misal array A dengan n elemen A[1], A[2], ..... , A[N] dalam memori.
Algoritma Insertion Sort memeriksa A dari A[1] sampai dengan A[N], menyisipkan
setiap elemen A[K] ke dalam posisi yang seharusnya dalam subarray terurut
A[1], A[2], ..... , A[K-1].

Algoritma sorting ini umumnya digunakan apabila jumlah elemennya

sedikit (n kecil). Masalah yang akan muncul dengan metoda ini adalah
bagaimana cara menyisipkan A[K] ke dalam letak yang seharusnya pada
subarray terurut A[1], A[2], ....., A[K-1]. Hal ini dapat dilakukan dengan
membandingkan A[K] dengan A[K-1], kemudian A[K] dengan A[K-2], A[K] dengan
A[K-3] dan seterusnya, sampai menemukan elemen A[J] dimana A[J] A[K].

Algoritma ini menggunakan sentinel elemen (A[0]) yang digunakan sebagai

perbandingan. Yang dimaksud dengan sentinel elemen adalah elemen yang
memiliki nilai yang sangat kecil.

Penggambaran proses Insertion Sort :

Proses A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

K = 1: - 77 33 44 11 88 22 66 55

K = 2: - 77 33 44 11 88 22 66 55

K = 3: - 33 77 44 11 88 22 66 55

K = 4: - 33 44 77 11 88 22 66 55

K = 5: - 11 33 44 77 88 22 66 55

K = 6: - 11 33 44 77 88 22 66 55

K = 7: - 11 22 33 44 77 88 66 55

K = 8: - 11 22 33 44 66 77 88 55

Urutan : - 11 22 33 44 55 66 77 88

Tabel 1.1

Contoh :
Array A dengan 8 elemen sebagai berikut :
77, 33, 44, 11, 88, 22, 66, 55

71
 Tabel 1.1 menggambarkan algoritma insertion sort. Elemen yang
dilingkari menandakan A[K] dalam masing-masing proses dari algoritma, dan
tanda panah menandakan letak yang seharusnya untuk menyisipkan A[K].

Algoritma Insertion Sort :

1. A[0] = 0 {sentinel elemen}
2. Repeat langkah 3 sampai 5 untuk K = 2,3,.....,N
3. Temp := A[K] ; PTR = K - 1
4. Repeat While Temp < A[PTR]
a. A[PTR+1] = A[PTR]
b. PTR = PTR - 1
[End Of Loop]
5. A[PTR+1] = Temp
[End Loop Langkah 2]
6. Return

Complexity Insertion Sort = O(n 2)

Selection Sort
Array A dengan n elemen A[1], A[2], ....., A[N] dalam memori. Algoritma untuk
mengurutkan A sebagai berikut : Pertama, cari elemen terkecil dalam array A dan
letakkan pada posisi pertama dalam array tersebut. Kemudian cari elemen kedua
terkecil dalam array A dan letakkan dalam posisi kedua dari array tersebut, dan begitu
seterusnya.

Proses 1 : Cari lokasi LOC yang merupakan elemen terkecil dalam array yang
terdiri dari N elemen , A[1], A[2], ...., A[N] dan kemudian tukar posisi
A[LOC] dengan A[1].

Proses 2 : Cari lokasi LOC yang merupakan elemen terkecil dalam array yang
terdiri dari N-1 elemen , A[2], A[3], ...., A[N] dan tukar posisi A[LOC]
dengan A[2]. A[1] , A[2] terurut, jika dan hanya jika A[1] A[2].

Proses 3 : Cari lokasi LOC yang merupakan elemen terkecil dalam array yang
terdiri dari N-2 elemen, A[3], A[4],......, A[N] dan tukar posisi A[LOC]
dengan A[3]. A[1], A[2], A[3] terurut, jika dan hanya jika A[2] A[3].
Dst.................

Sehingga A akan terurut setelah N-1 proses.

Contoh ;
Array A dengan 8 elemen sbb :
77, 33, 44, 11, 88, 22, 66, 55
Proses algoritma digambarkan dalam Tabel 1.2. Misalkan LOC berisi nilai lokasi
elemen terkecil A[K], A[K+1],...,A[N] selama proses K. Elemen yang dilingkari
merupakan elemen yang akan ditukar posisinya.

72
 Proses A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8]

K = 1 ; LOC = 4 77 33 44 11 88 22 66 55
K = 2 ; LOC = 6 11 33 44 11 88 22 66 55
K = 3 ; LOC = 6 11 22 44 77 88 33 66 55
K = 4 ; LOC = 6 11 22 33 77 88 44 66 55
K = 5 ; LOC = 8 11 22 33 44 88 77 66 55
K = 6 ; LOC = 7 11 22 33 44 55 77 66 88
K = 7 ; LOC = 7 11 22 33 44 55 66 77 88

Urutan : 11 22 33 44 55 66 77 88

Tabel 1.2

Algoritma :

Procedure SELECTION (A, N)

1. Repeat langkah 2 dan 3 untuk K = 1,2,.....,N-1
2. Call MIN(A, K, N, LOC)
3. Temp = A[K] ;A[K] = A[LOC] ; A[LOC] = Temp
[End Loop langkah 1]
4. Exit

Procedure MIN (A,K,N,LOC)

1. Min = A[K] ; LOC = K
2. Repeat For J = K+1, K+2, ......, N
If Min > A[J] Then Min = A[J] ; LOC = A[J] ; LOC = J
[End Loop]
3. Return

Complexity (kompleksitas) algoritma Selection Sort : O(n 2)

Merging
Misal A merupakan himpunan data terurut dengan r buah elemen dan B
himpunan data terurut dengan s buah elemen. Proses yang menggabungkan

73
elemen-elemen dalam A dan B menjadi himpunan elemen data terurut tunggal,
misal C dengan n = r + s buah elemen disebut dengan proses Merging.

74
Secara singkat, proses Merging dapat dijelaskan sebagai berikut ; ambil elemen
pertama dari A, A[1] dan B, B[1]. Bandingkan kedua elemen tersebut. Jika A[1] >
B[1], B[1] dimasukkan dalam C, jika tidak A[1] dimasukkan dalam C. Untuk
himpunan data yang elemennya dimasukkan dalam C, elemen yang akan
dibandingkan adalah elemen berikutnya. Dan seterusnya.

Contoh :
A = 11 12 23 33 45 67
B = 9 12 21 42

Disini A[1] = 11 dan B[1] = 9 dibandingkan dan A[1] > B[1], B[1]
dimasukkan dalam C. Pembandingan berikutnya A[1] = 11 dibandingkan dengan
B[2] = 12, A[1] dimasukkan dalam C, dan begitu seterusnya.

Algoritma MERGING :

1. NA = 1 ; NB = 1 dan PTR = 1
2. Repeat While NA R and NB S
If A[NA] < B[NB] then
a. C[PTR] = A[NA]
b. PTR = PTR + 1 ; NA = NA + 1
Else
a. C[PTR] = B[NB]
b. PTR = PTR + 1 ; NB = NB + 1
[End If Structure]
[End Loop]
3. If NA > R then
Repeat For k = 0,1,2,3,.....,S-NB
C[PTR+K] = B[NB+K]
[End loop]
Else
Repeat for K = 0,1,2,3,.....,R-NA
C[PTR+K] = A[NA+K]
[End loop]
[End If Structure]
4. Exit

Kompleksitas algoritma Merging = O(n). Dengan kata lain algoritma Merging

dapat dijalankan dalam waktu yang linear.

Merge Sort

Misal : Array A dangan n elemen A[1], A[2], ....., A[N] dalam memori. Algoritma
Merge Sort yang akan mengurutkan A akan digambarkan sebagai berikut :

Contoh :

75
 Array A berisi 6 elemen sbb :
15 12 45 56 13 10

Masing-masing proses dalam algoritma merge sort akan dimulai dari elemen
awal dalam A dan menggabungkan (merge) pasangan subarray yang terurut sbb :

15 12 45 56 13 10

12 15 45 56 1013

12 15 45 56 10 13

10 12 13 15 45 56

Kompleksitas dari proses merge-sort = O(n).

Tournament Sort
Tournament Sort disebut juga dengan Tree Selection Sort. Misal terdapat
elemen data sebagai berikut : 6, 25, 7, 2, 14, 10, 9, 22, 3, 14, 8, 12, 1, 30, 13.
Asumsikan bahwa batasan proses dalam memori hanya 4 buah elemen setiap
saatnya. Algoritma Tournament Sort membagi 4 elemen tersebut menjadi 2
pasangan elemen sbb :

6
25

7
2

Asumsikan bahwa data tersebut akan diurutkan secara ascending, sehingga

elemen terkecil pada masing-masing pasangan di atas adalah 2 dan 6.

6 6
25

7 2
2

2 adalah elemen terkecil dan merupakan elemen pertama pada output dari
urutan yang diurutkan.
6 6
25
2 2
7 2
2

76
Proses yang berikutnya akan ditentukan elemen kedua dalam list terurut. 2 tidak
diikutsertakan kembali.

6 6
25
6 2, 6
7 7
*

Proses selanjutnya :

6 6
25
6 2, 6
7 7
14

Proses ketiga :

10 10
25
7 2, 6, 7
7 7
14

Proses keempat :

10 10
25
9 2, 6, 7, 9
9 9
14

Proses kelima :
10 10
25
10 2, 6, 7, 9, 10
22 14
14

77
Pada proses keenam elemen 3 dimasukkan dalam tree :

3
25

22 14
14

Apabila 3 diikutkan dalam proses, maka urutan list terurut pada output akan
berantakan. Untuk mengatasinya, terdapat aturan sbb :
If Keynew < Keylastout
then keynew diletakkan dalam tree tetapi untuk sementara waktu
di-
diskualifikasikan.

Catatan : Keylastout adalah key terakhir yang ada dalam list terurut.

Elemen yang didiskualifikasikan akan ditandai dengan asterisk (*). Sehingga

hasil dari proses enam adalah :
*3 25
25
14 2, 6, 7, 9, 10, 14
22 14
14

Pada proses ketujuh, elemen berikutnya adalah 14. Karena elemen terakhir
dalam list terurut tidak lebih kecil dari elemen yang akan dimasukkan, yakni 14,
maka elemen 14 masuk dalam list terurut.
*3 25
25
14 2, 6, 7, 9, 10, 14, 14
22 14
14

Proses kedelapan, elemen berikutnya 8 dan elemen ini untuk sementara akan
didiskualifikasi karena 8 < dari elemen terakhir dalam list terurut yakni 14.
*3 25
25
22 2, 6, 7, 9, 10, 14, 14, 22
22 22
*8

Proses kesembilan :

*3 25
25
25 2, 6, 7, 9, 10, 14, 14, 22, 25

78
 *12 *
*8

Proses kesepuluh, elemen berikutnya 1 :

*3
*1

*12
*8

Sekarang semua elemen yang ada adalah elemen yang didiskualifikasikan. Dan
saat ini baru 9 elemen yang diurutkan. Sekarang elemen yang untuk sementara
didiskualifikasikan, dilepaskan dari diskualifikasi dan proses dimulai kembali.
Kali ini akan terbentuk list terurut kedua dari elemen-elemen yang
didiskualifikasi sebelumnya. Sehingga proses 10 :

3 1
1
1 2, 6, 7, 9, 10, 14, 14, 22, 25
12 8 1
8

Proses 11, elemen 30 :

3 3
30
3 2, 6, 7, 9, 10, 14, 14, 22, 25
12 8 1, 3
8

Proses 12 :

13 13
30
8 2, 6, 7, 9, 10, 14, 14, 22, 25
12 8 1, 3, 8
8

Sekarang input list kosong. Sehingga proses 13 :

13 13
30
12 2, 6, 7, 9, 10, 14, 14, 22, 25
12 12 1, 3, 8, 12
*

79
Proses 14 dan 15 tidak terdapat elemen yang dimasukkan dalam tree. Hasil
akhir dari proses tournament sort ini menghasilkan 2 himpunan elemen data
yang terurut :

2, 6, 7, 9, 10, 14, 14, 22, 25

1, 3, 8, 12, 13, 30

Kedua himpunan data yang terurut tersebut dapat digabungkan menjadi satu list
data terurut dengan menggunakan algoritma Merging.

Shell Sort
Disebut juga dengan metoda pertambahan menurun (diminishing
increment). Metoda ini dikembangkan oleh Donald L. Shell tahun 1959. Metoda
ini memanfaatkan penukaran sepasang elemen untuk mencapai keadaan urut.
Dalam hal ini jarak dua elemen yang dibandingkan dan ditukarkan tertentu.

Pada langkah pertama, ambil elemen pertama dan kita bandingkan

dengan elemen pada jarak tertentu dari elemen pertama tersebut. Kemudian
elemen kedua dibandingkan dengan elemen lain dengan jarak yang sama.
Demikian seterusnya sampai seluruh elemen dibandingkan.

Pada contoh berikut, proses pertama kali jarak diambil separoh

banyaknya elemen yang akan diurutkan. Proses kedua jaraknya diambil separuh
jarak yang pertama, dst....

Misal terdapat elemen sebagai berikut :

23 45 12 24 56 34 27 23 16

Proses pengurutan menggunakan metoda Shell ada pada tabel 1.3. Dalam hal
ini elemen yang ditulis miring adalah elemen yang dibandingkan dan kemudian
ditukar, jika perlu.

Jarak A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

Awal 23 45 12 24 56 34 27 23 16

Jarak = 4 23 45 12 24 56 34 27 23 16
23 45 12 24 56 34 27 23 16

80
 23 34 12 24 56 45 27 23 16
23 34 12 24 56 45 27 23 16
23 34 12 23 56 45 27 24 16
23 34 12 23 16 45 27 24 56

Jarak = 2 23 34 12 23 16 45 27 24 56
12 34 23 23 16 45 27 24 56
12 23 23 34 16 45 27 24 56
12 23 16 34 23 45 27 24 56
12 23 16 34 23 45 27 24 56
12 23 16 34 23 45 27 24 56
12 23 16 34 23 24 27 45 56
12 23 16 34 23 24 27 45 56

Jarak = 1 12 23 16 34 23 24 27 45 56
12 23 16 34 23 24 27 45 56
12 16 23 34 23 24 27 45 56
12 16 23 34 23 24 27 45 56
12 16 23 23 34 24 27 45 56
12 16 23 23 24 34 27 45 56
12 16 23 23 24 27 34 45 56
12 16 23 23 24 27 34 45 56
12 16 23 23 24 27 34 45 56

Akhir 12 16 23 23 24 27 34 45 56

Searching
Pencarian data sering disebut juga dengan istilah table look-up atau storage
and retrieval information, adalah suatu proses untuk mengumpulkan sejumlah
informasi di dalam pengingat komputer dan kemudian mencari kembali informasi
yang diperlukan .

Sequential Searching
Metoda yang paling sederhana dari sejumlah metoda pencarian adalah metoda
pencarian berurutan (sequential searching). Secara singkat metoda ini dapat
dijelaskan sebagai berikut :
Dari elemen-elemen yang diketahui, data yang dicari dibandingkan satu
persatu sampai data tersebut ditemukan atau tidak ditemukan.

Algoritma Sequential Searching :

1. Baca himpunan data yang diketahui, misalnya sebagai himpunan A dengan N
elemen.
2. Baca data yang dicari, misal Data
3. Ada = False
4. For I = 1 to N proses langkah 5

5. If Data = A[I] then

Ada = True ; Posisi = I ; I = N
6. If Ada = False Then
N = N+1 ; A[I] = Data
7. Selesai

81
Skema Move To The Front
Pada skema pencarian sekuensial move to the front, apabila proses pencarian
berhasil, maka record tersebut dipindahkan pada posisi pertama dari daftar
tersebut. Record pertama menjadi record kedua dan seterusnya.

Metoda move to the front ini, prosesnya lebih baik apabila menggunakan linked
list dibandingkan dengan array. (cari alasannya, mengapa !)

82
Skema Transposition
Pada skema pencarian sekuensial transposition, apabila prose pencarian berhasil,
maka record tersebut dipindahkan pada posisi berikutnya.

Kedua skema di atas (move to the front dan transposition) didasarkan pada
kemungkinan proses pencarian apabila elemen data yang di cari akan digunakan dan
dicari kembali.

(Cari kelebihan dan kekurangan kedua skema di atas dengan penggambaran secara
linked list dan array !)

83