Metode Shell
Metode ini disebut juga dengan
metode pertambahan menurun (diminishing increment).Metode dikembangkan oleh Donald L. Shell pada tahun
1959, sehingga sering disebut dengan Metode Shell Sort. Metode ini mengurutkan
data dengan cara membandingkan suatu data dengan data lain yang memiliki jarak
tertentu, kemudian dilakukan penukaran bila diperlukan.
Proses
pengurutan dengan metode Shell dapat dijelaskan sebagai berikut :
·
Pertama-tama adalah menentukan jarak mula-mula dari data
yang akan dibandingkan, yaitu N / 2. Data pertama dibandingkan dengan data
dengan jarak N / 2. Apabila data pertama lebih besar dari data ke N / 2
tersebut maka kedua data tersebut ditukar. Kemudian data kedua dibandingkan
dengan jarak yang sama yaitu N / 2. Demikian seterusnya sampai seluruh data
dibandingkan sehingga semua data ke-j selalu lebih kecil daripada data ke-(j +
N / 2).
·
Pada proses berikutnya, digunakan jarak (N / 2) / 2 atau N /
4. Data pertama dibandingkan dengan data dengan jarak N / 4. Apabila data
pertama lebih besar dari data ke N / 4 tersebut maka kedua data tersebut ditukar.
Kemudian data kedua dibandingkan dengan jarak yang sama yaitu N / 4. Demikian
seterusnya sampai seluruh data dibandingkan sehingga semua data ke-j lebih
kecil daripada data ke-(j + N / 4).
·
Pada proses berikutnya, digunakan jarak (N / 4) / 2 atau N /
8. Demikian seterusnya sampai jarak yang digunakan adalah 1.
Algoritma metode Shell dapat
dituliskan sebagai berikut :
Jarak ←N
Selama (Jarak > 1) kerjakan baris 3 sampai
dengan 9
Jarak ←Jarak
/ 2. Sudah ←false
Kerjakan baris 4 sampai dengan 8 selama Sudah =
false
Sudah ←true
j←0
Selama (j < N – Jarak) kerjakan baris 8 dan 9
Jika (Data[j] >Data[j + Jarak] maka tukar
Data[j], Data[j + Jarak]. Sudah ←true
j←j + 1
Untuk
lebih memperjelas langkah-langkah algoritma penyisipan langsung dapat dilihat
pada tabel. Proses pengurutan pada tabel 6.4 dapat dijelaskan sebagai berikut:
· Pada
saat Jarak = 5, j diulang dari 0 sampai dengan 4. Pada pengulangan pertama,
Data[0] dibandingkan dengan Data[5]. Karena 12<17, maka tidak terjadi
penukaran. Kemudian Data[1] dibandingkan dengan Data[6]. Karena 35>23 maka
Data[1] ditukar dengan Data[6]. Demikian seterusnya sampai j=4.
· Pada
saat Jarak = 5/2 = 2, j diulang dari 0 sampai dengan 7. Pada pengulangan
pertama, Data[0] dibandingkan dengan Data[2]. Karena 12>9 maka Data[0] ditukar
dengan Data[2]. Kemudian Data[1] dibandingkan dengan Data[3] juga terjadi
penukaran karena 23>11. Demikian seterusnya sampai j=7. Perhatikan untuk
Jarak = 2 proses pengulangan harus dilakukan lagi karena ternyata Data[0] >
Data[2]. Proses pengulangan ini berhenti bila Sudah=true.
· Demikian
seterusnya sampai Jarak=1.
Di bawah ini merupakan prosedur yang menggunakan
metode Shell.
void ShellSort(int N)
{
int Jarak, i, j;
bool Sudah;
Jarak = N;
while(Lompat > 1){
Jarak = Jarak / 2;
Sudah = false;
while(!Sudah){
Sudah = true;
for(j=0; j<N-Jarak; j++){
i = j + Jarak;
if(Data[j] > Data[i]){
61
Tukar(&Data[j], &Data[i]);
Sudah = false;
}
}
}
}
}
Metode Counting
Untuk dapat
melakukan pengurutan dengan counting
sort rentang nilai untuk kumpulan data yang akan diurutkan harus diketahui,
katakanlah k. Ide
dasar dari counting sort adalah menentukan, untuk setiap elemen x, jumlah
elemen yang lebih kecil daripada
x, yang kemudian informasi ini digunakan untuk menentukan posisi x. Contoh sederhana saja, jika terdapat 12 elemen yang
lebih kecil daripada x, maka
x akan mendapatkan posisinya di posisi 13.
Tentu saja,
sedikit modifikasi harus dilakukan agar metode ini dapat menangani kasus di mana terdapat elemen-elemen lain yang nilainya
sama dengan x. Di mana
tentu saja kita tidak dapat menempatkan semua elemen yang nilainya sama dengan x di posisi yang sama.
Implementasi Counting Sort
Misal array data
yang akan diurutkan adalah A. Counting sort membutuhkan sebuah array
C berukuran k, yang setiap elemen C[i]
merepresentasikan jumlah elemen dalam A yang nilainya adalah i.
Di array inilah penghitungan (counting) yang dilakukan dalam
pengurutan ini disimpan. Misal kita akan melakukan pengurutan pada array A
sebagai berikut, dengan n adalah 10 dan diasumsikan bahwa rentang nilai
setiap A[i] adalah 1..5 :
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
Dan array C setelah
diinisialisasi adalah :
C
|
0
|
0
|
0
|
0
|
0
|
|
1 2
3 4 5
|
Kemudian proses
penghitungan pun dimulai, proses ini linier, dilakukan dengan menelusuri array
A,
Langkah 1 : pembacaan pertama mendapat elemen A[1] dengan
isi 1, maka C[1] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7
8 9 10
|
C
|
1
|
0
|
0
|
0
|
0
|
|
1 2
3 4 5
|
Langkah 2 : pembacaan kedua mendapat elemen A[2] dengan
isi 3, maka C[3] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
C
|
1
|
0
|
1
|
0
|
0
|
|
1 2
3 4 5
|
Langkah 3 : pembacaan ketiga mendapat elemen A[3] dengan
isi 5, maka C[5] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
C
|
1
|
0
|
1
|
0
|
1
|
|
1 2
3 4 5
|
Langkah 4 : pembacaan keempat mendapat elemen A[4] dengan
isi 4, maka C[4] ditambah 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
C
|
1
|
0
|
1
|
1
|
1
|
|
1 2
3 4 5
|
Demikian dilakukan
terus menerus hingga semua elemen A telah diakses. Hingga setelah
langkah ke 10 didapatkan array C sebagai berikut :
C
|
1
|
2
|
3
|
1
|
3
|
|
1 2
3 4 5
|
Lalu array C
diproses sehingga setiap elemen C, C[i] tidak lagi
merepresentasikan jumlah elemen dengan nilai sama dengan i, namun setiap
C[i] menjadi merepresentasikan jumlah elemen yang lebih kecil
atau sama dengan i. Dan setelah proses tersebut dilakukan didapatkan C
sebagai berikut :
C
|
1
|
3
|
6
|
7
|
10
|
|
1 2
3 4 5
|
Setelah C didapat
dilakukan proses penempatan sesuai dengan posisi yang didapat. Proses ini
dilakukan dengan menelusuri kembali A dari belakang. Mengapa dari
belakang? Karena kita mengharapkan hasil pengurutan yang stable, yang
akan sangat penting dalam pengurutan data majemuk.
Dalam proses
ini kita mengakses elemen A[i], kemudian memposisikannya di
posisi sebagaimana tercatat dalam C[A[i]], kemudian kita
mengurangkan C[A[i]] dengan 1, yang dengan jelas untuk
memberikan posisi untuk elemen berikutnya dengan yang isinya sama dengan A[i].
Proses ini
memerlukan sebuah array bantu B yang ukurannya sama dengan array A,
yaitu n. Yang pada awalnya semua B[i] diinisialisasi
dengan nil.
B
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
|
1 2
3 4 5
6 7 8
9 10
|
Langkah 1 : elemen A[10] adalah 5, maka karena C[5]
adalah 10, maka B[10] diisi dengan 5, dan C[5] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
B
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
-
|
5
|
|
1 2
3 4
5 6 7
8 9 10
|
C
|
1
|
3
|
6
|
7
|
9
|
|
1 2
3 4 5
|
Langkah 2 : elemen A[9] adalah 3, maka karena C[3]
adalah 6, maka B[6] diisi dengan 3, dan C[3] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
B
|
-
|
-
|
-
|
-
|
-
|
3
|
-
|
-
|
-
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
C
|
1
|
3
|
5
|
7
|
9
|
|
1 2
3 4 5
|
Langkah 3 : elemen A[8] adalah 3, maka karena C[3]
adalah 5, maka B[5] diisi dengan 3, dan C[3] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
B
|
-
|
-
|
-
|
-
|
3
|
3
|
-
|
-
|
-
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
C
|
1
|
3
|
4
|
7
|
9
|
|
1 2
3 4 5
|
Langkah 4 : elemen A[7] adalah 2, maka karena C[2]
adalah 3, maka B[3] diisi dengan 2, dan C[2] dikurangi 1.
A
|
1
|
3
|
5
|
4
|
5
|
2
|
2
|
3
|
3
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
B
|
-
|
-
|
2
|
-
|
3
|
3
|
-
|
-
|
-
|
5
|
|
1 2
3 4 5
6 7 8
9 10
|
C
|
1
|
2
|
4
|
7
|
9
|
|
1 2
3 4 5
|
Demikian proses
dilakukan hingga elemen A[1] selesai diproses, sehingga didapatkan hasil
akhir
B
|
1
|
2
|
2
|
3
|
3
|
3
|
4
|
5
|
5
|
5
|
|
1 2
3 4
5 6 7
8 9 10
|
Yang telah
berupa array dengan elemen-elemennya terurut secara non-decreasing.
2.7 Algoritma dan Kompleksitas Waktu Counting Sort
Dari
implementasi yang telah dilakukan tersebut, penulis mengimplementasikannya
manjadi sebuah program menggunakan bahasa Pascal sebagai berikut :
procedure CountingSort (A : TArray; var B : TArray);
var
C : array [1..k] of byte;
i : integer;
begin
for i:=1 to k do
C[i] := 0;
for i:=1 to n do
C[A[i]] :=
C[A[i]] + 1;
for i:=2 to k do
C[i] := C[i] +
C[i-1];
for i:=n downto 1 do begin
B[C[A[i]]] :=
A[i];
C[A[i]] :=
C[A[i]] - 1;
end;
end;
Waktu yang
dibutuhkan untuk mengurutkan data menggunakan counting sort bisa
didapatkan dari perhitungan sebagai berikut : Kalang pertama membutuhkan waktu O(k),
kalang kedu membutuhkan waktu O(n), kalang ketiga membutuhkan
waktu O(k), dan kalang keempat membutuhkan waktu O(n).
Jadi secara
total membutuhkan waktu O(k+n), yang seringkali dianggap k =
O(n), sehingga waktu total yang dibutuhkan menjadi O(n)
Tidak ada komentar:
Posting Komentar