Saturday, July 8, 2017

Kupas Tuntas Algoritma Pengurutan (sorting)


Pengurutan (sorting) adalah proses mengatur sekumpulan objek menurut urutan atau susunan tertentu. Data yang diurut dapat berupa data bertipe dasar atau tipe terstruktur (record). Pengurutan dikatakan stabil jika dua atau lebih data yang sama (atau identik) tetap pada urutan yang sama setelah pengurutan.
Pengurutan dapat dilakukan secara ascending (urutan naik) dan descending (urutan turun). Pengurutan (sorting)  merupakan proses pengurutan data yang sebelumnya disusun secara acak sehingga tersusun secara teratur menurut aturan tertentu.
Contoh :
Data acak     : 5 6 8 1 3 25 10
Ascending     : 1 3 5 6 8 10 25
Descending   : 25 10 8 6 5 3 1

Ada beberapa algoritma pengurutan dalam berbagai literatur komputer, yang akan dibahas antara lain :
  1. Metode pengurutan apung (Bubble Sort)
  2. Metode pengurutan seleksi (Selection Sort)
  3. Metode pengurutan sisip (Insertion Sort)
  4. Metode pengurutan Shell (Shell Sort)
Dua Algoritma pertama melakukan prinsip pertukaran elemen dalam proses pengurutan. Sedangkan dua algoritma terakhir melakukan prinsip geser dan sisip elemen dalam proses pengurutan.
Algoritma pengurutan dapat diklasifikasikan menjadi :
  • Algoritma pengurutan internal, yaitu algoritma pengurutan untuk data yang disimpan didalam memori komputer.
  • Algoritma pengurutan eksternal, yaitu metode pengurutan untuk data yang disimpan didalam disk storage, disebut juga pengurutan arsip.

Kupas Tuntas Algoritma Pengurutan Apung (Bubble Sort)

Algoritma pengurutan Apung (bubble sort) diinspirasi oleh gelembung sabun yang berada diatas permukaan air. Untuk mendapatkan data larik yang terurut menaik, loka dari algoritma pengurutan apung secara global sebagai berikut:

Untuk setiap pass i = 1, 2, … , n-1, lakukan :
mulai dari elemen k = n, n-1, …, i+1, lakukan :

     - Bandingkan L[k] dengan L[k-1]
     - Pertukarkan L[k] dengan L[k-1] jika L[k] < L[k-1]Logika Rincian setiap pass sebagai berikut:
  • Pass 1    : mulai dari elemen ke-k = n,n-1,…,2, bandingkan L[k] dengan L[k-1]. Jika L[k]<L[k-1], pertukarkan     L[k] dengan L[k-1], sehingga L[1] berisi harga minimum pertama
  • Pass 2    : mulai dari elemen ke-k = n,n-1,…,3, bandingkan L[k] dengan L[k-1]. Jika L[k]<L[k-1], pertukarkan     L[k] dengan L[k-1], sehingga L[2] berisi harga minimum kedua.
  • Pass 3    : mulai dari elemen ke-k = n,n-1,…,4, bandingkan L[k] dengan L[k-1]. Jika L[k]<L[k-1], pertukarkan     L[k] dengan L[k-1], sehingga L[3] berisi harga minimum ketiga
lakukan sampai ke

  • .Pass n-1: mulai dari elemen ke-k = n, bandingkan L[k] dengan L[k-1]. Jika L[k]<L[k-1], pertukarkan L[k]     dengan L[k-1], pada akhir pass n-1, elemen L[n-1] berisi nilai minimum ke (n-1) dan larik L[1..n-1]     terurut menaik.
Algortimanya pengurutan apung/bubblesort dari kecil ke besar(ascending) bisa dituliskan sebagai berikut :