Analisis Algoritma: Sorting

Sorting atau Pengurutan data adalah proses mengurutkan data acak menjadi data yang terurut dari data terkecil sampai data terbesar (Ascending) atau dari data terbesar sampai data terkecil (Descending). Proses Sorting ini sering dilakukan dalam pengolahan data.

Berikut adalah beberapa jenis metode pengurutan, yaitu :

1. Bubble Sort

Bubble Sort atau Exchange Sort adalah metode pengurutan yang bisa diibaratkan seperti “gelembung air”. Karena metode ini menggunakan cara penukaran dan membandingkan data yang ada disebelahnya secara berulang, dan proses ini akan berhenti pada saat jumlah banyaknya data dikurangi 1.

Kelebihan Bubble Sort

- Metode pengurutan yang paling simple.
- Sangat mudah dipahami algoritmanya.

Kekurangan Bubble Sort

- Merupakan metode yang paling tidak efisien jika datanya cukup banyak. Pada Bubble Sort jumlah pengulangannya akan tetap sama jumlahnya walaupun data sudah cukup terurut. Karena disebabkan membandingkan semua data untuk menentukan posisinya.

Contoh Pseudocode Bubble Sort

procedure bubble_sort(input/output data : larik)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

i,j,N,temp : integer

Algoritma:

for i <-- 1 to (N-1) do

for j <-- N downto (i+1) do

if (data(j) < data(j-1))

then

temp <-- data(j)

data(j) <-- data(j-1)

data(j-1) <-- temp

endif

endfor

endprocedure

Contoh Implementasi Bubble Sort

2. Selection Sort

Selection Sort dapat disebut juga kombinasi dari searching dan soritng, cara kerja dari algoritma selection sort ini adalah mencari data maksimum atau minimum dari indeks awal sampai indeks akhir, kemudian ditukarkan dengan data pada indeks awal atau akhir tergantung diurutnya secara ascending atau descending, Algoritma Selection Sort ini termasuk dalam comparison-based sorting seperti halnya Bubble Sort.

Selection Sort terbagi menjadi 2 metode pengurutan, yaitu :

- Maximum Selection Sort, yaitu memilih data maksimum sebagai basis pengurutan.
- Minimum Selection Sort, yaitu memilih data minimum sebagai basis pengurutan.

Kelebihan Selection Sort

- Algoritmanya sangat rapat dan mudah diimplementasikan.
- Operasi pertukarannya hanya dilakukan sekali.
- Waktu pengurutan dapat lebih ditekan.
- Mudah menggabungkannya kembali.
- Kompleksitas Selection Sort relatif lebih kecil.

Kekurangan Selection Sort

- Sulit untuk membagi masalah.

Contoh Pseudocode Selection Sort

procedure selec_sort_min_asc(input/output data : larik)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

i,j,N,min,temp : integer

Algoritma:

for i <-- 1 to (N-1) do

min <-- i

for j <-- (i+1) to N do

if (data(j) < data(min))

then

min <-- j

endif

endfor

temp <-- data(i)

data(i) <-- data(min)

data(min) <-- temp

endfor

endprocedure

Contoh Implementasi Selection Sort

3. Insertion Sort

Insertion Sort termasuk dalam comparison-based sorting, metode pengurutan insertion sort ini dengan cara membandingkan data ke-I (dimana I dimulai dari data ke-2 sampai dengan data terakhir) dengan data berikutnya. dan menyisipkan elemen larik pada indeks yang tepat.

Insertion Sort terbagi menjadi 2 metode pengurutan, yaitu :

1. Straight Insertion Sort

Ilustrasi dari langkah-langkah pengurutan straight insertion sort dapat dilihat pada tabel berikut ini :

2. Binary insertion sort

Metode ini digunakan untuk memperbaiki metode Straight Insertion Sort dengan melakukan proses perbandingan yang lebih sedikit dan lebih efisien.

Kelebihan Insertion Sort

- Sederhana dalam implementasinya.
- Efektif jika jumlah data sedikit.
- Jika list sudah terurut atau sebagian terurut makas Insertion Sort akan lebih efisien dibanding
Quicksort.
- Lebih efektif dibanding Bubble Sort, dan Selection Sort
- Loop dalam Insertion Sort sangat cepat, sehingga Insertion sort adalah salah satu metode pengurutan tercepat pada jumlah data sedikit.
- Stabil.

Kekurangan Insertion Sort

- Banyaknya operasi yang diperlukan dalam mencari posisi yang tepat untuk elemen larik.
- Untuk larik yang jumlahnya besar metode ini tidak praktis.
- Jika list terurut terbalik sehingga setiap eksekusi dari perintah harus memindai dan mengganti seluruh bagian sebelum menyisipkan elemen berikutnya.
- Membutuhkan waktu O(n2) pada elemen yang tidak terurut, sehingga tidak cocok dalan pengurutan yang jumlah elemennya banyak.

Contoh Pseudocode Insertion Sort

procedure insertion_sort(input/output data : larik)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

i,j,N,temp : integer

Algoritma:

for i <-- 2 to N do

j <-- i

while ((j > 1) and (data(j) < data(j-1))) do

temp <-- data[j]

data[j] <-- data[j-1]

data[j-1] <-- temp

j <-- j-1

endwhile

endfor

endprocedure

Contoh Implementasi Insertion Sort

4. Shell Sort

Metode pengurutan ini disebut juga metode penambahan menurun (diminishing increment) dikembangkan oleh Donald L. Shell pada tahun 1959. Algoritma ini merupakan perbaikan dari metode pengurutan sisip. Cara kerjannya metode ini dengan membandingkan suatu elemen dengan elemen lain yang memiliki jarak tertentu, kemudian dilakukan penukaran bila diperlukan.

Kelebihan Shell Short

- Algoritmanya sangat rapat dan mudah diimplementasikan.
- Operasi pertukarannya hanya dilakukan sekali.
- Waktu pengurutan dapat lebih ditekan.
- Mudah menggabungkannya kembali.
- Kompleksitas Selection Sort relatif lebih kecil.

Kekurangan Shell Short

- Membutuhkan method tambahan.
- Sulit untuk membagi masalah.

Contoh Pseudocode Shell Sort

procedure InsSort (input/output data : larik, input N, start, step : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

i,j,y : integer

ketemu : boolean

Algoritma:

i <-- start + step

while (i <= N) do

y <-- data[i]

j <-- i – step

ketemu <-- false

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

if (y < data[j])

then

data[j + step] <-- data[j]

else

ketemu <-- true

endif

endwhile

data[j + step] <-- y

i <-- i + step

endwhile

endprocedure

procedure Shellsort(input/output data : larik, input N : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

start,step : integer

Algoritma:

step <-- N

while (step > 1) do

step <-- step div (3 + 1)

for start <-- 1 to step do

InsSort (data, N, start, step)

endfor

endwhile

endprocedure

Contoh Implementasi Shell Sort

5. Merge Sort

Merge Sort merupakan algoritma yang berdasarkan strategi divide and conquer. Cara kerja algoritma ini yaitu memecah susunan data menjadi sublists – sublist kecil, kemudian dilakukan proses pemandingan, penukaran, dan penggabungan data. Berulang sampai data tersebut sudah terurut.

- Divide : Membagi masalah menjadi beberapa submasalah berukuran lebih kecil.
- Conquer: Memecahkan masing-masing submasalah (secara rekursif),
- Combine: Mengabungkan solusi masing-masing submasalah sehingga membentuk solusi masalah semula.

Kelebihan Merge Sort

- Dibanding dengan algoritma lain, merge sort ini termasuk algoritma yang sangat efisien dalam penggunaannya sebab setiap list selalu dibagi bagi menjadi list yang lebih kecil, kemudian digabungkan lagi sehingga tidak perlu melakukan banyak perbandingan.
- Cocok untuk sorting akses datanya lambat misalnya tape drive atau hard disk.
- Cocok untuk sorting data yang biasanya diakses secara sequentially (berurutan),
misalnya linked list, tape drive, dan hard disk.

Kekurangan Merge Sort

- Kekurangan Merge Sort yaitu terlalu banyak menggunakan ruang pada memori.
- Merge Sort membutuhkan lebih banyak ruang daripada jenis sorting lainnya.

Contoh Pseudocode Merge Sort

procedure merge_sort(input/output data : larik, input left,mid,right : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : menghasilkan data (1:N) yang terbagi dua bagian}

Kamus:

temp : larik

Algoritma:

i <-- left

j <-- mid + 1

k <-- left

while ((i <= mid) and (j <= right)) do

if (data(i) < data(j))

then

temp(k) <-- data(i)

i <-- i + 1

else

temp(k) <-- data(j)

j <-- j + 1

endif

k <-- k + 1

endwhile

while (i <= mid) do

temp(k) <-- data(i)

k <-- k + 1

i <-- i + 1

endwhile

while (j <= right) do

temp(k) <-- data(j)

k <-- k + 1

j <-- j + 1

endwhile

for k <-- left to right do

data(k) <-- temp(k)

endfor

endprocedure

procedure merge_sort(input/output data : larik, left,right : integer)

{I.S. : Data (1:N) yang terbagi dua bagian sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

mid : integer

Algoritma:

if (left < right)

then

mid <-- (left + right) div 2

merge_sort_asc (data, left, mid)

merge_sort_asc (data, mid+1, right)

merge_sort (data, left, mid, right)

endif

endprocedure

Contoh Implementasi Merge Sort

6. Heap Sort

Metode heap sort adalah metode dari pengembangan tree. Metode sorting ini mengurutkan data berdasarkan perbandingan, dan merupakan salah satu algoritma pengurutan tercepat karena mampu mengurutkan data yang sangat banyak dengan waktu yang cepat. Algoritma Heap Sort memiliki kompleksitas yang besar dalam pembuatan kodenya. Programmer sering menggunakan ini ketika berhadapan dengan array yang jumlahnya sangat besar.

Beberapa aturan dalam Heap Sort sebagai berikut :

- Untuk mengisikan heap dimulai dari level 1 sampai ke level dibawahnya, bila dalam level yang sama semua kunci heap belum terisi maka tidak boleh mengisi dibawahnya.
- Heap dalam kondisi terurut apabila left child <> parent.
- Penambahan kunci diletakkan pada posisi terakhir dari level dan disebelah kanan child yg terakhir, kemudian diurutkan dengan cara upheap.
- Bila menghapus heap dengan mengambil kunci pada parent di level 1 kemudian digantikan posisi kunci terakhir, selanjutnya disort kembali metode downheap.
- Dalam langkah-langkahnya heap sort terbagi menjadi 2 langkah yaitu insert_heap dan build_heap.

Kelebihan Heap Sort

- Algoritma Heap Sort banyak digunakan karena efisiensi waktunya.
- Penggunaan memori yang sedikit.

Kekurangan Heap Sort

- Heap Sort membutuhkan banyak ruang memori untuk proses pengurutan.
- Algoritmanya yang memilki kompleksitas yang besar.

Contoh Pseudocode Heap Sort

procedure swap(input/output a,b : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah ditukar}

Kamus:

temp : integer

Algoritma:

temp <-- a

a <-- b

b <-- temp

endprocedure

procedure Shiftdown(input/output data : larik)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah memenuhi kondisi heap}

Kamus:

Start,akhir,root,child : integer

Algoritma:

root <-- start

while ((root*2+1) <= akhir) do

child <-- root*2+1

if (child < akhir) and (data[child] < data[child+1])

then

child <-- child + 1

if (data[root] < data[child])

then

swap (data[root], data[child])

root <-- child

else

return

endif

endwhile

endprocedure

procedure Heapify(input/output data : larik)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah dibentuk menjadi heap}

Kamus:

Start, count : integer

Algoritma:

start <-- (count - 1) div 2

while (start >= 0) do

Shiftdown (data, start, count - 1)

start <-- start – 1

endwhile

endprocedure

procedure heapify(input/output data : larik, input N : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan heap yang sudah terurut secara ascending}

Kamus:

akhir : integer

Algoritma:

Heapify (data,N)

akhir <-- N - 1

while (akhir > 0) do

Swap(data[akhir], data[0])

akhir <-- akhir - 1

Shiftdown (data, 0, akhir)

Endwhile

enprocedure

Contoh Implementasi Heap Sort

7. Quick Sort

Metode Quick Sort sering disebut juga metode partisi (Patition Exchange Sort). Quick Sort merupakan yang paling efisien diantara metode sorting lainnya. Cara kerja metode ini yaitu dengan membagi dua bagian susunan data, dengan nilai data awal sebagai niali tengahnya. Sehingga akan diperoleh kelompok data di sebelah kiri yang lebih kecil dari nilai tengah dan kelompok data di sebelah kanan yang lebih besar dari nilai tengah jika kita mengurutkannya secara ascending.

Kelebihan Quick Sort

- Secara umum memiliki kompleksitas O(n log n).
- Algoritmanya sederhana dan mudah diterapkan pada berbagai bahasa pemrograman.
- Dalam prakteknya adalah yang tercepat dari berbagai algoritma pengurutan dengan perbandingan, seperti merge sort dan heap sort.
- Melakukan proses langsung pada input (in-place) dengan sedikit tambahan memori.
- Bekerja dengan baik pada berbagai jenis input data (seperti angka dan karakter).
- Quicksort dapat dengan mudah diparalelkan karena sifatnya “divide-and-conquer”.

Kekurangan Quick Sort

- Sedikit kesalahan dalam penulisan program membuatnya bekerja tidak beraturan (hasilnya tidak benar atau tidak pernah selesai).
- Memiliki ketergantungan terhadap data yang dimasukkan, yang dalam kasus terburuk memiliki kompleksitas O(n2).
- Secara umum bersifat tidak stable, yaitu mengubah urutan input dalam hasil akhirnya (dalam hal inputnya bernilai sama).
- Pada penerapan secara rekursif (memanggil dirinya sendiri) bila terjadi kasus terburuk dapat menghabiskan stack dan memacetkan program.

Contoh Pseudocode Quick Sort

procedure quick_sort(input/output data : larik, input left, right : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

i, j : integer

temp : integer

Algoritma:

while (right > left) do

i <-- left

j <-- right

temp <-- data(left)

while (i < j) do

while (data(j) > temp) do

j <-- j – 1

endwhile

data(i) <-- data(j)

while (i < j) and (data[i] <= temp) do

i <-- i + 1

endwhile

data(j) <-- data(i)

endwhile

data(i) <-- temp

quick_sort_asc(data,left,i-1)

left <-- i + 1

endwhile

endprocedure

Contoh Implementasi Quick Sort

8. Radix Sort

Radix Sort merupakan metode sorting tanpa perbandingan atau Non-Comparison Sort. Proses yang dilakukan dalam metode ini ialah mengklasifikasikan data sesuai dengan kategori terurut yang tertentu dan dalam tiap kategorinya dilakukan pengklasifikasian lagi dan berulang sesuai kebutuhan. Dan kemudian subkategori-subkategori tersebut digabungkan kembali, dilakukan hanya dengan metode sederhana concatenation.

Berdasarkan urutan pemrosesan radixnya, Radix Sort terbagi 2 macam, yaitu: LSD (Least Significant Digit), di mana pemrosesan dimulai dari radix yang paling tidak signifikan. dan MSD (Most Significant Digit), di mana pemrosesan dimulai dari radix yang paling signifikan.

Kelebihan Radix Sort

- Algoritmanya sangat efektif. Hal ini dapat dilihat dari kompleksitas waktu
asimptotiknya yang sangat kecil (O(kN)). Hal ini mengakibatkan algoritma radix sort
sangat efektif untuk data dalam jumlah yang sangat besar sekalipun.
- Konsep Algoritma mudah dipahami.

Kekurangan Radix Sort

- Realisasi program rumit
- Kurang fleksibel untuk tipe data lain.

Contoh Pseudocode Radix Sort

function pangkat(input nilai, pemangkat : integer) --> integer

{I.S. : nilai sudah terdefinisi}

{F.S. : menghasilkan fungsi pangkat}

Kamus: {Tidak ada}

Algoritma:

if (pemangkat = 0)

then

pangkat <-- 1

else

pangkat <-- nilai * pangkat(nilai,pemangkat-1)

endif

endprocedure

procedure radix_sort_asc(input/output data : larik, digit_max : integer)

{I.S. : Data (1:N) sudah terdefinisi }

{F.S. : Menghasilkan data yang sudah terurut secara Ascending}

Kamus:

bucket, pencacah, temp1 : integer

temp : angka

Algoritma:

for temp1 <-- 1 to digit_max do

pencacah <-- 0

for bucket <-- 0 to 9 do

for j <-- 1 to N do

k <-- (data(j) div pangkat(10,temps-1)) mod 10

if (k = bucket)

then

pencacah <-- pencacah + 1

temp[pencacah] <-- data[j]

endif

endfor

for i <-- 1 to N do

data(i) <-- temp(i)

endfor

endprocedure

Contoh Implementasi Radix Sort

Silahkan klik url dibawah ini untuk melihat ilustrasi beberapa metode sorting :
https://www.toptal.com/developers/sorting-algorithms

Sumber :

https://en.wikipedia.org/wiki/Sorting_algorithm
Munir, Rinaldi. 2007. Algoritma dan Pemrograman dalam bahasa Pascal dan C Edisi Revisi. Bandung: Informatika.
Nur Wahyudi, Wahyudi. Januari 2009, "Algoritma Sederhana dalam Memahami Proses Pengurutan Data". Jurnal Teknologi Informasi DINAMIK. Volume XIV, No.1.
Fathoni, Saniman dan Muhaammad. Januari 2010. "Konsep Sorting Dalam Pemrograman". Jurnal SAINTIKOM. Volume VIII, No.1.
Mulia, Firdi. "Penerapan Pohon Dalam Heap Sort". Makalah. STEI, Teknik Informatika, Institut Teknologi Bandung.