Sorting 

 1. Insertion sort

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.

Algoritmanya :

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

}

}

2.  Selection sort

 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.

Algoritmanya :

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

}

}

3.  Merge sort

Merge sort menggunakan poladivide and conquer. Dengan hal ini deskripsi dari algoritma dirumuskan dalam 3 langkah
berpola divide-and-conquer. Berikut menjelaskan langkah kerja dariMerge sort.

1. Divide

Memilah elemen – elemen dari rangkaian data menjadi dua bagian.

2. Conquer

Conquer setiap bagian dengan memanggil prosedur merge sortsecara 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.

Algoritmanya :

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

}

}

Gambar3.1. Diagram Merge Sort

4. Quick sort

 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

Algoritmanya :

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

}

}

Gambar 3.2. Diagram Quick Sort

5.  Counting sort

Adalah sebuah algoritma sorting linear yang digunakan untuk mengurutkan ‘item’ ketika urutannya telah ditentukan dan memiliki panjang yang terbatas. Bilangan interval yang telah tetap, katakana k1 ke k2 adalah contoh dari ‘item’ tersebut. Counting sort sebenarnya merupakan metode pengurutan yang memanfaatkan index variabel array. Hanya effektif pada data yang nilainya kecil.

Algoritma ini diproses dengan mendefinisikan sebuah hubungan urutan antara ‘item’ yang akan disorting. Katakana ‘item’ yang akan disorting adalah variable A. Maka, terdapat sebuah array tambahan dengan ukuran yang serupa dengan array A. katakana array tersebut adalah array B. untuk setiap element di A, sebut e, algoritma ini menyimpan jumlah ‘item’ di A lebih kecil dari atau sama dengan e di B(e). jika hasil sorting yang terakhir disimpan di array C, maka untuk masing-masing e di A, dibuat dalam arah yang sebaliknya, yaitu C[B(e)]=e. setelah step di atas, niali dari B(e) berkurang dengan 1.

Algoritma ini membuat 2 passover A dan passover B. Jika ukuran dari range k lebih kecil dari ukuran input n, maka time complexity = O(n). perhatikan juga bahwa algoritma ini stabil yang berarti bahwa sambungan diselesaikan dengan langsung mengabarkan element-element yang muncul pertama kali.

Adapun syarat algoritma ini berjalan dengan baik ialah:

1. Data harus bilangan bulat yang bernilai lebih besar atau sama dengan nol
2. Range data diketahui

Ada 3 macam array yang terlibat:

1. Array untuk mengisi bilangan yang belum diurutkan.
2. Array untuk mengisi frekuensi bilangan itu, sekaligus sebagai penghitung kejadian.
3. Array untuk mengisi bilangan yang sudah diurutkan.

Algoritmanya :

countingsort(A[], B[], min, max, n)
for i = min to max do
C[i] = 0

for j = 1 to n do
C[A[j]] = C[A[j]] + 1

for i = min + 1 to max do
C[i] = C[i] + C[i-1]

for j = n downto 1 do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] – 1