Sorting Algorithm
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).
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
|
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
|
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.
|
Merging
|
Misal A merupakan himpunan data terurut
dengan r buah elemen dan B himpunan data terurut dengan s buah elemen. Proses
yang menggabungkan elemen-elemen dalam A dan B menjadi himpunan elemen data
terurut tunggal, misal C dengan n = r + s buah elemen disebut dengan proses Merging.
Secara singkat, proses Merging dapat dijelaskan sebagai
berikut ; ambil elemen pertama dari A, A[1] dan B, B[1]. Bandingkan kedua
elemen tersebut. Jika A[1] > B[1], B[1] dimasukkan dalam C, jika tidak A[1]
dimasukkan dalam C. Untuk himpunan data yang elemennya dimasukkan dalam C,
elemen yang akan dibandingkan adalah elemen berikutnya. Dan seterusnya.
Contoh :
A = 11 12
23 33 45
67
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.
|
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
|
|
|
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
|
Berikut ini adalah beberapa contoh algoritma Sorting:
Pengurutan Sisip (Insertion Sort)
Kamus Lokal
K : integer {pencacah langkah}
J : integer {pencacah untuk penelusuran larik}
Temp : integer {peubah bantu untuk agar L[K] tidak ditimpa selama pergeseran}
ALGORITMA
{elemen L[1] dianggap sudah terurut}
for K ← 2 to N do {mulai dari langkah 2 sampai langkah N}
Temp ← L[K] {ambil elemen L[K] supaya tidak ditimpa pergeseran}
{cari posisi yang tepat untuk L[K] di dalam L[1..K-1] sambil menggeser}
J ← K - 1
while Temp ≤ L[J] AND (J > 1) do
L[J+1] ← L[J]
J ← J-1
endwhile
if Temp ≥ L[J] then
L[J+1] ← Temp
else
L[J+1] ← L[J]
L[J] ← Temp
endif
endfor
Pengurutan Sisip (Insertion Sort)
procedure UrutSisip_Turun(input/output L: Larik, input N : integer)
Kamus Lokal
K : integer {pencacah langkah}
J : integer {pencacah untuk penelusuran larik}
Temp : integer {peubah bantu untuk agar L[K] tidak ditimpa selama pergeseran}
ALGORITMA
{elemen L[1] dianggap sudah terurut}
for K ← 2 to N do {mulai dari langkah 2 sampai langkah N}
Temp ← L[K] {ambil elemen L[K] supaya tidak ditimpa pergeseran}
{cari posisi yang tepat untuk L[K] di dalam L[1..K-1] sambil menggeser}
J ← K - 1
while Temp ≥ L[J] AND (J > 1) do
L[J+1] ← L[J]
J ← J-1
endwhile
{Temp > L[J] or J = 1}
if Temp ≤ L[J] then
L[J+1] ← Temp
else
L[J+1] ← L[J]
L[J+1] ← Temp
endif
endfor
Algoritma Selection Sort
{cari elemen terkecil}
t := i {t adalah index elemen terkecil}
for j := i + 1 to n do
if l[j] < l[t] then
t := j
endif
endfor
{tukar elemen terkecil dengan elemen i}
temp := l[j]
l[j] := l[i]
l[i] := temp
for i := 1 to n – 1 do
{cari elemen terkecil}
t := i {t adalah index elemen terkecil}
for j := i + 1 to n do
if l[j] < l[t] then
t := j
endif
endfor
{tukar elemen terkecil dengan elemen i}
temp := l[j]
l[j] := l[i]
l[i] := temp
endfor
Algoritma Selection Sort
proc UrutPilih (l,n)
{mengurutkan membesar data di dalam larik l yang berelemen sebanyak n dengan cara pemilihan}
for i := 1 to n – 1 do
{cari elemen terkecil}
t := i {t adalah index elemen terkecil}
for j := i + 1 to n do
if l[j] < l[t] then
t := j
endif
endfor
{tukar elemen terkecil dengan elemen i}
temp := l[j]
l[j] := l[i]
l[i] := temp
endfor
Algoritma Shell Sort
Banyak = N
range = banyak / 2
while range <> 0
counter = 1
target = banyak-range
while counter<=target
kiri = counter
selesai = false
while selesai=false
kanan = kiri+range
if item (kiri)>= item(kanan)
selesai = true
else
swap item (kiri) dan
item (kanan)
if kiri > range
kiri = kiri - range
else
selesai = true
end_if
end_if
end_while
counter = counter + 1
end_while
range = range / 2
end_while
Algoritma Pengurutan Maksimum
Algoritma Pengurutan Minimum
Pengurutan Gravitasi
procedure UrutGravitasi(input/output L: Larik; input N : integer)
Deklarasi
I : integer {pencacah untuk jumlah langkah}
K : integer {pencacah untuk pemberatan pada setiap langkah}
U : integer {indeks ujung kiri bagian larik yang telah terurut}
Temp : integer {peubah bantu untuk pertukaran}
Algoritma
U ← N
for I ← 1 to N-1 do
for K ← 1 to U-1 do
if L[K] > L[K+1] then {pertukarkan L[K] dengan L[K+1]}
Temp ← L[K]
L[K] ← L[K-1]
L[K-1] ← Temp
endif
endfor
{ larik L[U..N] terurut, larik L[1..U-1] belum terurut }
U ← U - 1
Endfor
Algoritma Pengurutan Maksimum
procedure UrutMaksimum(input/output L: Larik, input N : integer)
Kamus Lokal
I : integer {pencacah untuk jumlah langkah}
J : integer {pencacah untuk mencari nilai maksimum}
U : integer {indeks ujung kiri bagian larik yang telah terurut}
Maks : integer {nilai maksimum sementara}
Imaks : integer {indeks yang berisi nilai maksimum sementara}
Temp : integer {peubah bantu untuk pertukaran}
Algoritma
U ← N
for I ← 1 to N-1 do
Maks ← L[1]
Imaks ← 1
for J ← 2 to U do
if L[J] > L[Imaks] then
Maks ← L[J]
Imaks ← J
endif
endfor
{pertukarkan Maks dengan L[U]}
Temp ← L[U]
L[U] ← L[Imaks]
L[Imaks] ← Temp
{ larik L[U..N] terurut, larik L[1..U-1] belum terurut }
U ← U - 1
endfor
Algoritma Pengurutan Minimum
procedure UrutMin(input/output L: Larik, input N : integer)
Kamus Lokal
I : integer {pencacah untuk jumlah langkah}
J : integer {pencacah untuk mencari nilai minimum}
U : integer {indeks ujung kiri bagian larik yang telah terurut}
Imin : integer {indeks yang berisi nilai minimum sementara}
Temp : integer {peubah bantu untuk pertukaran}
Algoritma
U ← N
for I ← 1 to N-1 do
Imin ← 1
for J ← 2 to U do
if L[J] < L[Imin] then
Imin ← J
endif
endfor
{pertukarkan Maks dengan L[U]}
Temp ← L[U]
L[U] ← L[Imin]
L[Imin] ← Temp
{ larik L[U..N] terurut, larik L[1..U-1] belum terurut }
U ← U - 1
endfor
