SORT

Definisi Sort

Sort adalah proses pengurutan data yang sebelumnya disusun secara acak sehingga menjadi tersusun secara teratur menurut suatu aturan tertentu.

Pada umumnya terdapat 2 jenis pengurutan :

v Ascending (Naik)

v Descending (Turun)

Contoh :

Data Acak : 5 6 8 1 3 25 10

Terurut Ascending : 1 3 5 6 8 10 25

Terurut Descending : 25 10 8 6 5 3 1

Untuk melakukan proses pengurutan tersebut dapat digunakan berbagai macam cara / metoda. Beberapa metoda diantaranya :

a) Buble / Exchange Sort

b) Selection Sort

c) Insertion Sort

d) Quick Sort

Procedure Bubble Sort Ascending

Procedure Asc_Bubble(var data:array; jmldata:integer);

Var i,j : integer;

Begin

For i:= 2 to jmldata do

For j:= jmldata downto I do

If data[j] <>

Tukardata (data[j], data[j-1]);

end;

Untuk pengurutan secara descending anda hanya perlu menggantikan baris ke-6 dengan berikut ini :

If data[j] > data[j-1] then

Selection Sort

Membandingkan elemen yang sekarang dengan elemen yang berikutnya sampai dengan elemen yang terakhir. Jika ditemukan elemen lain yang lebih kecil dari elemen sekarang maka dicatat posisinya dan kemudian ditukar. Dan begitu seterusnya.

Procedure Asc_Selection;

Var min, pos : byte;

Begin

For i:= 1 to max-1 do

Begin

Pos:=i;

For j:= i+1 to max do

If data[j] <>then pos:=j;

If i <> pos then tukardata(data[i],data[pos]);

end;

end;

Insertion Sort

Pengurutan dilakukan dengan cara membandingkan data ke-I (dimana I dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. Jika ditemukan data yang lebih kecil maka data tersebut disisipkan ke depan sesuai posisi yang seharusnya.

QUICK SORT

Membandingkan suatu elemen (disebut pivot) dengan elemen yang lain dan menyusunnya sedemikian rupa sehingga elemen- elemen lain yang lebih kecil daripada pivot tersebut terletak di sebelah kirinya dan elemen-elemen lain yang lebih besar daripada pivot tersebut terletak di sebelah kanannya. Sehingga dengan demikian telah terbntuk dua sublist, yang terletak di sebelah kiri dan kanan dari pivot. Lalu pada sublist kiri dan sublist kanan kita anggap sebuah list baru dan kita kerjakan proses yang sama seperti sebelumnya. Demikian seterusnya sampai tidak terdapat sublist lagi. Sehingga didalamnya telah terjadi proses Rekursif.

Proses :

Bilangan yang di dalam kurung merupakan pivot

Persegi panjang yang digambarkan dengan garis terputus-putus menunjukkan sublist.

i bergerak dari sudut kiri ke kanan sampai mendapatkan nilai yang >= pivot.

j bergerak dari sudut kanan ke kiri sampai menemukan nilai yang <>

Struktur Bahasa PASCAL secara umum

Pascal mempunyai struktur sebagai berikut:
1. Bagian Judul Program
2. Bagian Deklarasi
a. Deklarasi tipe data (TYPE)
b. Deklarasi variabel (VAR)
c. Deklarasi konstanta (CONST)
d. Deklarasi label (LABEL)
e. Deklarasi sub-program (PROCEDURE dan FUNCTION)
3. Bagian Program Utama Perintah-perintah.

Teks Pascal setidaknya memiliki bagian Judul Program, bagian Deklarasi, dan Bagian Program Utama yang berupa perintah-perintah. Sedangkan untuk bagian deklarasi menyesuaikan dengan isi dari program itu sendiri. Contoh program PASCAL:

program TAMBAH_00; { Menjumlahkan dua bilangan yang nilainya diberikan dalam perintah}
var X, Y, Z: integer; { Deklarasi variabel X,Y dan Z sebagai bilangan bulat }
BEGIN { Program Utama Mulai }
X := 50; { Perintah memberikan nilai 50 pada var. X }
Y := 25; { Perintah memberikan nilai 25 pada var. Y }
Z := X + Y; { Perintah menjumlahkan X dan Y serta menyimpan hasilnya ke Z}
END. { Akhir Program Utama }

Pada contoh ini nilai X dan Y tidak bisa sembarang, karena didefiniskan tertentu. Agar nilai X dan Y bisa bebas ditentukan, nilai X dan Y dibaca dari default input.

program TAMBAH_01; { Menjumlahlan dua buah bilangan yang dibaca dari default input }
var X, Y, Z: integer; { Deklarasi variabel X,Y dan Z sebagai bilangan bulat }
BEGIN { Program Utama Mulai }
read(X); { Membaca nilai X lewat key-board }
read(Y); { Membaca nilai Y lewat key-board }
Z := X + Y; { Menjumlahkan X dan Y serta menyimpan hasilnya ke Z }
write(Z); { Menyajikan Z ke layar monitor }
END. { Akhir Program Utama }

Dasar Bahasa PASCAL

Unsur-unsur Pemrograman
a. Mendapatkan data dengan membaca data dari default input (key board, file atau sumber data lainnya).
b. Menyimpan data ke dalam memori dengan struktur data yang sesuai,
c. Memproses data dengan instruksi yang tepat.
d. Menyajikan atau mengirimkan hasil olahan data ke default output (monitor, file atau tujuan lainnya).

Jenis identifier

a. Identifier umum

Merupakan identifier yang didefinisikan sendiri oleh pemrogram. Pemrogram mempunyai kebebasan untuk menentukan nama identifiernya, dengan syarat nama tersebut tidak sama dengan identifier standar dan reserved word yang akan dibahas lebih lanjut. Hal ini untuk mencegah kesalahan yang bisa timbul akibat tumpang tindih identifier dalam program.

b. Identifier Standar (Baku)

Merupakan identifier yang didefinisikan oleh pembuat kompiler Pascal. Biasanya pembuat kompiler menyediakan suatu library yang sudah ada didalam kompiler. Library berisi berbagai procedure, fungsi atau unit yang sudah siap pakai. Misalnya Turbo Pascal Windows 1.5 memiliki suatu unit untuk memproses output yaitu wincrt, gotoxy, yang dengan mudah bisa dipakai oleh programmer di dalam menuliskan kode-kode programnya. Dinamai Identifier Standar karena suatu kompiler tidak harus memilikinya, masing-masing kompiler dimungkinkan mempunyai identifier yang berbeda untuk suatu tugas yang hampir sama. Misalnya Turbo Pascal versi DOS menggunakan crt untuk melakukan fungsi yang sama dengan wincrt (TPW 1.5). Beberapa Identifier Standar yang dimiliki oleh kompiler-kompiler Pascal antara lain:

abs arctan boolean char cos dispose eof eoln exp false input integer ln maxint new odd ord output pack page pred read readln real reset rewrite round sin sqr sqrt succ text true trunc write writeln

c. Identifier "reserved word", yaitu yang sudah didefinisikan dan digunakan oleh bahasa PASCAL sendiri (Kita tidak bisa menamai identifier kita dengan ini).

and array begin case const div do downto else end file for forward function goto if in label mod nil not of or packed procedure program record repeat set then to type until var while with

Deklarasi Variable:
Mendeklarasikan varibel adalah:
a. Memberikan nama variabel sebagai identitas pengenal
b. Menentukan tipe data variabel
Contoh deklarasi variabel:

var K : integer;
R : real;
C : char;
T : boolean;

Beberapa identifier yang sejenis bisa dideklarasikan bersamaan.

var i, j, k : integer;{Variabel i, j dan k sebagai integer}
namaMHS, alamatMHS : char; {Nama dan alamat mahasiswa }

Deklarasi Konstanta:
Mendeklarasikan konstanta adalah:
a. Memberikan nama konstanta sebagai identitas pengenal
b. Menentukan nilai konstanta
Contoh deklarasi konstanta:

const MaximumSize = 100; {integer }
ExitCommand = 'Q'; {char }

Tipe Data

Tipe data yang disediakan oleh PASCAL meliputi:
1. Tipe Data Sederhana

merupakan tipe data dasar yang sering dipakai oleh program, meliputi: integer (bilangan bulat), real (bilangan pecahan), char (alphanumerik dan tanda baca), dan boolean (logika). Untuk data integer dan real masing-masing terbagi menjadi beberapa kategori

a. Bilangan Integer
merupakan tipe data berupa bilangan bulat, terbagi atas beberapa kategori seperti terlihat dalam tabel 1. tabel 1 menunjukkan jenis data, ukuran dalam memori dan rentang nilainya.

RECORD (REKAMAN)

Sebuah record rekaman disusun oleh beberapa field. Tiap field berisi data dari tipe dasar / bentukan tertentu.

Cara pendeklarasian dari record adalah sbb:
• Mendefinisikan tipe dari record (jumlah field, jenis tipe data yang dipakai),
• Mendefinisikan variabel untuk dilakukan operasi.

SYNTAX

type

nama_record = record
identifier_1 : tipe_data_1;
:
:
identifier_n : tipe_data_n;
end;
var variabel : nama_record;

Contoh.

type

Data_mahasiswa = record
Nama : string;
Usia : integer;
Kota : String;
Kodepos : integer;
end;
Var
x: Data_mahasiswa;

1. Pengaksesan Elemen Record
Nama variable disertai nama field.

x.Nama
x.Usia
x.Kota
x.Kodepos

Contoh.

program RECORD_INTRO;
type tanggal = record
bulan, hari, tahun : integer;
end;
var waktu : tanggal;
begin
waktu.hari :=25;
waktu.bulan:=09;
waktu.tahun:= 1983;
writeln('hari ini adalah ',waktu.hari,':',waktu.bulan,':', waktu.tahun)
end.

2. Pengunaan With … do
Pernyataan with untuk lebih menyederhanakan pengaksesan field-field pada record. Pemrograman dapat mengakses field cukup dengan menyebutkan nama field-nya saja. Misalkan pernyataan :

x.Nama
x.Usia
x.Kota
x.Kodepos

menjadi

with x do
Begin
Nama
Usia
Kota
Kodepos
end

Contoh.

program RECORD_INTRO;
type tanggal = record
bulan, hari, tahun : integer;
end;
var waktu : tanggal;
begin {program utama}
with waktu do {mulai with}
begin
hari :=25;
bulan:=09;
tahun:=1983;
writeln('hari ini adalah ',hari,':',bulan,':', tahun)
end {akhir with}
end.

3. Array dari Record
Suatu array dapat juga berisi record contoh suatu deklarasi record tanggal.

type tanggal = record
bulan, hari, tahun : integer;
end;
var waktu : tanggal;

kemudian kita membentuk suatu array dari record ini, namakan birthdays.

var birthdays : array[1..10] of tanggal;

pernyataan ini akan membentuk suatu array dengan 10 elemen. Dimana tiap elemen adalah sebuah record tanggal, yaitu, terdiri atas bulan, hari, tahun dengan tipe data Integer.
Digambarkan seperti berikut:

Contoh Pemberian nilai awal dari masing-masing elemen birthdays:

Birthdays[1].hari :=25;
Birthdays[1].bulan:=09;
Birthdays[1].tahun:=1983;

4. Record di dalam Record
Record bisa berisi record lain sebagai field. Seperti contoh record tanggal dan jam dikombinasikan menjadi sebuah record saat ini,

type tanggal = record
bulan, hari, tahun : integer;
end;
type waktu =record
jam, menit, detik : integer;
end;
type waktu_ini =record
tanggal_ini : tanggal;
waktu_ini : waktu
end;

Kemudian kita perlu membuat variabel kerja

var saat_ini : waktu_ini;

pemberian nilai akan terjadi seperti di bawah ini:

saat_ini.tanggal.bulan:= 11;
saat_ini.tanggal.hari:= 2;
saat_ini.tanggal.tahun:= 1985;
saat_ini.waktu.jam:= 3;
saat_ini.waktu.menit:= 3;
saat_ini.waktu.detik:= 33;

STACK ( Tumpukan )

-à Adalah tumpulan data yang seolah-olah ada data di atas data lain.

-à Suatu metode untuk Input dan hapus di dalam memori komputer.

Konsep utama dalam STACK adalah LIFO ( Last In First Out ).

Algoritma:

1. Input/tambah data
• Jika ada input maka no stack/no tumpukan yang semula 0 akan tambah 1 demi 1 sampai maksimal tumpukan.

2. Pengambilan data

· Jika ada pengambilan data maka data dipindahkan di variabel lain contohnya temp. Dan posisi tumpukannya yang semula maksimal akan berkurang 1 demi 1 sampai posisi 0 kembali.

1. Deklarasi STACK

Type

Const

Max = 5;

Nama record = Record

Data : type data;

Top : byte;

End;

Nama_array = ARRAY [1..max] of Nama record;

Var

STACK : nama Array;

1. Operasi pada STACK

· CREATE

Membuat stack baru yang masih kosong.

Procedure create;

Begin

Stack.top:=0;

End;

· FULL

Untuk memeriksa apakah stack sudah penuh atau belum.

Fuction full:bolean;

Begin

Stack.top:=max;

End;

· PUSH

Menambah sebuah elemen ( data ) kedalam stack

Syarat: tidak bisa dilakukan jika stack sudah penuh.

Procedure push ( input:string );

Begin

If not full then

Begin

Stack.top:=stack.top;

Stack.data:=input;

End;

End;

· EMPTY

Fuction empty: bolean;

Begin

Empty:=false;

If top:=0 then empty:=true;

End;

· POP

Mengambil elemen teratas dari stack.

Syarat: Stack tidak boleh kosong.

Procedure Pop ( elemen:string );

Begin

If not empty then

Begin

Elemen:=stack.data;

Stack.top:=top – 1;

End;

End;

QUEUE ( ANTRIAN )

-à Kumpulan data dimana data masuk dan keluar pada ujung yang berbeda.

-à Konsep utama FIFO ( Fisrt In First Out ).

Algoritma:

1. Input/tambah data
• Jika ada input maka no antrian yang semula 0 akan tambah 1 demi 1 sampai maksimal antrian.
2. Hapus/Pengambilan data

· Jika ada pengambilan data maka data dipindahkan di variabel lain contohnya temp, antrian ke-dua akan maju ke antrian pertama dan seterusnya. Dan jumlah antrian yang semula maksimal akan berkurang 1 demi 1 sampai antrian 0 kembali.

1. Deklarasi Queue

Type

Const

Max = 5;

Nama record = Record

Data : type data;

Top : byte;

End;

Nama_array = ARRAY [1..max] of Nama record;

Var

Antri : nama Array;

4. Operasi pada queue

· CREATE

Membuat antrian baru yang masih kosong.

Procedure create;

Begin

antri.top:=0;

End;

· FULL

Untuk memeriksa apakah antrian sudah penih..

Fuction full:bolean;

Begin

antri.top:=max;

End;

· PUSH

Menambah sebuah elemen ( data ) kedalam antrian.

Syarat: tidak bisa dilakukan jika antrian sudah penuh.

Procedure push ( input:string );

Begin

If not full then

Begin

antri.top:=antri.top;

antri.data:=input;

End;

End;

· EMPTY

Fuction empty: bolean;

Begin

Empty:=false;

If top:=0 then empty:=true;

End;

· POP

Mengambil 1 elemen dari sebuah antrian.

Syarat: antrian tidak boleh kosong.

Procedure Pop ( elemen:string );

Begin

If not empty then

Begin

Elemen:=antri.data;

antri.top:=top – 1;

End;

End;

POINTER

Variabel Pointer

Pada materi sebelumnya telah dijelaskan mengenai variabel bertipe array, suatu tipe data yang bersifat statis (ukuran dan urutannya sudah pasti). Selain itu ruang memori yang dipakai olehnya tidak dapat dihapus bila variabel bertipe array tersebut sudah tidak digunakan lagi pada saat program dijalankan. Untuk memecahkan masalah diatas, kita dapat menggunakan variabel pointer. Tipe data pointer bersifat dinamis, variabel akan dialokasikan hanya pada saat dibutuhkan dan sesudah tidak dibutuhkan dapat dialokasikan kembali.

Pendeklarasian variabel pointer tidak jauh berbeda dengan pendeklarasian variabel biasa, hanya perlu ditambahan simbol topi (^) sebelum tipe datanya. Simbol topi tersebut menandahkan bahwa variabel tersebut menunjuk ke lokasi tertentu pada memori.

Single Linked List

Apabila setiap kali anda ingin menambahkan data selalu dengan menggunakan variabel pointer yang baru, anda akan membutuhkan banyak sekali variabel pointer(penunjuk).