Ayo Membuat Program Pascal/Algoritma Sorting Dasar

Pada halaman ini, akan dipelajari mengenai konsep algoritme/logika dari pengurutan data (sorting) dengan kompleksitas O(n²), meliputi:

Bubble Sort
Selection Sort
Insertion Sort

Ada 2 tujuan berbeda dari suatu pengurutan data, yaitu:

Pengurutan data secara Menaik (Ascending), contohnya data diurutkan dari A sampai Z, atau dari 0 sampai 100
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, dipakai prosedur Tukar berikut ini:

procedure Tukar(var A, B: string);
var C: string;
begin
   C:= A;
   A:= B;
   B:= C;
end;

Bubble Sort

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;

program urutkan data ;

   uses crt;
   const
       N = 6 ;
       A : array [1..N] of integer = (25, 22, 28, 30, 15, 45, 60) ;

var

   j, k, x 
   integer ;

begin

   writeln ('data sebelum urut...')
   for j := 1 to N begin 
       writeln ('a[',j,'] = ',A[j]);
       and ;
       {proses urut }
       for j := N to n-1 do begin 
       for k := N downto J+1 do begin 
           if A [K] < A [k-1] then begin 
               temp     := A[k];
               A[k]     := A[k-1];
               A[k-1]   := temp;
           end;
       end;
   end;
   writeln ;
   writeln ( 'data seseudah di urutkan secara ascending ...');
   writeln ('______________________________________________')
   for j := 1 to N do 
   begin
       writeln ( 'A[',j,'] = ',A[j]);
   end;

end.

Insertion Sort

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;