Pengurutan data adalah
proses yang dilakukan terhadap himpunan data, disusun sedemikian rupa sehingga
diperoleh data baru berurut. Pada umumnya ada dua macam pengurutan, yaitu (1)
pengurutan secara ascending (urut
naik) dan (2) pengurutan secara descending
(urut turun). Proses pengurutan seluruh data berada dalam memori disebut internal sorting. Sedangkan bila data
tidak berada di dalam memori disebut external
sorting.
Masalah
utama dalam pengurutan adalah bagaimana mendapatkan metode terbaik yang akan
memberikan jumlah operasi pemindahan data paling minimum. Kedua operasi
tersebut akan mempengaruhi algoritma pengurutan data. Umumnya kompleksitas
algoritma biasa dilihat dari waktu (time
complexcity) atau ruang (space
complexcity).
Algoritma
pengurutan data yang akan diuraikan dan dilakukan dalam praktikum struktur data
ini hanya mencangkup tiga metode pengurutan data, yaitu : (1) insert
sort (pengurutan penyisipan), (2) selection
sort (pengurutan pemilihan), dan (3) bubble
sort (pengurutan gelembung). Berikut ini merupakan penjelasannya.
1. Insert Sort (Pengurutan
Penyisipan)
Metode
ini dilakukan dengan cara menyisipkan elemen larik pada posisi yang tepat.
Prinsip kerja metode ini membagi dua data sedemikian rupa sehingga pada bagian
pertama menampung data yang sudah terurut dan bagian kedua menampung data yang
belum terurut. Selanjutnya diambil satu data dari bagian yang belum terurut dan
dilakukan penyisipan ke bagian yang sudah terurut.
Procedure
insertionsort (var A : tabel; N : integer);
{IS : Tabel A terdefinisi dengan N
adalah banyaknya data}
{FS : Tabel A yang terurut membesar}
Var
pass, i : integer; {counter}
temp : integer; {variabel untuk nilai sementara}
Begin
for pass := 2 to N do
begin
temp := A[pass];
i := pass-1;
while ((temp < A[i]) and
(I > 1) do
begin
A[i+1] := A[i];
i := i-1;
end;
if (temp <
A[i]) then
begin
A[i+1] := A[i];
i := i-1;
end;
A[i+1] := temp;
End;
End;
2. Selection Sort
(Pengurutan Pemilihan)
Metode
minimum dan maximum sort merupakan metode yang tergolong dalam selection sort.
Pada minimum sort, untuk meletakkan
data pada posisi ke-1 dilakukan dengan mencari nilai minimum data mulai dari
posisi ke-1 sampai dengan posisi ke-N dengan N adalah banyaknya data. Untuk maximum sort, dilakukan dengan
menggunakan nilai maksimum.
Procedure
switch (var A, B : Tabel);
{IS : Tabel A dan B berisi nilai missal
A = x dan B = y}
{FS : A = y dan B = x}
Var
Temp : integer;
{variabel untuk nilai sementara}
Begin
Temp
:= A;
A
:= B;
B
:= temp;
End;
Procedure
minimumSort (var A : Tabel; N : integer);
{IS : Tabel A terdefinisi dengan N
adalah banyaknya data}
{FS : Tabel A yang terurut membesar}
Var
pass, i : integer; {counter}
imin : integer; {variabel untuk indeks nilai minimum}
begin
imin := pass;
for
i := pass +1 to N do
begin
if
(A[imin] > a[i]) then imin := i;
if
(imin <> pass) then switch
(A[pass], A[imin]);
end;
end;
end;
3. Bubble Sort
(Pengurutan Gelembung)
Prinsip
dari bubble sort adalah melatakkan nilai pada posisi ke-I dengan
menggelembungkan atau mengangkat nilai minimum dari i+1 sampai dengan N.
Procedure
bubblesort (var A : Tabel; N : integer);
{IS : Tabel A terdefinisi dengan N
adalah banyaknya data}
{FS : Tabel A yang terurut membesar}
Var
Pass, i : integer {counter}
Tukar : Boolean {true jika untuk satu kali pass terjadi pertukaran}
Begin
Tukar := true;
Pass := 1;
While
((tukar) and (pass < N)) do
Begin
Tukar := false;
For
i := N downto pass+1 do
Begin
If (A[i] < [i-1]) then
Begin
Switch
(A[i], A[i-1]);
Tukar := true;
End;
End;
End;
End;
Implementasi dari
ketiga metode sorting tersebut dilakukan menggunakan data sebagai berikut.
Const
NMax : 100;
Type
Tabel = array[1..NMax]
of integer;
*****
program
sorting;
uses
crt;
const
max = 100;
type
data = array [1..max] of integer;
type
dosen = record
nip
:integer;
nama
:string[50];
end;
dsn
= array [1..max] of dosen;
var
d :
dsn;
n, s: integer;
pil,pil1,pil2 : char;
procedure
insertsort(var c:dsn;n:integer;pil:integer);
var
pass,i
:integer;
temp
:integer;
temp1 :string;
begin
for pass:=2 to n do
begin
temp
:=c[pass].nip;
temp1 :=c[pass].nama;
i:=pass-1;
if pil = 1 then
begin
while ((temp < c[i].nip) and (i > 1))
do
begin
c[i+1].nip := c[i].nip;
c[i+1].nama := c[i].nama;
i := i - 1;
end;
if(temp < c[i].nip)then
begin
c[i+1].nip := c[i].nip;
c[i+1].nama := c[i].nama;
i := i - 1;
end;
c[i+1].nip := temp;
c[i+1].nama := temp1;
end
else
if pil = 2 then
begin
while ((temp > c[i].nip) and (i > 1))
do
begin
c[i+1].nip := c[i].nip;
c[i+1].nama := c[i].nama;
i := i - 1;
end;
if(temp > c[i].nip)then
begin
c[i+1].nip := c[i].nip;
c[i+1].nama := c[i].nama;
i := i - 1;
end;
c[i+1].nip := temp;
c[i+1].nama := temp1;
end;
end;
end;
procedure
switch(var c:dsn; pass, i : integer);
var
temp1 : integer;
temp2, temp3 : string;
begin
temp1:=c[pass].nip;
temp2:=c[pass].nama;
c[pass].nip:=c[i].nip;
c[pass].nama:=c[i].nama;
c[i].nip:=temp1;
c[i].nama:=temp2;
end;
procedure
minsort(var c:dsn;n:integer);
var
pass,i :integer;
imin
:integer;
begin
for pass:=1 to n-1 do
begin
imin := pass;
for i := pass + 1 to n do
if ( c[imin].nip > c[i].nip ) then
imin:=i;
if (imin <> pass)then
switch( c, pass,imin);
end;
end;
procedure
maxsort(var c:dsn;n:integer);
var
pass,i :integer;
imin
:integer;
begin
for pass:=1 to n-1 do
begin
imin:=pass;
for i:=pass+1 to n do
if (c[imin].nip < c[i].nip) then imin:=i;
if (imin <> pass)then
switch(c,pass,imin);
end;
end;
procedure
bubblesortmin(var c:dsn;n:integer);
var
pass,i
:integer;
tukar :boolean;
begin
tukar:=true;
pass :=1;
while((tukar)
and (pass < n)) do
begin
tukar := false;
for i := n downto pass+1 do
if (c[i].nip < c[i-1].nip) then
begin
switch(c,pass,i);
tukar := true;
end;
end;
end;
procedure
bubblesortmax(var c:dsn;n:integer);
var
pass,i
:integer;
tukar :boolean;
begin
tukar:=true;
pass :=1;
while((tukar)
and (pass > n)) do
begin
tukar := false;
for i := n downto pass+1 do
if (c[i].nip > c[i-1].nip) then
begin
switch(c,pass,i);
tukar := true;
end;
end;
end;
begin
clrscr;
writeln('================================');
writeln('-----------------Sorting
Method------------------');
writeln('================================');
writeln('
1. Insertion Sorting ');
writeln('
2. Selection Sorting ');
writeln('
3. Bubble Sorting ');
writeln('
4. Exit ');
writeln('================================');
writeln;
write
('Pilihan : ');readln(pil);
writeln;writeln;
clrscr;
pil1 := 'Y';
s := 0;
repeat
s := s + 1;
write('NIP Dosen ke-',s,' : ');readln(d[s].nip);
write('Nama Dosen ke-',s,' : ');readln(d[s].nama);
writeln;
write('Masukkan Data lagi ? : ');readln(pil1);
writeln;
clrscr;
until not (pil1 in ['y','Y']);
if pil = '1' then
begin
writeln('Pilihan Sorting : ');
writeln('1. Ascending');
writeln('2. Descending');
writeln;
write
('Masukkan pilihan (1/2)? ');readln(pil2);
if pil2 = '1' then
insertsort(d,s,1)
else if pil2 = '2' then
insertsort(d,s,2)
else
writeln('Inputan Karakter
Salah!');
for n := 1 to s do
begin
writeln;
writeln('Nama : ',d[n].nip);
writeln('NIP : ',d[n].nama);
writeln;
end;
end
else if pil = '2' then
begin
writeln('Pilihan Sorting : ');
writeln('1. Ascending');
writeln('2. Descending');
writeln;
write
('Masukkan pilihan (1/2)? '); readln(pil2);
if pil2 = '1' then
minsort(d,s)
else if pil2 = '2' then
maxsort(d,s)
else
writeln('Inputan Karakter
Salah..!!!');
for n := 1 to s do
begin
writeln;
writeln('Nama : ',d[n].nip);
writeln('NIP : ',d[n].nama);
writeln;
end;
end
else if pil = '3'then
begin
writeln('Pilihan Sorting : ');
writeln('1. Ascending');
writeln('2. Descending');
writeln;
write
(Masukkan pilihan (1/2)? ');readln(pil2);
if pil2 = '1' then
bubblesortmin(d,s)
else if pil2 = 2' then
bubblesortmax(d,s)
else
writeln('Inputan Karakter
Salah..!!!);
for n := 1 to s do
begin
begin
writeln;
writeln('Nama : ',d[n].nip);
writeln('NIP : ',d[n].nama);
writeln;
end;
end
end
else
if pil2 = '4 then
exit
readkey;
end.
Tidak ada komentar:
Posting Komentar