Algoritma Sorting

Sorting  adalah  proses  menyusun  elemen  –  elemen  dengan  tata  urut  tertentu  dan

proses tersebut  terimplementasi dalam  bermacam aplikasi. Kita ambil  contoh pada

aplikasi perbankan. Aplikasi tersebut mampu menampilkan daftar account yang aktif.

Hampir   seluruh   pengguna   pada   sistem   akan   memilih   tampilan   daftar   berurutan

secara ascending demi kenyamanan dalam penelusuran data.

Beberapa   macam   algoritma  sorting  telah   dibuat   karena  proses   tersebut   sangat

mendasar  dan  sering   digunakan.   Oleh   karena   itu,   pemahaman   atas  algoritma   –

algoritma yang ada sangatlah berguna.

Setelah menyelesaikan pembahasan pada bagian ini, anda diharapkan mampu :

1. Memahami   dan   menjelaskan   algoritma   dari  insertion   sort,   selection   sort, merge sort

    dan quick sort.

2. Membuat implementasi pribadi menggunakan algoritma yang ada

Insertion Sort

Salah satu  algoritma  sorting  yang paling  sederhana adalah  insertion  sort.  Ide   dari

algoritma ini  dapat  dianalogikan seperti  mengurutkan  kartu.  Penjelasan berikut  ini

menerangkan bagaimana algoritma  insertion sort  bekerja dalam  pengurutan  kartu.

Anggaplah  anda  ingin  mengurutkan  satu  set   kartu  dari  kartu  yang  bernilai  paling

kecil hingga yang paling besar. Seluruh kartu diletakkan pada meja, sebutlah meja

ini sebagai meja pertama, disusun dari kiri ke kanan dan atas ke bawah. Kemudian

kita mempunyai  meja  yang  lain,   meja kedua,  dimana  kartu  yang  diurutkan  akan

diletakkan.  Ambil  kartu  pertama yang terletak  pada pojok   kiri   atas meja  pertama

dan letakkan pada meja kedua. Ambil kartu  kedua dari  meja pertama, bandingkan

dengan kartu yang berada pada meja kedua, kemudian letakkan pada  urutan yang

sesuai setelah perbandingan. Proses tersebut akan berlangsung hingga seluruh kartu

pada meja pertama telah diletakkan berurutan pada meja kedua.

Algoritma insertion sort  pada dasarnya memilah data yang akan diurutkan  menjadi

dua bagian, yang belum diurutkan (meja pertama) dan yang sudah diurutkan (meja

kedua).   Elemen   pertama   diambil   dari   bagian   array   yang   belum   diurutkan   dan

kemudian   diletakkan   sesuai   posisinya   pada   bagian   lain   dari   array   yang   telah

diurutkan. Langkah ini  dilakukan secara berulang hingga tidak ada lagi elemen yang

tersisa pada bagian array yang belum diurutkan.

Selection Sort

Jika anda diminta untuk membuat  algoritma sorting  tersendiri, anda mungkin  akan

menemukan sebuah algoritma yang mirip dengan selection sort. Layaknya insertion

sort, algoritma ini sangat rapat dan mudah untuk diimplementasikan.

Mari kita kembali menelusuri bagaimana algoritma ini berfungsi terhadap satu paket

kartu.   Asumsikan   bahwa   kartu   tersebut   akan   diurutkan   secara  ascending.   Pada

awalnya,  kartu tersebut   akan  disusun secara  linier  pada  sebuah meja  dari  kiri  ke

kanan,   dan   dari   atas   ke   bawah.   Pilih   nilai   kartu   yang   paling   rendah,   kemudian

tukarkan posisi  kartu ini dengan kartu yang terletak pada pojok kiri atas meja. Lalu

cari  kartu  dengan  nilai  paling  rendah  diantara  sisa kartu  yang  tersedia.  Tukarkan

kartu   yang  baru   saja  terpilih   dengan   kartu   pada  posisi   kedua.   Ulangi  langkah  –

langkah   tersebut   hingga   posisi   kedua  sebelum   posisi   terakhir   dibandingkan   dan

dapat digeser dengan kartu yang bernilai lebih rendah.

Ide utama dari  algoritma  selection  sort  adalah memilih elemen dengan nilai paling

rendah dan  menukar elemen yang  terpilih  dengan elemen  ke-i.  Nilai dari  i  dimulai

dari 1 ke n, dimana n adalah jumlah total elemen dikurangi 1.

Merge Sort

Sebelum   mendalami   algoritma  merge  sort,  mari  kita  mengetahui  garis  besar  dari

konsep divide and conquer karena merge sort mengadaptasi pola tersebut.

Pola Divide and Conquer

Beberapa   algoritma   mengimplementasikan   konsep   rekursi   untuk   menyelesaikan

permasalahan.   Permasalahan   utama   kemudian   dipecah   menjadi   sub-masalah,

kemudian  solusi   dari  sub-masalah  akan  membimbing  menuju solusi  permasalahan

utama.

Pada setiap tingkatan rekursi, pola tersebut terdiri atas 3 langkah.

1. Divide

Memilah masalah menjadi sub masalah

2. Conquer

Selesaikan  sub  masalah  tersebut  secara rekursif. Jika sub-masalah  tersebut

    cukup ringkas dan sederhana, pendekatan penyelesaian secara langsung akan lebih efektif

3. Kombinasi

Mengkombinasikan solusi  dari sub-masalah, yang akan membimbing menuju

    penyelesaian atas permasalahan utama

Memahami Merge Sort

Seperti yang telah dijelaskan sebelumnya, Merge sort menggunakan pola divide  and

conquer.   Dengan   hal   ini   deskripsi   dari   algoritma   dirumuskan   dalam   3   langkah

berpola divide-and-conquer. Berikut menjelaskan langkah kerja dari Merge sort.

1. Divide

Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

Conquer   setiap   bagian   dengan   memanggil   prosedur  merge   sort  secara

    rekursif

3. Kombinasi

Mengkombinasikan  dua  bagian tersebut   secara  rekursif  untuk  mendapatkan

    rangkaian data berurutan.

Proses rekursi berhenti jika mencapai elemen dasar.  Hal ini terjadi bilamana bagian

yang  akan diurutkan menyisakan tepat  satu  elemen.  Sisa pengurutan  satu elemen

tersebut menandakan bahwa bagian tersebut telah terurut sesuai rangkaian.

Quicksort

Quicksort ditemukan oleh C.A.R  Hoare.  Seperti pada merge sort, algoritma ini juga

berdasar  pada pola  divide-and-conquer.  Berbeda dengan  merge  sort,  algoritma ini

hanya mengikuti langkah – langkah sebagai berikut :

1. Divide

Memilah rangkaian data menjadi dua sub-rangkaian A[p…q-1] dan A[q+1…r] dimana setiap elemen A[p…q-1]  adalah kurang dari  atau sama dengan A[q] dan   setiap   elemen   pada   A[q+1…r]   adalah   lebih   besar  atau  sama   dengan elemen   pada   A[q].   A[q]   disebut   sebagai   elemen   pivot.   Perhitungan   pada elemen q merupakan salah satu bagian dari prosedur pemisahan.

2. Conquer

Mengurutkan elemen pada sub-rangkaian secara rekursif

Pada algoritma quicksort, langkah ”kombinasi” tidak  di lakukan karena telah terjadi

pengurutan elemen – elemen pada sub-array