Sorting Pada Turbo Pascal

Hay guys… Bertemu lagi dengan saya, dengan materi yang berebeda lagi tentunya, tetapi tidak
lepas dari turbo pascal, maklum lah, masih belum bisa move on sama turbo pascal… hehehe.
Kalau kemarin kita telah membahas mengenai fungsi dan rekursif, sekarang kita akan membahas
mengenai sorting. Apasih sorting dalam turbo pascal itu? Berikut penjelasan kami.
SORTING
Pada halaman ini, kita akan mempeljari mengenai konsep algoritme/logika dari pengurutan data
(sorting) dengan kompleksitas, yang meliputi:
1. Buble Sort (sederhana tapi lambat)
2. Quick Sort (cepat tetapi rumit)
3. Shell Sort (agak cepat dan tidak terlalu rumit)
4. Selection Sort
5. Insert Sort
6. Marge Sort

Ada 2 tujuan berbeda dari suatu pengurutan data, yaitu:

1. Pengurutan data secara Menaik (Ascending), contohnya data diurutkan dari A

sampai Z, atau dari 0 sampai 100.
2. Pengurutan data secara Menurun (Descending), contohnya data diurutkan dari
Z sampai A, atau dari 100 sampai 0
Dalam pembahasan di halaman ini, dipakai asumsi Pengurutan data secara Menaik dengan
data berupa string yang ada di dalam suatu array 1 dimensi. Sedangkan untuk melakukan
pertukaran data,

1. Buble Sort (sederhana tapi lambat)

Bubble Sort adalah metode pengurutan data dengan prinsip: data di lokasi/indeks I
dibandingkan dengan data lain di lokasi/indeks sebelahnya I+1, apabila terdapat ketidakcocokan
data, maka data di lokasi I tersebut akan ditukar dengan data di lokasi I+1. Maka secara perlahan,
data akan bergerak menuju ke lokasi yang tepat. Dari sifat inilah, istilah bubble yang
artinya gelembung diambil. Seperti gelembung dalam minuman soda, yang perlahan bergerak
naik ke atas.
Disajikan contoh cara kerjanya, untuk 5 buah data yaitu 4, 5, 1, 3, 2. Pengurutan dimulai dari
lokasi pertama (I adalah 1), dan dibandingkan dengan lokasi sebelahnya (I+1 adalah 2). Karena
data 4 dan 5 sudah berada pada urutan yang cocok, maka tidak terjadi pertukaran. Kemudian
dicek data lokasi berikutnya (I adalah 2) dengan lokasi sebelahnya (I+1 adalah 3), ternyata data 5
dan 1 tidak cocok, maka ditukar. Lokasi berikutnya (I adalah 3) dibandingkan dengan lokasi
sebelahnya (I+1 adalah 4), ternyata data 5 dan 3, tidak cocok lagi, maka ditukar lagi. Demikian
seterusnya, dikerjakan sampai dipastikan bahwa semua data ada pada lokasi yang cocok, yang
dilakukan dengan cara sudah tidak ada lagi pertukaran yang dilakukan. Berikut adalah
proses perubahan data untuk contoh data 4, 5, 1, 3, 2 tersebut:
Perulangan Pertama (First Pass)
4 5 1 3 2 (cocok)
4 5 1 3 2 (tukar 5 dan 1) 4 1 5 3 2
4 1 5 3 2 (tukar 5 dan 3) 4 1 3 5 2
4 1 3 5 2 (tukar 5 dan 2) 4 1 3 2 5

Perulangan Kedua (Second Pass)

4 1 3 2 5 (tukar 4 dan 1) 1 4 3 2 5
1 4 3 2 5 (tukar 4 dan 3) 1 3 4 2 5
1 3 4 2 5 (tukar 4 dan 2) 1 3 2 4 5
1 3 2 4 5 (cocok)

Perulangan Ketiga (Third Pass)

1 3 2 4 5 (cocok)
1 3 2 4 5 (tukar 3 dan 2) 1 2 3 4 5
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)

Perulangan Keempat (Fourth Pass)

1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)
1 2 3 4 5 (cocok)

Pada waktu Perulangan Keempat, sudah tidak terjadi pertukaran lagi (semua sudah cocok), maka
sudah dapat dipastikan bahwa semua data sudah berada di lokasi yang tepat.

Berikut adalah implementasi dari Algoritme Bubble Sort dengan memakai prosedur. Parameter
data berjenis referensi ke tipe data array of string:

procedure Bubble(var Arr: array of string);

var I: integer;
Ada_Tukar: boolean;
begin
repeat
Ada_Tukar:= false;
for I:= Low(Arr) to High(Arr)-1 do begin
if Arr[I] > Arr[I+1] then begin
Tukar(Arr[I], Arr[I+1]);
Ada_Tukar:= true;
end;
end;
until Ada_Tukar = false;
end;
2. Quick Sort (cepat tetapi rumit)
Quick Sort merupakan suatu algoritma pengurutan data yang menggunakan teknik
pemecahan data menjadi partisi-partisi, sehingga metode ini disebut juga dengan nama partition
exchange sort. Untuk memulai irterasi pengurutan, pertama-tama sebuah elemen dipilih dari
data, kemudian elemen-elemen data akan diurutkan diatur sedemikian rupa, sehingga nilai
variabel Sementara berada di suatu posisi ke I yang memenuhi kondisi sebagai berikut :
a) Semua elemen di posisi ke 1 sampai dengan ke I-1 adalah lebih kecil atau sama dengan
Sementara.
b) Semua elemen di posisi ke I+1 sampai dengan ke N adalah lebih besar atau sama dengan
Sementara.

Program rekursi untuk mengurutkan data dengan metode Quick Sort ini dapat berupa :

(* Program Quick Sort

Mengurutkan Data Dengan Metode Quick Sort secara rekursi Stefanus Eko Prasetyo, Junaini
Krisnawati, Deli, Lintang Agung, Hendry, Nico Arsanto*)

Type
TipeArray = string[20];
ArrayUrut = array[1..1000] of TipeArray;

Procedure QuickSort(var x : ArrayUrut;

Bawah, Atas : word);

var
I, J : word;
Sementara : TipeArray;
Begin
While Atas > bawah Do
begin
I := Bawah;
J := Atas;
Sementara := X[Bawah];

{Memecah Array menjadi 2 bagian}

While I < J Do Begin
While X[J] > Sementara Do J := J - 1;
X[I] := X[J];
While (I<J) And (X[I] <= Sementara) Do I := I + 1;
X[J] := x[I];
end;

X[I] := Sementara;
 {Urutkan rekursi}
QuickSort(X, Bawah, I-1);
Bawah := I + 1;
end;
end;

Var
Nama : ArrayUrut;
N, I : word;
Begin
Write('Jumlah data yang akan diurutkan ='); ReadLn(N);
Writeln;
Writeln('Masukkan data :');
For I:=1 to N Do Begin
Write('Data ke ',I,' = '); ReadLn(Nama[I]);
end;

{urutkan dengan prosedur QuickSort}

QuickSort(Nama,1,N);

{Tampilkan Data yang telah diurut}

WriteLn;

WriteLn('Data yang telah di urut :');

WriteLn('-------------------------');
For I := 1 To N Do
WriteLn(Nama[I]);

end.
Bila Program dijalan amka outputnya adalah :
3. Shell Sort (agak cepat dan tidak terlalu rumit)
Metode shell sort disebut juga dengan metode pertambahan menurun (diminishing
increment). Metode ini dikembangkan oleh Donald L. Shell pada tahun 1959, sehingga sering
disebut dengan Metode Shell Sort. Metode perbandingan dan pertukaran. Perbandingan dimulai
dari separuh array yang akan disortir dengan separuh bagian yang lain.
Algoritma utamanya adalah sebagai berikut:
Baca:=0;
For i:=1 to m-1 do
Begin
tempat:=I;
for j:= i+1 to m do
if a[tempat]>A[j] then
tempat:=j;
Ganti (A[i], A[tempat]);
INC(baca);
End;

4. Insert Sort
Insertion Sort adalah contoh lain dari metode pengurutan yang sederhana. Insertion Sort adalah
kebalikan dari buble sort yang mengurutkan data dari belakang, Insertion Sort mengurutkan data dari
depan. Ambil dua data pertama, urutkan sesuai yang diinginkan. Lalu sisipkan data ketiga ditempat
semestinya lalu sisipkan data keempat ditempat semestinya diantara 3 data sebelumnya dan begitu
seterusnya sampai semua data selesai diurutkan.
Data Asli Langkah 1 Langkah 2 Langkah 3 Langkah 4 Langkah 5 Data Urut
 D C C A A A A
C D A C C B B
A A D D B C C
B B B B D D D

5. Marge Sort
Urut gabung atau sering juga disebut dalam istilah Inggrisnya merge sort merupakan
algoritme pengurutan dalam ilmu komputer yang dirancang untuk memenuhi kebutuhan
pengurutan atas suatu rangkaian data yang tidak memungkinkan untuk ditampung dalam memori
komputer karena jumlahnya yang terlalu besar. Algoritme ini ditemukan oleh John von Neumann
pada tahun 1945.
Prinsip utama yang diimplementasikan pada algoritme urut gabung seringkali disebut sebagai
pecah-belah dan taklukkan (bahasa Inggris: divide and conquer). Cara kerja algoritme urut
gabung adalah membagi larik data yang diberikan menjadi dua bagian yang lebih kecil. Kedua
larik yang baru tersebut kemudian akan diurutkan secara terpisah. Setelah kedua buah list
tersusun, maka akan dibentuk larik baru sebagai hasil penggabungan dari dua buah larik
sebelumnya. Menurut keefektifannya, alogaritma ini bekerja dengan tingkat keefektifan
O(nlog(n)).

Contoh penerapan atas sebuah larik sebagai data sumber yang akan diurutkan {3, 9, 4, 1, 5, 2}
adalah sebagai berikut:
 Larik tersebut dibagi menjadi dua bagian, {3, 9, 4} dan {1, 5, 2}
 Kedua larik kemudian diurutkan secara terpisah sehingga menjadi {3, 4, 9} dan {1, 2, 5}
 Sebuah larik baru dibentuk yang sebagai penggabungan dari kedua larik tersebut {1}, sementara
nilai-nilai dalam masing larik {3, 4, 9} dan {2, 5} (nilai 1 dalam elemen larik ke dua telah
dipindahkan ke larik baru)
 langkah berikutnya adalah penggabungan dari masing-masing larik ke dalam larik baru yang
dibuat sebelumnya.
{1, 2} <-> {3, 4, 9} dan {5}
{1, 2, 3} <-> {4, 9} dan {5}
{1, 2, 3, 4} <-> {9} dan {5}
{1, 2, 3, 4, 5} <-> {9} dan {null}
{1, 2, 3, 4, 5, 9} <-> {null} dan {null}

6. Selection Sort
Cara kerja metode ini didasarkan pada pencarian elemen dengan nilai terkecil. kemudian
dilakukan penukaran dengan elemen ke-I. Secara singkat metode ini bisa dijelaskan sebagai
berikut. Pada langkah pertama, dicari data yang terkecil dari data pertama sampai terakhir.
Kemudian data tersebut kita tukar dari data pertama. Dengan demikian, data pertama sekarang
mempunyai nilai paling kecil dibanding dengan data lain. Pada langkah kedua, data terkecil kita
cari mulai dari data kedua sampai data terakhir. Data terkecil yang kita peroleh kita tukar dengan
data kedua. Demikian seterusnya sampai seluruh data terurut.
Contoh dari proses sorting dengan menggunakan metode Selection sort :

Contoh:
program sorting_nama;
uses crt;
type rec_data=record
nama:string;
end;

var data: array [1..50] of rec_data;

n,i,j:byte;
temp:string;

procedure input;
begin
clrscr;
writeln('Program mengurutkan Nama');
writeln;
write('Masukkan Jumlah Nama : ');readln(n);
for i :=1 to n do
begin
write('Nama ke-',i,' : ');readln(data[i].nama);
end;
end;

procedure bubble;
begin
for i:=n downto 2 do
begin
for j:=1 to i-1 do
if data[j].nama > data[j+1].nama then
begin
temp := data[j+1].nama;
data[j+1].nama:=data[j].nama;
data[j].nama :=temp;
end;
end;

for i :=1 to n do
begin
writeln('Nama ke-',i,' : ',data[i].nama);

end;
end;

BEGIN
clrscr;
input;
writeln;
writeln('Data Setelah Diurutkan');
bubble;
readln;
END.
Output: