LAPORAN AKHIR PRAKTIKUM

STRUKTUR DATA

NAMA : SUPRIYANDI

NIM : DBC 113 170

KELAS : B

MODUL : IV (Pengurutan Data)

JURUSAN TEKNIK INFORMATIKA

FAKULTAS TEKNIK

UNIVERSITAS PALANGKA RAYA

2014

BAB I

TUJUAN DAN LANDASAN TEORI

A. Tujuan Praktikum

1. Mengetahui implementasi beberapa metode pengurutan data.

2. Mampu menerapkan metode pengurutan data pada sebuah program.

3. Mengetahui perbandingan kompleksitas beberapa metode pengurutan

data.

B. Landasan Teori

Pengurutan data adalah proses yang dilakukan terhadap himpunan

data, disusun sedemikian rupa sehingga diperoleh data baru terurut. 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 complexity) atau ruang (space complexity).

Algoritma pengurutan data yang akan diuraikan dan dilakukan dalam

praktikum struktur data ini hanya mencakup tiga metode pengurutan data,

yaitu : (1) insertion sort (pengurutan penyisipan), (2) selection sort

(pengurutan pemilihan), dan (3) bubble sort (pengurutan gelembung). Berikut

ini merupakan penjelasannya.

1. Insertion 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 InsertonSort (Var A : Tabel, N : integer);

{IS : Tabel A terdefinisi dengan N adalah banyaknya

data}

{FS : Tabel A berurut 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;

If ((temp < A[i] then

Begin

A[i] + 1 := A[i];

i := i 1;

End;

i := [i + 1] := temt;

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

pad posisi ke-i dilakukan dengan mencari nilai minimum data mulai dari

posisi ke-i 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 banayaknya

data}

{FS : Tabel A terurut membesar}

Var

Pass, i : integer;

Imin : integer;

Begin

For pass := 1 to N-1

Begin

Imin := pass;

For i := pass + 1 to N do

Begin

If (A[imin] > A[i]) Then imin := i;

If (i.min pass) then switch

(A[pass], A[imin]);

End;

End;

End;

3. Bubble Sort (Pengurutan Gelembung)

Prinsip dari buuble sort adalah meletakkan 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 banayakna

data}

{FS : Tabel A 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] < A[i-1] then

Begin

Switch (A[i], A[i-1]));

Tukar := true;

End;

End;

End;

End;

Implementasinya dari ketiga metode sorting tersebut dilakukan

menggunakan data sebagai berikut :

Const

NMAX = 100;

Type

Tabel = Array[1..NMAX] of integer;

BAB II

LANGKAH KERJA

Buatlah sebuah program dengan ketentuan sebagai berikut :

1. Pengurutan (sorting) menggunakan ketiga metode :

a. Insertion sort

b. Selection sort

c. Bubble sort

2. Masukan awal adalah data bertipe record mahasiswa dengan elemen :

NIM : integer;

Nama : string[30];

Alamat : string[50];

3. Proses pengurutan bisa dipilih berdasarkan NIM atau Nama secara ascending.

4. Keluaran adalah data yang telah diurutkan.

BAB III

PEMBAHASAN

Pada Modul ini, kita disuruh membuat sebuah program untuk menampilkan

data mahasiswa dengan menggunakan tiga metode yaitu insertion sort, selection

sort dan bubble sort. Program ini menggunakan pengurutan NIM atau mahasiswa

secara ascending.

Berikut merupakan listing program :

Program Pengurutan_Data_Mahasiswa;

Uses crt;

Label a;

Const max = 100;

Type data = array [1..max] of integer;

Type mahasiswa = record

nim :integer;

nama :string [30];

alamat :string [50];

End;

mhs=array [1..max] of mahasiswa;

Var

m :mhs;

n :integer;

s,p,pilih,pil :integer;

z :byte;

Procedure insertsort(var c:mhs;n:integer);

Var

pass,i :integer;

temp :integer;

temp1,temp2 :string;

Begin

For pass:=2 to n do

Begin

temp:=c[pass].nim;

temp1:=c[pass].nama;

temp2:=c[pass].alamat;

i:=pass-1;

While ((temp < c[i].nim) and (i > 1)) do

Begin

c[i+1].nim := c[i].nim;

c[i+1].nama := c[i].nama;

c[i+1].alamat := c[i].alamat;

i := i - 1;

End;

if(temp < c[i].nim)then

Begin

c[i+1].nim := c[i].nim;

c[i+1].nama := c[i].nama;

c[i+1].alamat := c[i].alamat;

i := i - 1;

End;

c[i+1].nim := temp;

c[i+1].nama := temp1;

c[i+1].alamat := temp2;

End;

End;

Procedure switch(var a,b:integer);

Var

temp:integer;

Begin

temp:=a;

a:=b;

b:=temp;

End;

Procedure minsort(var c:mhs;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].nim > c[i].nim) then imin:=i;

if (imin pass) then

switch(c[pass].nim,c[imin].nim);

End;

End;

Procedure bubblesort(var c:mhs;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].nim < c[i-1].nim) then

Begin

switch (c[i].nim,c[i-1].nim);

tukar := true;

End;

End;

End;

Begin

a: clrscr;

write('Banyaknya Data Mahasiswa : ');readln(n);

writeln;

For s:=1 to n do

Begin

write('NIM Mahasiswa Ke-',s,' : ');readln(m[s].nim);

write('Nama Mahasiwa Ke-',s,' : ');readln(m[s].nama);

write('Alamat Mahasiswa Ke-',s,' : ');readln(m[s].alamat);

writeln;

End;

writeln;

writeln('==Pilih Metode Pengurutan==');

writeln('1. Insertion Sorting');

writeln('2. Selection Sorting');

writeln('3. Bubble Sorting');

writeln('4. Exit');

writeln;

write('Pilihan Anda (1/2/3/4) :

');readln(pil);writeln;writeln;

Case pil of

1:Begin

clrscr;

writeln(' Insertion Sorting ');

writeln;

insertsort(m,n);

for s:=1 to n do

Begin

write('NIM : ');writeln(m[s].nim);

write('Nama : ');writeln(m[s].nama);

write('Alamat : ');writeln(m[s].alamat);

writeln;

End;

writeln;

End;

2:Begin

clrscr;

writeln(' Selection Sorting ');

writeln;

minsort(m,n);

for s:=1 to n do

Begin

write('NIM : ');writeln(m[s].nim);

write('Nama : ');writeln(m[s].nama);

write('Alamat : ');writeln(m[s].alamat);

writeln;

End;

writeln;

End;

3:Begin

clrscr;

writeln(' Bubble Sorting ');

writeln;

bubblesort(m,n);

for s:=1 to n do

Begin

write('NIM : ');writeln(m[s].nim);

write('Nama : ');writeln(m[s].nama);

write('Alamat : ');writeln(m[s].alamat);

writeln;

End;

writeln;

End;

4:Begin

writeln('Program Diakhiri..!!');

End;

else

writeln('Pilihan Anda Salah');

for s:=1 to n do Begin delay(60000);

End;

goto a;

End;

readkey;

End.

PEMBAHASAN :

Const max = 100;

Type data = array [1..max] of integer;

Type mahasiswa = record

nim :integer;

nama :string [30];

alamat :string [50];

End;

Const Max Adalah untuk menetapkan variabel baru dengan panjang karakter

100 (yang berarti bernilai konstan).

Pada tipe data terdapat fungsi array. Fungsi ini adalah fungsi atau tipe data

terstruktur yang merupakan kumpulan data yang bertipe sejenis. MAX pada

array merupakan penentuan jumlah maksimum suatu karakter inputan data

yang dapat diterima. Apabila data yang dimasukan melebihi jumlah karakter

yang ditentukan sebelumnya, maka program akan mengalami error.

Pada bagian Type Mahasiswa, merupakan tempat untuk menentukan type yang

akan kita gunakan. Sama seperti halnya pada penentuan variable. Untuk nim

mahasiswa yang kita tentukan, tipe data yang kita pakai adalah string, karena

untuk nim kita terdiri dari karakter huruf dan angka. Untuk jumlah karakter

pada nim dibuat terbatas yaitu hanya sebanyak 30 karakter inputan saja dan

pada alamat 50 karakter.

Var

m :mhs;

n :integer;

s,p,pilih,pil :integer;

z :byte;

Bagian ini merupakan penentuan variable global yang akan berpengaruh pada

keseluruhan program selain variable yang terdapat pada masing-masing

procedure. Tipe data yang digunakan masing-masing adalah mhs, integer, dan

byte.

Procedure insertsort(var c:mhs;n:integer);

Var

pass,i :integer;

temp :integer;

temp1,temp2 :string;

Begin

For pass:=2 to n do

Begin

temp:=c[pass].nim;

temp1:=c[pass].nama;

temp2:=c[pass].alamat;

i:=pass-1;

While ((temp < c[i].nim) and (i > 1)) do

Begin

c[i+1].nim := c[i].nim;

c[i+1].nama := c[i].nama;

c[i+1].alamat := c[i].alamat;

i := i - 1;

End;

if(temp < c[i].nim)then

Begin

c[i+1].nim := c[i].nim;

c[i+1].nama := c[i].nama;

c[i+1].alamat := c[i].alamat;

i := i - 1;

End;

c[i+1].nim := temp;

c[i+1].nama := temp1;

c[i+1].alamat := temp2;

End;

End;

Pada coding diatas kita menggunakan metode insertion sort, yaitu memilah data

yang akan diurutkan menjadi dua bagian, yang belum diurutkan (pertama), dan

yang telah diurutkan (kedua). Elemen pertama yang diambil dari bagian array

yang belum diurutkan dan kemudian diletakkan pada posisinya sesuai dengan

bagian lain dari array yang telah diurutkan. langkah ini dilakukan secara

berulang hingga tidak ada lagi elemen yang tersisa pada bagian array yang

belum diurutkan.

Metode ini mengurutkan data-data yang telah dibaca dan berikutnya secara

berulang akan menyisipkan data-data dalam array yang belum terbaca ke sisi

kiri array yang telah terurut.

Insertion Sort merupakan algoritma yang efisien untuk mengurutkan yang

mempunyai jumlah elemen sedikit.

Procedure switch(var a,b:integer);

Var

temp:integer;

Begin

temp:=a;

a:=b;

b:=temp;

End;

Procedure minsort(var c:mhs;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].nim > c[i].nim) then imin:=i;

if (imin pass) then

switch(c[pass].nim,c[imin].nim);

End;

End;

Coding diatas menggunakan metode pengurutan selection sort, yaitu metode

pengurutan dengan cara memilih elemen atau proses kerja dengan cara memilih

elemen terkecil untuk kemudian dibandingkan & ditukarkan dengan elemen

data awal dan seterusnya sampai dengan seluruh elemen, sehingga akan

menghasilkan pola data yang telah di short.

Procedure bubblesort(var c:mhs;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].nim < c[i-1].nim) then

Begin

switch (c[i].nim,c[i-1].nim);

tukar := true;

End;

End;

End;

Pada coding di atas kita menggunakan metode pengurutan bubble sort, yaitu

metode untuk meletakkan nilai pada posisi ke-i dengan menggelembungkan

atau mengangkat nilai minimum dari i+1 sampai dengan N.

Metode bubble sort adalah metode yang mendasarkan penukaran dua buah

elemen untuk mencapai keadaan urut. Metode ini adalah yang termudah, tetapi

paling tidak efisien.

Begin

tukar:=true;

pass:=1;

While((tukar) and (pass < n)) do

Begin

tukar := false;

for i := n downto pass+1 do

if (c[i].nim < c[i-1].nim) then

Begin

switch (c[i].nim,c[i-1].nim);

tukar := true;

End;

End;

End;

Dari potongan listing bubble sort di atas jika tukar = true, maka data tersebut =

1, dan jika tukar = false, maka data tersebut akan ditambah dengan angka 1.

Pada prosedur ini juga ada pemanggilan untuk prosedur switch switch

(c[i].nim,c[i-1].nim);.

Case pil of

1:Begin

clrscr;

writeln(' Insertion Sorting ');

writeln;

insertsort(m,n);

for s:=1 to n do

Begin

write('NIM : ');writeln(m[s].nim);

write('Nama : ');writeln(m[s].nama);

write('Alamat : ');writeln(m[s].alamat);

writeln;

End;

writeln;

End;

2:Begin

clrscr;

writeln(' Selection Sorting ');

writeln;

minsort(m,n);

for s:=1 to n do

Begin

write('NIM : ');writeln(m[s].nim);

write('Nama : ');writeln(m[s].nama);

write('Alamat : ');writeln(m[s].alamat);

writeln;

End;

writeln;

End;

3:Begin

clrscr;

writeln(' Bubble Sorting ');

writeln;

bubblesort(m,n);

for s:=1 to n do

Begin

write('NIM : ');writeln(m[s].nim);

write('Nama : ');writeln(m[s].nama);

write('Alamat : ');writeln(m[s].alamat);

writeln;

End;

writeln;

End;

4:Begin

writeln('Program Diakhiri..!!');

End;

else

writeln('Pilihan Anda Salah');

for s:=1 to n do Begin delay(60000);

End;

goto a;

End;

readkey;

End.

Listing program di atas adalah statemen Case Of , bagian ini merupakan bagian

untuk pendeklarasian secara ascending. Setelah kita memilih palihan kita pada

menu tadi kemudian kita akan diminta memilih Insertion Sort, Selection Sort,

dan Bubble Sort. Disini dilakukan pemanggilan-pemanggilan prosedur-

prosedur yang telah dideklarasi sebelumnya.

BAB IV

KESIMPULAN

Metode pengurutan data yang digunakan pada praktikum ini mencakup tiga metode

pengurutan data, yaitu :

1. Insertion Sort (Metode Penyisipan)

Metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat.

Prinsip kerjanya adalah dengan membagi dua data sedemikian rupa sehingga

pada bagian pertama menampung data yang sudah terurut dan bagian kedua

menampung data yang belum terurut.

2. Selection Sort (Metode Pemilihan)

Metode pemilihan untuk meletakkan data pada posisi yang ke-i maka dicari nilai

minimum data mulai dari posisi ke-i sampai posisi ke-N dengan N adalah banyak

data.

3. Bubble Sort (Metode Gelembung)

Metode untuk meletakkan nilai pada posisi ke-i dengan menggelembungkan atau

mengangkat nilai minimum dari i+1 sampai dengan N.

Metode Insertion Sort merupakan metode yang efisien untuk mengurutkan

yang mempunyai jumlah elemen sedikit.

Metode bubble sort adalah yang termudah, tetapi paling tidak efisien.

BAB V

DAFTAR ISI

2014.Modul Praktikum Struktur Data. Palangkaraya:Universitas Palangkaraya.

http://sovyan-nurzaman.blogspot.com/2012/06/selection-sort.html

http://sisinform-aaf1231072.blogspot.com/2013/02/pengertian-sorting.html

http://indra-sijo.blogspot.com/2011/01/program-insertion-sort-untuk-pascal.html

BAB VI

LAMPIRAN

Coding :

Hasil Output memasukkan data :

Hasil output Insertion sorting :

Hasil output Selection Sorting :

Hasil output Bubble Sorting :