SORTING

Algoritma Sorting

Tujuan

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.

Pengenalan Pemrograman 2 1

J.E.N.I.

Algoritma

void insertionSort(Object array[], int startIdx, int endIdx) {

for (int i = startIdx; i < endIdx; i++) {

int k = i;

for (int j = i + 1; j < endIdx; j++) {

if (((Comparable) array[k]).compareTo(array[j])>0) {

k = j;

}

}

swap(array[i],array[k]);

}

}

Sebuah Contoh

Data

Mango

Apple

Peach

Orange

Banana

1st Pass

Mango

Apple

Peach

Orange

Banana

2nd Pass

Apple

Mango

Peach

Orange

Banana

3rd Pass

Apple

Mango

Orange

Peach

Banana

4th Pass

Apple

Banana

Mango

Orange

Peach

Gambar 1.1.2: Contoh insertion sort

Pada akhir modul ini, anda akan diminta untuk membuat implementasi bermacam

algoritma sorting yang akan dibahas pada bagian ini.

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.

Pengenalan Pemrograman 2 2

J.E.N.I.

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.

Algoritma

void selectionSort(Object array[], int startIdx, int endIdx) {

int min;

for (int i = startIdx; i < endIdx; i++) {

min = i;

for (int j = i + 1; j < endIdx; j++) {

if (((Comparable)array[min]).compareTo(array[j])>0) {

min = j;

}

}

swap(array[min], array[i]);

}

}

Sebuah Contoh

Data

Maricar

Vanessa

Margaux

Hannah

Rowena

1st Pass

Hannah

Vanessa

Margaux

Maricar

Rowena

2nd Pass

Hannah

Margaux

Vanessa

Maricar

Rowena

3rd Pass

Hannah

Margaux

Maricar

Vanessa

Rowena

4th Pass

Hannah

Margaux

Maricar

Rowena

Vanessa

Figure 1.2.2: Contoh selection sort

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.

Pengenalan Pemrograman 2 3

J.E.N.I.

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.

Algoritma

void mergeSort(Object array[], int startIdx, int endIdx) {

if (array.length != 1) {

//Membagi rangkaian data, rightArr dan leftArr

mergeSort(leftArr, startIdx, midIdx);

mergeSort(rightArr, midIdx+1, endIdx);

combine(leftArr, rightArr);

}

}

Pengenalan Pemrograman 2 4

J.E.N.I.

Sebuah Contoh

Rangkaian data:

7 2 5 6

Membagi rangkaian menjadi dua bagian:

LeftArr RightArr

7 2 5 6

Membagi LeftArr menjadi dua bagian:

LeftArr RightArr

7 2

Mengkombinasikan

2 7

Membagi RightArr menjadi dua bagian:

LeftArr RightArr

Mengkombinasikan

5 6

Mengkombinasikan LeftArr dan RightArr.

2 5 6 7

Gambar 1.3.4: Contoh merge sort

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.

Pengenalan Pemrograman 2 5

J.E.N.I.

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

Algoritma

void quickSort(Object array[], int leftIdx, int rightIdx) {

int pivotIdx;

/* Kondisi Terminasi */

if (rightIdx > leftIdx) {

pivotIdx = partition(array, leftIdx, rightIdx);

quickSort(array, leftIdx, pivotIdx-1);

quickSort(array, pivotIdx+1, rightIdx);

}

}

Sebuah Contoh

Rangkaian data:

3 1 4 1 5 9 2 6 5 3 5 8

Pilih sebuah elemen yang akan menjadi elemen pivot.

3 1 4 1 5 9 2 6 5 3 5 8

Inisialisasi elemen kiri sebagai elemen kedua dan elemen kanan sebagai elemen

akhir.

kiri kanan

3 1 4 1 5 9 2 6 5 3 5 8

Geser elemen kiri kearah kanan sampai ditemukan nilai yang lebih besar dari elemen

pivot tersebut. Geser elemen kanan ke arah kiri sampai ditemukan nilai dari elemen

yang tidak lebih besar dari elemen tersebut.

kiri kanan

3 1 4 1 5 9 2 6 5 3 5 8

Tukarkan antara elemen kiri dan kanan

kiri kanan

Pengenalan Pemrograman 2 6

J.E.N.I.

3 1 3 1 5 9 2 6 5 4 5 8

Geserkan lagi elemen kiri dan kanan.

kiri kanan

3 1 3 1 5 9 2 6 5 4 5 8

Tukarkan antar elemen kembali.

kiri kanan

3 1 3 1 2 9 5 6 5 4 5 8

Geserkan kembali elemen kiri dan kanan.

kanan kiri

3 1 3 1 2 9 5 6 5 4 5 8

Terlihat bahwa titik kanan dan kiri telah digeser sehingga mendapatkan nilai elemen

kanan < elemen kiri. Dalam hal ini tukarkan elemen pivot dengan elemen kanan.

pivot

2 1 3 1 3 9 5 6 5 4 5 8

Gambar 1.4.2: Contoh quicksort

Kemudian urutkan elemen sub-rangkaian pada setiap sisi dari elemen pivot.