I.INSERTION SORTSalah 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.

# Algoritmavoid 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]);

# Contoh

II. BUBBLE SORTPengurutan dengan menggunakan metode bubble sort akan

membandingkan elemen sekarang dengan elemen berikutnya. Jika elemen sekarang lebih besar daripada elemen berikutnya maka elemen terseut ditukar. Jika anda perhatikan, maka setiap langkah dari algoritma ini akan menggeser satu persatu elemen dari kanan ke kiri. Jika barisan bilangan tidak disusun secara horisontal melainkan vertikal, akan terlihat seperti gelembung – gelembung bubble yang naik dari dasar akuarium. Oleh karena itu algoritma ini disebut dengan Bubble Sort.

Diberi nama “Bubble” karena proses pengurutan secara berangsur-angsur bergerak /berpindah ke posisinya yang tepat, seperti gelembung yang keluar dari sebuah gelas bersoda. Bubble Sort mengurutkan data dengan cara membandingkan elemen sekarang dengan elemen berikutnya. Pengurutan Ascending :Jika elemen sekarang lebih besar dari elemen berikutnya maka kedua elemen tersebut ditukar. Pengurutan Descending: Jika elemen sekarang lebih kecil dari elemen berikutnya, maka kedua elemen tersebut ditukar.

Algoritma ini seolah-olah menggeser satu per satu elemen dari kanan ke kiri atau kiri ke kanan, tergantung jenis pengurutannya. Ketika satu proses telah selesai, maka bubble sort akan mengulangi proses, demikian seterusnya. Kapan berhentinya? Bubble sort berhenti jika seluruh array telah diperiksa dan tidak ada pertukaran lagi yang bisa dilakukan, serta tercapai perurutan yang telah diinginkan.

Tahapan yang dilakukan di dalam Bubble Sort adalah sebagai berikut :1. Pengecekkan dapat dilakukan dari data yang paling awal maupun dari

data yang paling akhir. Jika pengecekkan dimulai dari data yang paling awal, maka data yang paling awal tersebut kemudian akan dilakukan pengecekkan dengan data yang ada sesudahnya. Jika ternyata data yang ada di awal tersebut lebih kecil, maka data tersebut akan ditukar. Maka proses pengecekkan tersebut dilakukan sampai dengan data yang paling akhir.

2. Kemudian langkah selanjutanya pengecekkan dilakukan kembali pada data yang palin awal dan kembali dibandingkan dengan data yang ada sesudahnya. Jika data yang di awal tersebut ternyata lebih kecil, maka data tersebut akan ditukar dan proses pengecekkan dilakukan, namun tidak sampai data yang paling akhir. Karena data yang paling akhir merupakan data yang paling kecil. Langkah ini akan diulang terus menerus sesuai dengan jumlah data yang dimasukkan oleh user.

# Algoritma

Dengan algoritma diatas, data terurut naik (ascending), untuk urut turun (descending) silahkan ubah bagian:

, menjadi:

III. QUICK SORT

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. DivideMemilah 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. ConquerMengurutkan elemen pada sub-rangkaian secara rekursif

Pada algoritma quicksort, langkah ”kombinasi” tidak di lakukan karena telah terjadi pengurutan elemen – elemen pada sub-array

# Algoritmavoid 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);

}}

# Contoh

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