Pendahuluan

Pengurutan / sorting adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu.

Banyak algoritma pengurutan:

1. Bubble Sort
2. Selection Sort (Maksimum/Minimum Sort)
3. Insertion Sort
4. Heap Sort
5. Shell Sort
6. Quick Sort
7. Merge Sort
8. Radix Sort
9. Tree Sort

Klarsifikasi algoritma pengurutan:

1. Algortima pengurutan internal = algoritma pengurutan untuk data yang disimpan dalam memori komputer. Seperti pengurutan Larik.
2. Algoritma pengurutan eksternal / pengurutan arsip/file = algoritma pengurutan untuk data yang disimpan di dalam disk storage.

Algoritma Pengurutan Apung / Bubble Sort

Terinspirasi oleh gelembung sabun yang berada diatas permukaan air.

Jika L[k] < L[k-1] maka

tukarkan  L[k] dengan L[k-1]

Contoh bilangan belum terurut:

procedure BubbleSort(var L: LarikEmerer; n:integer);

Deklarasi:

i,k,temp : integer;

Algoritma:

for i ß 1 to n-1 do

   for k ß n downto i+1 do

   if L[k] < L[k-1] then

      begin

      temp  ß  L[k];

      L[k]  ß  L[k-1];

      L[k-1]  ß  temp;

      end;

Algoritma Pengurutan Seleksi / Selection Sort

Dengan cara memilih elemen maksimum/minimum dari larik, lalu menempatkan elemen maksimum/minimum itu pada akhir/awal larik (elemen terujung).

Contoh bilangan yang akan diurutkan:

procedure MaksSelectionSort(var L: LarikEmerer; n:integer);

var i,j,imaks,temp: integer;

begin

for i:=n downto 2 do

   begin

   imaks := 1;

   for j:= 2 to i do

         if L[j] > L[imaks] then

         imaks := j;

         temp := L[imaks];

     L[imaks] := L[i];

     L[i] := temp;

   end;  end;

procedure MinSelectionSort(var L: LarikEmerer; n:integer);

var i,j,imin,temp: integer;

begin

for i:=1 to n-1 do

   begin

   imin := i;

   for j:= i+1 to n do

        if L[j] < L[imin] then

        imin := j;

        temp := L[imin];

   L[imin] := L[i];

   L[i] := temp;

   end;

end;

Algoritma Pengurutan Sisip / Insertion Sort

Adalah metode pengurutan dengan cara menyisipkan elemen larik pada posisi yang tepat. Pencarian posisi yang tepat dilakukan dengan cara menyisir larik.

procedure InsertSort(var L: LarikEmerer; n:integer);

var i,j,y: integer;

    ketemu: boolean;

begin

for i:=2 to n do

   begin

   y := L[i];

   j := i-1;

   ketemu := false;

   while (j>=1) and (not ketemu) do

      begin

      if y < L[j] then

         begin

         L[j+1] := L[j];

         j := j-1 ;

         end

         else

            ketemu := true;

           end;

           L[j+1] := y ;

   end;

end;

Algoritma Pengurutan Shell

Ditemukan oleh Donald Shell tahun 1959. Yang merupakan perbaikan dari pengurutan sisip yang pergeseran elemennya terlalu jauh/banyak.

Dengan cara mengurutkan larik setiap k elemen dengan metode pengirutan sisip.

Tidak seorangpun pernah dapat menganalisis algoritma pengurutan Shell secara tepat, karena pemilihan ukuran step didasarkan pada pertimbangan sugesti.

procedure ShellSort(var L: LarikEmerer; n:integer) ;

var step,start: integer;

begin

step := n ;

while step>1 do

   begin

   step := step div 3 + 1;

   for start := 1 to step do

      InsSort(L, N, start, step);

   end;  end;

procedure InsSort(var L:LarikEmerer ; n, start, step:integer);

var i,j,y: integer;

    ketemu: boolean;

begin

i := start + step;

while i<= n do

   begin

   y := L[i];

   j := i-step;

   ketemu:=false;

   while (j>=1) and (not ketemu) do

      begin

      if y < L[j] then

         begin

         L[j+step] := L[j];

         j := j-step ;

         end

         else

         ketemu := true;

      end;

      L[j+step] := y ;

     i := i+step;

end;

end;

Daftar Pustaka:

Munir, Rinaldi. 2007.  Algoritma dan pemrograman dalam Bahasa Pascal dan C, Penerbit informatika. Bandung.