Algoritma
quick sort diperkenalkanpertama kali oleh C.A.R.
Hoare padatahun 1960, dandimuatsebagaiartikel di “Computer
Journal 5” pada April 1962. Quick sort adalahalgoritma sorting yang
berdasarkanpembandingandenganmetoda divide-and-conqueror. Disebut Quick Sort,
karenaAlgoritma quick sort mengurutkandengansangatcepat.
Algoritma
quick sort mengurutkandengansangatcepat,
namunalgoritmainisangatkomplexdandiprosessecararekursif.
Sangatmemungkinkanuntukmenulisalgoritma yang
lebihcepatuntukbeberapakasuskhusus, namununtukkasusumum, sampaisaatinitidakada
yang lebihcepatdibandingkanalgoritma quick sort.
Quick Sort merupakansuatualgoritmapengurutan data yang menggunakanteknikpemecahan data menjadipartisi-partisi, sehinggametodeinidisebutjugadengannama partition exchange sort. Untukmemulaiirterasipengurutan, pertama-tama sebuahelemendipilihdaridata, kemudianelemen-elemen data akandiurutkandiatursedemikianrupasehingganilaivariabelSementaraberada di suatuposisike I yang memenuhikondisisebagaiberikut :
1.
Semuaelemen di
posisike 1 sampaidenganke I-1 adalahlebihkecilatausamadenganSementara.
2.
Semuaelemen di
posisike I+1 sampaidenganke N adalahlebihbesaratausamadenganSementara.
Sebagaicontoh,
data yang akandiurutkansejumlah 12 elemensebagaiberikut :
Misalnya
element yang dipilihadalah element yang pertama, makavariabelSementarabernilai
33. Setelahdiatur, makanilai 33 akanmenempatiposisike I, yaituposisiurutanke 6
sebagaiberikut :
Tampakbahwakondisiberikutterpenuhi,
yaitu :
1.
Semuaelemen di
posisike 1 sampaidenganposisike 5 (10, 25, 18, 7,dan 5)
akanlebihkecilatausamadengannilai 33 yang dipilih.
2.
Semuaelemen di
posisike 7 sampaidenganke 12 (57,99,55,45,40 dan 50) aka
lebihbesaratausamadengannilai 33 yang dipilih.
Dengandemikian, data
tersebutakanterpecahmenjadi 2 partisi, sebagaiberikut :
(10 25 18 7 5) 33 (57
99 55 45 40 50)
Proses
inidiulangikembaliuntukmasing-masingpartisi data, yaitu:
untuk
data (10, 25, 18, 7, 5) dan data (57, 99, 55, 45, 40, 50).
Untukpartisi
yang pertama, bilanilaiSementara yang diambiladalah data
pertamakembalidalampartisibersangkutan, yaitu 10 dandiaturkembalisedemikianrupa,
makanilai data yang dipilihakanterletak di posisisebagaiberikut:
(5 7) 10 (18 25)
33 (57 99 55 45 40 50)
Untukmengurutkanmasing-masingpartisi,
maka proses
tersebutdiulangikembalidantiap-tiappartisidipecah-pecahkembalilebihlanjut.
Kurung yang menutupipartisimenunjukkan data yang
belumurutdanperludiurutkankembali. Sedang data yang
tidakberadadiantaratandakurungmerupakan data yang sudahdiurut.
Iterasiselanjutyasampaididapatkan data yang
telahurutsemuanyaadalahsebagaiberikutini.
5 ( 7)
10 (18 25) 33 (57 99 55 45 40 50)
5
7 10 18 (25) 33 (57 99 55 45 40 50)
5
7 10 18 25 33 (50 40 55 45) 57 (99)
5
7 10 18 25 33 (50 40 55 45) 57 99
5
7 10 18 25 33 (45 40) 50 (55) 57 99
5
7 10 18 25 33 (45 40) 50 55 57 99
5
7 10 18 25 33 40 (45) 50 55 57 99
5
7 10 18 25 33 40 45 50 55 57 99
Contoh program:
program QUIKSORT;
uses crt;
type larik=array[1..10] of integer;
var i:integer;
data:larik;
ch : string;
procedure input_data;
begin
clrscr;
writeln (' PENGURUTAN DENGAN METODE QUICK SORT');
writeln (' -------------------------------------------');
writeln;
writeln;
writeln ('masukan 10 data');
writeln ('=================');
writeln;
for i := 1 to 10 do {input 10 data}
begin
write ('data ke-',i,'=');
readln (data[i]);
end;
clrscr;
writeln;
writeln ('************************************');
for i:= 1 to 10 do
write(data[i],' ');
writeln;
writeln('*************************************');
writeln;
writeln;
writeln ;
writeln ( 'Hasil data yang telah diurutkan:');
writeln ('=====================================');
end;
procedure TUKARKAN(var d,b:integer);
var t:integer;
begin
t:=d;
d:=b;
b:=t;
end;
procedure quicksort(var A:larik; aw,ak:integer);
var i,j:integer;
procedure atur;
begin
I:= Aw + 1 ;
J:= Ak ;
while A[I] < A[Aw] do inc (I);
while A[j] >A [Aw] do dec (J);
while I < J do
begin
TUKARKAN (A[I],A[J]);
while A[I] < A[Aw] do inc(I);
while A[J] > A[Aw] do dec(J);
end;
TUKARKAN (A [Aw], A [J] )
END;
BEGIN
IF Aw < Ak THEN
BEGIN
ATUR;
QUICKSORT (A,Aw,J-1);
QUICKSORT (A,J+1,Ak)
END
END;
begin
repeat
input_data;
quicksort(data,1,10);
for i:=1 to 10 do
write(data[i],' ');
begin
end;
writeln;
writeln ('======================================');
writeln;
writeln;
writeln;
writeln ('di ulang lagi apa enggak...???? (Y/N)');
readkey;
ch:= readkey;
writeln;
until
(ch='n') ;
gotoxy(10,23); writeln ('>>>> Thank You <<<<<<<<');
readkey;
end.
Shell Sort (Metode
Shell)
Metodeinidisebutjugadenganmetodepertambahanmenurun
(diminishing increment). Metodeinidikembangkanoleh Donald L. Shell padatahun
1959, sehinggaseringdisebutdenganMetode Shell Sort. Metodeinimengurutkan data
dengancaramembandingkansuatu data dengan data lain yang memilikijaraktertentu,
kemudiandilakukanpenukaranbiladiperlukan. Proses pengurutandenganmetode Shell
dapatdijelaskansebagaiberikut :
Metodeinimengurutkan data
dengancaramembandingkansuatu data lain yang
memilikijaraktentusehinggamembentuksebuah sub-list-,
kemudiandilakukanpenukaranapabiladiperlukan.
Pertama-tama adalahmenentukanjarakmula-muladari data yang
akandibandingkan, yaitu N / 2.
Data
pertamadibandingkandengan data denganjarak N / 2.
Apabila data
pertamalebihbesardari data ke N / 2 tersebutmakakedua data tersebutditukar.
Kemudian data keduadibandingkandenganjarak yang samayaitu N / 2.
Demikianseterusnyasampaiseluruh
data dibandingkansehinggasemua data ke-j selalulebihkecildaripada data ke-(j +
N / 2).
Pada
proses berikutnya, digunakanjarak (N / 2) / 2 atau N / 4. Data
pertamadibandingkandengan data denganjarak N / 4. Apabila data
pertamalebihbesardari data ke N / 4 tersebutmakakedua data tersebutditukar.
Kemudian data keduadibandingkandenganjarak yang samayaitu N / 4.
Demikianlahseterusnyahinggaseluruh data dibandingkansehinggasemua data ke-j
lebihkecildaripada data ke-(j + N / 4).
Pada proses berikutnya, digunakanjarak (N / 4) / 2 atau N / 8. Demikianseterusnyasampaijarak yang digunakanadalah 1.
Pada proses berikutnya, digunakanjarak (N / 4) / 2 atau N / 8. Demikianseterusnyasampaijarak yang digunakanadalah 1.
Algoritmametode
Shell dapatdituliskansebagaiberikut :
1. Jarak = N
2. Selama (Jarak> 1) kerjakanbaris 3 sampaidengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakanbaris 4 sampaidengan 8 selamaSudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakanbaris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] makatukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
1. Jarak = N
2. Selama (Jarak> 1) kerjakanbaris 3 sampaidengan 9
3. Jarak = Jarak / 2. Sudah = false
4. Kerjakanbaris 4 sampaidengan 8 selamaSudah = false
5. Sudah = true
6. j = 0
7. Selama (j < N – Jarak) kerjakanbaris 8 dan 9
8. Jika (Data[j] > Data[j + Jarak] makatukar Data[j],
Data[j + Jarak].
Sudah = true
9. j = j + 1
Jarak yang dipakaididasarkanpada increment
value atau sequence number K.Misalnya sequence number yang dipakaiadalah 5,3,1.
tidakadapembuktianyadisinibahwabilangantersebutadalah sequence number terbaik.
Setiap sup-list berisisetiap element
ke-K darikumpulan element yang asli.
Sebagaicontoh
:
Jika K=5 maka sub-list
adalahsebagaiberikut :
–
s[0] s[5] s[10]…
–
s[1] s[6] s[11]…
–
s[2] s[7] s[12]…
–
dst
Begitujuga
K=3 maka sub-listnyaadalah :
–
s[0] s[3] s[6]…
–
s[1] s[4] s[7]…
–
dst
Proses
shell short
– urutkan sekumpulan
element dibawah ini, misalnya diberikan sequence number : 5,3,1
Contoh
lainter dapat elemen sebagai berikut :
23
45 12 24 56 34 27 23 16
Proses
pengurutanmenggunakanmetoda Shell Dalamhalinielemen yang digaisbawahadalahelemen
yang dibandingkandankemudianditukar, jikaperlu.
Contoh procedure program:
Procedure Shell(Var Temp : Data; JmlData : Integer);
Var I,J, Jarak : Integer;
Begin
Jarak := JmlData Div 2;
While Jarak > 0 Do
Begin
For I:=1 To JmlData-Jarak Do
Begin
J := I + Jarak;
If Temp[I] > Temp[J] Then
SWAP(Temp[I], Temp[Lok]);
End;
Jarak := Jarak Div 2;
End;
End;
RADIX
SORT
Radix Sort
merupakansalahsatualgoritma Non-Comparasion Sort (pengurutantanpapembandingan).
Proses yang dilakukandalammetodeiniadalahmengklasifikasikan/menyelesaikan data
sesuaidengankategoriterurut yang tertentu,
dantiapkategoridilakukanpengklasifikasianlagi, danseterusnyasesuaikebutuhan,
kemudiansubkategori-kategoriataubagian-bagiandari kategori
tersebutdigabungkankembali.
Secaraharfiah
Radix dapatdiartikansebagaiposisidalamangka, karenacarainipertamakalinyamengurutkannilai-nilai
yang dimasukan (input) berdasarkan radix pertamanya,
lalupengurutandilakukanberdasarkan radix keduanya, danbegituseterusnya.
Padasistemdesimal, radix adalah digit dalamangkadesimal. Misalnya, angka “169”
mempunyai 3 digit yaitu 1,6 dan 9.
Sayaakanmembeikancontohpenggunaanalgoritma
radix sort untukpengurutansebuahkumpulanbilanganbulatpositif, denganjumlah
digit maksimal3 :
Hasil pengkategorian tersebut lalu digabung kembali dengan metode konkatenasi menjadi
:
Kemudian pengkategorian dilakukan kembali,namun kali ini berdasar
digit keduaatau digit tengah, dan jangan lupa bahwa urutan pada tiap sub kumpulan data
harus sesuai dengan urutan kemunculanpada kumpulan data
Kemudianlangkahketiga,
atau langkah terakhir pada contoh ini adalah pengkategorian kembali berdasar digit yang
terkiri, atau yang paling signufikan
Yang kemudian dikonkatenasilagi menjadi
Algoritma dan Kompleksitas Waktu Radix Sort Implementasi dari algoritma tersebut dibuat menggunakan bahasa
Pascal, yang direalisasikan dengan menggunakan queue sebagai representasi tiap kategori
radix untuk pengkategorian. Array A adalah array input, dan array B adalah array
A yang sudah terurut.
Contoh program: