Sorting

Sorting. Sama seperti arti kata tersebut, dalam post ini akan dibahas mengenai pengurutan.
Pengurutan dilakukan untuk menjadikan suatu deretan/kumpulan elemen menjadi terurut berdasarkan suatu kriteria tertentu (menaik, menurun, dsb.)

Ada banyak algoritma untuk pengurutan, di antaranya akan dibahas di sini.


Bubble Sort
Bayangkan sebuah wadah yang terisi cairan dengan massa jenis yang berbeda-beda. Secara otomatis cairan dengan massa jenis terkecil akan naik menempati posisi paling atas, dan yang bermassajenis terbesar, vice versa. Sebelum mencapai titik setara itu, cairan bermassajenis kecil akan naik menuju ke arah permukaan, sampai cairan di atasnya memiliki massa jenis > dan yang di bawah <

Animasi untuk memperjelas (taken from wikipedia):

Source code:

//sorting technique : Bubble Sort

var
  arr : array [1..20] of integer = (1,6,2,8,30,3,7,3,4,8,12,19,53,63,85,13,63,85,3,100); //early initialization
  i   : integer;  // iterator

procedure swap(var a,b:integer);  // sudah dijelaskan pada post sebelumnya

procedure bubble_sort(l,r :integer; var arr :array [1..20] of integer); 
var
  i,j : integer;  // var. lokal untuk iterasi
begin
  for i:=1 to (r-l) do        // mengapa dari 1 sampai (r-l)? Apa itu (r-l)?
    for j:=l+1 to r do
      if (arr[j-1]>arr[j]) then        // ascending, menaik
        swap(arr[j-1],arr[j]);
end;

begin
  writeln('Array awal:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;

  bubble_sort(1,5,arr);   // sort array arr[] dari indeks 1 - n
  writeln('Setelah elemen ke 1 sampai 5 tersort:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;

  bubble_sort(1,20,arr);
  writeln('Setelah elemen ke 1 sampai 20 tersort:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;
end.

Output:

Array awal:
1 6 2 8 30 3 7 3 4 8 12 19 53 63 85 13 63 85 3 100
Setelah elemen ke 1 sampai 5 tersort:
1 2 6 8 30 3 7 3 4 8 12 19 53 63 85 13 63 85 3 100
Setelah elemen ke 1 sampai 20 tersort:
1 2 3 3 3 4 6 7 8 8 12 13 19 30 53 63 63 85 85 100

Potongan kode yang diberikan di atas berjalan dalam kompleksitas O(n^2), artinya untuk mengurutkan n buah elemen, terjadi n^2 proses. Sebenarnya masih ada beberapa pengamatan dan optimisasi untuk kode bubble sort di atas agar dapat berjalan dengan best case O(n).

Selection Sort
Selection sort adalah cara lain pengurutan dengan pemikiran kurang lebih seperti ini: Mencari nilai elemen yang tepat untuk posisi ke-i agar pada akhirnya seluruh elemen terurut. Itu sebabnya algoritma yang satu ini disebut selection sort.
Dalam algoritma ini kita mencari suatu nilai (terkecil maupun terbesar, sesuai kriteria) untuk ditempatkan pada posisi ke-i. Algo ini melakukan sebanyak worstcase n-1 kali pemilihan dalam suatu range data untuk mencari nilai yang tepat, untuk satu posisi. Jadi untuk semua posisi dilakukan n*(n-1) kali.


Animasi untuk memperjelas (taken from wikipedia):

Source code:

//sorting technique : Selection Sort

var
  arr : array [1..20] of integer = (1,6,2,8,30,3,7,3,4,8,12,19,53,63,85,13,63,85,3,100); //early initialization
  i   : integer;  // iterator

procedure swap(var a,b:integer); 

procedure selc_sort(l,r :integer; var arr :array [1..20] of integer);
var
  i,j : integer;     // var. lokal untuk iterasi
  val,idx : integer;
begin
  for i:=l to r-1 do
  begin
    val:=999999;        // untuk ascending, simpan nilai 'infinity' ke dalam val
    for j:=i to r do
      if (arr[j]<val) then
      begin
        val:=arr[j];
        idx:=j;
      end;
    swap(arr[i],arr[idx]);      // sudah ketemu nilai yang cocok, tukar
  end;
end;

begin
  writeln('Array awal:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;

  selc_sort(1,5,arr);   // sort array arr[] dari indeks 1 - n
  writeln('Setelah elemen ke 1 sampai 5 tersort:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;

  selc_sort(1,20,arr);
  writeln('Setelah elemen ke 1 sampai 20 tersort:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;
end.

Coba jalankan program di atas.
Algoritma sorting ini memiliki worst case complexity O(n^2), dan best case complexity O(n^2) juga.


Quick Sort
Quick sort adalah cara pengurutan dengan cara membagi-bagi elemen-elemen yang sudah ada menjadi partisi-partisi berdasarkan pivot yang dipakai, dan kemudian melakukan hal yang sama dalam partisi-partisi baru tersebut. Lalu apa bedanya jika di partisi? Tidak hanya partisi yang terjadi.
Biasanya, suatu range elemen yang ingin disort dibagi menjadi dua partisi dengan syarat (ini kalau ascending) partisi pertama memiliki nilai-nilai yang < dari elemen pivot, dan partisi kedua memiliki nilai-nilai yang > dari elemen pivot.
Animasi dan gambar untuk memperjelas (taken from wikipedia):

Source code:

//sorting technique : Quick Sort

var
  arr : array [1..20] of integer = (1,6,2,8,30,3,7,3,4,8,12,19,53,63,85,13,63,85,3,100); //early initialization
  i   : integer;  // iterator

procedure swap(var a,b:integer); 

procedure qsort(l,r :integer; var arr :array [1..20] of integer);
var
  newl,newr,pivot : integer;
begin
  if (l<r) then
  begin
    newl:=l; newr:=r; pivot:=arr[(l+r) div 2];
    while (newl<=newr) do
    begin
      while (arr[newl]<pivot) do inc(newl);
      while (arr[newr]>pivot) do dec(newr);
      if (newl<=newr) then
        swap(arr[newl],arr[newr]);
    end;
    qsort(l,newr);
    qsort(newl,r);
  end;
end;

begin
  writeln('Array awal:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;

  qsort(1,5,arr);   // sort array arr[] dari indeks 1 - n
  writeln('Setelah elemen ke 1 sampai 5 tersort:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;

  qsort(1,20,arr);
  writeln('Setelah elemen ke 1 sampai 20 tersort:');
  for i:=1 to 20 do write(arr[i],' ');
  writeln;
end.

Coba jalankan program di atas.
Quick sort berjalan dengan average case complexity O(n lg n), dimana lg adalah operasi logaritma basis 2. Namun ada suatu susunan elemen yang menyebabkan quicksort berjalan dalam O(n^2). Jadi meskipun quicksort itu 'quick', namun tidak selalu 'quick'.