Macam-Macam Algoritma Sorting dan Contoh Programnya dalam Pascal

Karena fokus kita disini adalah menuntun anda bagaimana memahami logika pemrograman dan algoritma maka disini saya akan sedikit mengulas mengenai algoritma sorting.

Jika anda merupakan mahasiswa teknik informatika maka algoritma sorting (pengurutan data) ini mungkin akan anda dapatkan saat anda berada di awal semester perkuliahan.

Beberapa metode sorting mengurutkan data yang dikenal antara lain adalah:

1. Bubble Sort (sederhana tetapi lambat)
2. Quick Sort (cepat tetapi rumit)
3. Shell Sort (agak cepat dan tidak terlalu rumit)
4. Selection Sort
5. Insert Sort
6. Merge Sort

Yang perlu anda ketahui adalah bagaimana cara kerja dari masing-masing algoritma.

Dan disini kita akan membandingkan beberapa algoritma tersebut untuk mengurutkan sebuah data. Namun anda harus ingat bahwa: tidak ada algoritma salah atau buruk.

Hanya saja, ada algoritma yang lebih baik dari yang lain.

Nah disini tugas anda sebagai programmer adalah menentukan algoritma terbaik untuk program anda dan menguji apakah sudah sesuai dengan kebutuhan anda.

#1 Bubble Sort

Yang pertama kita akan membahas bubble sort. Algoritma ini merupakan salah satu algoritma pengurutan yang paling sederhana, baik dalam hal pengertian maupun penerapannya.

Ide dari algoritma bubble sort adalah mengulang proses pembandingan antara tiap-tiap elemen array dan menukarnya apabila urutannya salah.

Teknik ini menyusun data yang diinginkan secara berurutan dengan membandingkan elemen data yang ada dan terus diulang hingga tidak perlu dilakukan penukaran lagi.

Berikut ini adalah gambaran dari algoritma bubble sort:

for i:=1 to Jumlah_data-1 do
  for j:=i+1 to Jumlah_data do
    if Data[i]>Data[j] then
    begin
      t:=Data[i];
      Data[i]:=Data[j];
      Data[j]:=t;
    end;

Kita misalkan memiliki 5 angka yang akan kita simpan kedalam variabel Data (Array).

Dengan masing-masing nilai sebagai berikut:

Data[1] := 3;
Data[2] := 1;
Data[3] := 4;
Data[4] := 2;
Data[5] := 6;

Cara Kerja:

1. Langkah pertama: Data[1] akan dibandingkan dengan Data[2]. Jika Data[1] lebih besar dari Data[2] maka nilai dari kedua variabel tersebut ditukar posisinya.
2. Data[1] akan terus dibandingkan dengan data-data selanjutnya (Data[3], Data[4], dan Data[5]). Hingga akhirnya Data[1] berisi nilai terkecil.
3. Setelah proses perbandingan Data[1] selesai, selanjutnya kita akan membandingkan Data[2] dengan Data[3], Data[4] dan Data[5] seperti proses sebelumnya.
4. Begitu seterusnya sampai semua data selesai di bandingkan.

Berikut adalah conto program pascal dengan agoritma buble sort:

Program Bubble_Urutan;
  uses crt;
  var Data:array[1 .. 5] of integer;
  i,j,t,Jumlah_data:integer;
Begin
  Data[1] := 3;
  Data[2] := 1;
  Data[3] := 4;
  Data[4] := 2;
  Data[5] := 6;
  Jumlah_data := 5;

  writeln('Data Awal:');
  for i:=1 to Jumlah_data do
  begin
    writeln('Data[',i,'] = ',Data[i]);
  end;

  for i:=1 to Jumlah_data-1 do
    for j:=i+1 to Jumlah_data do
      if Data[i]>Data[j] then
      begin
        t:=Data[i];
        Data[i]:=Data[j];
        Data[j]:=t;
      end;

  writeln('Hasil:');
  for i:=1 to Jumlah_data do
  begin
    writeln('Data[',i,'] = ',Data[i]);
  end;

End.

#2 Quick Short

Algoritma quick short ditemukan oleh E. Hoare. Algoritma ini menggunakan metode rekursi sampai habis. Prinsipnya membagi data menjadi dua bagian yang sama (kiri dan kanan).

Dimana data tengah menjadi pivot (pusat operasi). Kemudian kita akan mengumpukan data dengan nilai lebih kecil dari pivot disebelah kiri pivot, dan di kanan untuk yang lebih besar.

Karena dimungkinkan bagian kiri dan kanan pivot tidak sama besarnya. maka dari itu tiap bagian di bagi menjadi dua lagi sehingga mempunyai pivot yang baru.

baca:=0;
pusat := A[(awal+akhir) div 2];
kiri := awal;
kanan := akhir;
While kiri <= kanan Do
  Begin
  While A[kiri] < pusat Do
  Inc(kiri);
  While A[kanan] > pusat Do
    Dec(kanan);
    If kiri<=kanan Then
      Begin
      Ganti(A[kiri],A[kanan]);
      Inc(kiri);
      Dec(kanan);
      Inc(baca);
      End;
  End;

If kanan>awal Then
  Urut(awal,kanan);
  If akhir>kiri Then
    Urut(kiri,akhir);

Algoritma Quick Sort juga disebut juga dengan partition Exchange sort karena konsepnya membuat partisi-partisi, dan sort dilakukan per partisi.

……………………………….

#3 Shell Sort

Prinsipnya hampir sama dengan Bubble Sort tetapi dioptmisisasi sehingga lebih cepat.

Ditemukan oleh Donald Shell. prinsipnya adalah membandingkan data dengan jarak tertentu dalam array. Algoritma utamanya adalah sebagai berikut :

baca:=0;
For i:= (m Div 2) Downto 1 Do
For j:= 1 To m-i Do
  If A[j]>A[j+i] Then
  Begin
    Ganti(A[j],A[j+i]);
    Inc(baca);
  End;

#4 Selection Sort

………………

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;

#5 Insert Sort

…………………………

Algoritma utamanya adalah sebagai berikut :

baca:=0;
For i:= 2 To m Do
Begin
  G:=A[i];
  j:=i-1;
  A[0]:=G;
    While G<A[j] Do
    Begin
      A[j+1]:=A[j];
      Dec(j);
      Inc(baca);
    End;
    A[j+1]:=G;
End;

#6 Merge Sort

Algoritma utamanya

Begin
i:=awal;
k:=awal;
j:=tengah+1;
Repeat
  If A[i]<A[j] Then
    Begin
      B[k]:=A[i];
      Inc(i);
      End
      Else
      Begin
      B[k]:=A[j];
      Inc(j);
    End;
  Inc(k);
  Inc(baca);
Until (i>tengah) Or (j>akhir);

If i>tengah Then
  For t:= j To akhir Do
  Begin
    B[k+t-j]:=A[t];
  End
Else
  For t:= i To tengah Do
  Begin
    B[k+t-i]:=A[t];
  End;
End;