Pada kesempatan ini akan dibahas beberpa implementasi dari algoritma pengurutan seperti bubble sort, selection sort, insert sort, dan quick sort. Berikut adalah beberapa implementasi algoritma pengurutan dalam bahasa Pascal :
Bubble Sort
procedure bubblesort(var d:array100; c:integer);
var
i,j:integer;
begin
for i:=1 to c-1 do
for j:=c downto i+1 do
if(d[j] < d[j-1]) then
swap(d[j],d[j-1]);
end;
Selection Sort
procedure selectionsort(var d:array100; c:integer);
var
lok,i,j:integer;
begin
for i:=1 to c-1 do
begin
lok:=i;
for j:= i+1 to c do
if(d[j]<d[lok]) then
lok:=j;
swap(d[i],d[lok]);
end;
end;
procedure swap(var a,b:integer);
var
t:integer;
begin
t:=a;
a:=b;
b:=t
end;
Insert Sort
procedure InsertionSort(var Data:Tdata);
var i,j,temp : integer;
begin
for i:=1 to N-1 do begin
temp:=Data[i];
j:=i;
while (j>0) and (temp < Data[j-1]) do begin
Data[j]:=Data[j-1];
j:=j-1;
end;
Data[j]:=temp;
end;
end;
Quick Sort
procedure quicksort(var d:array100; a,b:integer);
var
a1,b1,pivot : integer;
begin
a1:=a;
b1:=b;
pivot := d[(a+b) div 2];
repeat
while (d[a1] < pivot) do
inc(a1);
while (d[b1] > pivot) do
dec(b1);
if(a1 <= b1) then
begin
swap(d[a1],d[b1]);
inc(a1);
dec(a1);
end;
until (a1 <= b1);
if (a < b1) then
quicksort(d,a,b1);
if (a1 < b) then
quicksort(d,a1,b);
end;
Keterangan :
array100 adalah type array [1..100] of integer harus dideklarasikan terlebih dahulu pada type.
c adalah jumlah jumlah data pada array.
Read More... Pencarian Linier/Sekuensial
Pencarian Linier atau
Pencarian Sekuensial (Bah.Ingg:
Linear Search atau
Sequential Search) adalah pencarian data secara linier (garis lurus), artinya adalah pencarian dilakukan secara teratur (secara sekuensial) dari awal sampai akhir data (atau bisa juga dari akhir ke awal data). Berikut adalah 2 fakta penting tentang pencarian linier:
- Hanya bagus untuk dipakai pada data yang acak/tak terurut (unsorted)
- Kompleksitasnya adalah O(n)
Berikut adalah implementasi dari pencarian linier memakai
function untuk pencarian data bertipe
string:
type
TArrString = array of string;
function CariLinier(var Arr: TArrString; Cari: string): LongInt;
var
Idx, Batas, Ketemu: LongInt;
begin
Idx:= Low(Arr);
Batas:= High(Arr);
Ketemu:= -1;
while (Idx <= Batas) and (Ketemu = -1) do begin
if Arr[Idx] = Cari then Ketemu:= Idx;
Inc(Idx);
end;
CariLinier:= Ketemu;
end;
Penjelasannya:
type
TArrString = array of string;
function CariLinier(var Arr: TArrString; Cari: string): LongInt;
var
Idx, Batas, Ketemu: LongInt;
begin
Idx:= Low(Arr); // Dapatkan index terendah dari array
Batas:= High(Arr); // Dapatkan index tertinggi dari array
Ketemu:= -1; // Asumsi awal: belum ketemu
// Lakukan perulangan selama data yang dicek belum habis
// (Idx <= Batas) dan belum ketemu (Ketemu = -1)
while (Idx <= Batas) and (Ketemu = -1) do begin
// Jika array di posisi Idx adalah data yang dicari, maka
// posisi Ketemu ada di posisi Idx saat ini
if Arr[Idx] = Cari then Ketemu:= Idx;
// Naikkan posisi Idx (Cek data berikutnya)
Inc(Idx);
end;
CariLinier:= Ketemu;
end;
Pencarian Biner
Pencarian Biner (Bah.Ingg:
Binary Search) adalah pencarian data secara eliminasi biner berulang/terus-menerus. Maksudnya adalah pada saat pencarian data, 1 kelompok data yang sudah urut dibagi menjadi 2 subkelompok. Lalu salah satu subkelompok dieliminasi, sehingga ruang lingkup pencarian data menjadi lebih sedikit. Kemudian subkelompok yang tersisa dibagi lagi menjadi 2 subkelompok lagi, demikian dilakukan secara berulang-ulang.
Sebagai contoh, misalnya diinginkan mencari data nama
Irawan di sekumpulan data nama yang sudah terurut. Apabila kelompok data ini dibagi 2, ternyata di bagian tengah terdapat nama
Leny. Maka subkelompok data sesudah
Leny akan dieliminasi, karena tidak mungkin nama
Irawan akan terdapat pada data huruf L s/d Z. Sedangkan, subkelompok sebelum
Leny, kemudian akan dibagi 2 lagi, dan diperiksa ulang. Ternyata kali ini di bagian tengah terdapat nama
Gery. Maka kelompok data sebelum
Gery akan dieliminasi, karena tidak mungkin terdapat data
Irawan pada huruf A s/d G. Demikian seterusnya terjadi, proses eliminasi ruang lingkup pencarian data menjadi semakin sedikit secara berulang.
Berikut adalah 3 fakta penting mengenai pencarian biner:
- Hanya bisa berfungsi pada data yang sudah terurut (sorted), ini adalah syarat mutlak dari pencarian biner
- Merupakan salah satu contoh penerapan cara kerja dari konsep Divide and Conquer
- Kompleksitasnya adalah O(lg n)
Ini adalah implementasi dari pencarian biner memakai
function untuk pencarian data bertipe
string:
type
TArrString = array of string;
function CariBiner(var Arr: TArrString; Cari: string): LongInt;
var
Awal, Akhir, Tengah, Ketemu: LongInt;
begin
Awal:= Low(Arr);
Akhir:= High(Arr);
Ketemu:= -1;
while (Awal <= Akhir) and (Ketemu = -1) do begin
Tengah:= (Awal + Akhir) shr 1;
if Arr[Tengah] = Cari then Ketemu:= Tengah else begin
if Cari < Arr[Tengah] then Akhir:= Tengah-1 else Awal:= Tengah+1;
end;
end;
CariBiner:= Ketemu;
end;
Penjelasannya:
type
TArrString = array of string;
function CariBiner(var Arr: TArrString; Cari: string): LongInt;
var
Awal, Akhir, Tengah, Ketemu: LongInt;
begin
Awal:= Low(Arr); // Posisi awal pencarian
Akhir:= High(Arr); // Posisi akhir pencarian
Ketemu:= -1; // Asumsi awal: belum ketemu
// Ulangi selama ruang lingkup pencarian masih ada (Awal <= Akhir)
// dan data yang dicari belum ketemu (Ketemu = -1)
while (Awal <= Akhir) and (Ketemu = -1) do begin
// Hitung lokasi data yang di tengah ruang lingkup pencarian
Tengah:= (Awal + Akhir) shr 1;
{ Cek apakah data yang di tengah merupakan data yang dicari, apabila bukan, pindahkan ruang lingkup pencarian,
kalau data ada di sebelah kiri (lebih kecil <),
maka batas akhir yang dikurangi (Akhir:= Tengah - 1),
sedangkan jika data ada di sebelah kanan,
maka batas awal yang ditambah (Awal:= Tengah + 1) }
if Arr[Tengah] = Cari then Ketemu:= Tengah else begin
if Cari < Arr[Tengah] then Akhir:= Tengah-1 else Awal:= Tengah+1;
end;
end;
CariBiner:= Ketemu;
end;
