Hai semuanya pada kesempatan kali ini saya akan menjelaskan salah satu pengurutan dalam suatu algoritma . Pada materi sebelumnya kita sudah belajar pengurutan merge ( Merge Sort) dan pada post kali ini saya akan menjelaskan pengurutan shell (Shell Sort) , mungkin kalian sudah tahu apa itu Shell Sort atau dari kalian ada yang belum paham apa itu Shell Sort . Yapss , disini saya akan mengingatkan kembali apa itu Shell Sort bagi yang sudah tahu sebelumnya dan menjelaskan bagi yang belum mengerti apa itu Shell Sort .
Algoritma
pengurutan Shell diberi nama sesuai penemunya (Donald Shell tahun 1959) [PAR95]
. Algoritma ini merupakan perbaikan terhadap metode pengurutan sisip. Kelemahan
metode pengurutan sisip sudah disebutkan pada post sebelumnya . Metode Shell
Sort disebut juga dengan metode pertambahan menurun (diminshing icrement
short). Metode ini mengurutkan data dengan cara membandungkan suatu data lain
yang memiliki jarak tertentu sehingga membentuk sebuah sub-list, kemudian
dilakukan pertukaran apabila diperlukan.
Untuk melakukan
pengurutan , kita mengurutkan larik setiap k elemen dengan metode pengurutan
sisip, misalnya kita urutkan setiap 5 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 elemen k = 1.
Karena setiap nilai step selalu berkurang maka Shell Short disebut dengan
metode pengurutan penambahan penurunan.
Contoh :
Data sebelum pengurutan
13
|
40
|
29
|
60
|
80
|
21
|
15
|
37
|
45
|
88
|
22
|
46
|
18
|
Pass 1 (step = 5): Urutkan
setiap lima elemen
Data
|
13
|
40
|
29
|
60
|
80
|
21
|
15
|
37
|
45
|
88
|
22
|
46
|
18
|
Index
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
|
|
|
|
|
|
|||||||||||
13
|
..........................................
|
21
|
..........................................
|
22
|
|||||||||
15
|
..........................................
|
22
|
..........................................
|
40
|
|||||||||
18
|
..........................................
|
29
|
..........................................
|
37
|
|||||||||
45
|
..........................................
|
60
|
|||||||||||
Hasil pass pertama : 13, 15, 18, 45, 80, 21, 22, 29, 60, 88, 22, 40, 37
Pass 2 (step=3): Urutkan setiap tiga elemen
Data
|
13
|
40
|
29
|
60
|
80
|
21
|
15
|
37
|
45
|
88
|
22
|
46
|
18
|
Index
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
|
|
|
|
|
|
|
|
||||||||||
13
|
...................
|
15
|
...................
|
18
|
...................
|
60
|
...................
|
88
|
|||||
22
|
...................
|
37
|
...................
|
40
|
...................
|
80
|
|||||||
21
|
...................
|
29
|
...................
|
45
|
...................
|
46
|
|||||||
Hasil pass kedua : 13, 22, 21, 15, 37, 29, 18, 40, 45, 60, 80, 46, 88
Pass 3 (step=1): Urutkan setiap 1 elemen
Data
|
13
|
40
|
29
|
60
|
80
|
21
|
15
|
37
|
45
|
88
|
22
|
46
|
18
|
Index
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13
|
15
|
18
|
21
|
22
|
29
|
37
|
40
|
45
|
46
|
60
|
80
|
88
|
Hasil Pass ketiga :
13, 15, 18, 21, 22, 29, 37, 40, 45, 46, 60, 80, 88
Perhatikan bahwa pada
pass yang terakhir (step = 1), pengurutan Shell menjadi sama dengan pengurutan
sisip biasa .
Nilai-nilai step
seperti 5,3 dan 1 bukanlah angka “sihir” (magic). Kita dapat memilih
nilai-nilai step yang lain 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 algoritma Shell, namum tidak seorang pun yang dapat membuktikan bahwa
pemilihan step tertentu paling bagus diantara pemilihan step yang lain [KRU91].
Algoritma
Pengurutan Shell
Procedure ShellSort(var L : LarikInt; n : integer);
{ Mengurutkan elemen larik
L[1..n] sehingga tersusun menaik dengan metode pengurutan Shell. }
{ I.S : Elemen-elemen larik L
sudah terdefinisi nilainya }
{ F.S : 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; {endwhile}
end;
{endprocedure}
Kelebihan Shell Sort
1.
Algoritma ini sangat rapat dan mudah
diimplementasikan
2. Operasi
pertukarannya hanya dilakukan sekali saja
3. Waktu
pengurutannya dapat lebih ditekan
4. Mudah
menggabungkannya kembali
5.
Kompleksitas selection sort relatif lebih kecil
Kekurangan Shell Sort
1.
Membutuhkan method tambahan
2.
Sulit untuk membagi masalah
EmoticonEmoticon