ALGORITMA SORT
• Pengurutan data sangat penting untuk data yang bertipe data numerik ataupun karakter.
• Pengurutan dapat dilakukan secara ascending (urut naik) dan descending (urut turun)
• Pengurutan (Sorting) adalah proses menyusun kembali data yang sebelumnya telah disusun dengan suatu pola tertentu, 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

DEKLARASI ARRAY UNTUK SORTING
Deklarasikan:
int data[100];
int n; //untuk jumlah data

Fungsi untuk Tukar 2 Buah Data:
public tukar(int *a,int *b){
int t=*a;
*a=*b;
*b=t;
}

METODE PENGURUTAN DATA
• Pengurutan berdasarkan perbandingan (comparison-based sorting)
o Bubble Sort, Exchange Sort
• Pengurutan berdasarkan prioritas (priority queue sorting method)
o Selection Sort, Heap Sort
• Pengurutan berdasarkan penyisipan dan penjagaan terurut (insert and keep sorted method)
o Insertion Sort, Tree Sort
• Pengurutan berdasarkan pembagian dan penguasaan (devide and conquer method)
o Quick Sort, Merge Sort
• Pengurutan berkurang menurun (diminishing increment sort method)
o Shell Sort

BUBBLE SORT
• Metode sorting termudah akan tetapi merupakan metode yang paling lambat.
• 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.

Procedure Buble Sort

//Versi 1
public bubble_sort(){
for(int i=1;i=i;j--){
if(data[j]data[j+1])
tukar(&data[j],&data[j+1]); //descending
}
}
}

EXCHANGE SORT
• Sangat mirip dengan Bubble Sort
• Banyak yang mengatakan Bubble Sort sama dengan Exchange Sort
• Pebedaan : dalam hal bagaimana membandingkan antar elemen elemennya.
• Exchange sort membandingkan suatu elemen dengan elemen-elemen lainnya dalam array tersebut, dan melakukan pertukaran elemen jika perlu. Jadi ada elemen yang selalu menjadi elemen pusat (pivot).
• Sedangkan Bubble sort akan membandingkan elemen pertama/terakhir dengan elemen sebelumnya/sesudahnya, kemudian elemen sebelum/sesudahnya itu akan menjadi pusat (pivot) untuk dibandingkan dengan elemen sebelumnya/sesudahnya lagi, begitu seterusnya.

Procedur e Exchange Sort

public exchange_sort()
{
for (int i=0; i= 0; i--)
siftDown(numbers, i, array_size);

for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
new siftDown(numbers, 0, i-1);
}
}

private siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;

done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;

if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
}

SELECTION SORT
• Merupakan kombinasi antara sorting dan searching
• Untuk setiap proses, akan dicari elemen-elemen yang belum diurutkan yang memiliki nilai terkecil atau terbesar akan dipertukarkan ke posisi yang tepat di dalam array.
• Misalnya untuk putaran pertama, akan dicari data dengan nilai terkecil dan data ini akan ditempatkan di indeks terkecil (data[0]), pada putaran kedua akan dicari data kedua terkecil, dan akan ditempatkan di indeks kedua (data[1]).
• Selama proses, pembandingan dan pengubahan hanya dilakukan pada indeks pembanding saja, pertukaran data secara fisik terjadi pada akhir proses.

Procedure Selection Sort

public selection_sort(){
for(int i=0;itemp && j>=0){
data[j+1] = data[j];
j--;
}
data[j+1] = temp;
}
}

MERGE SORT
• Data yang akan diurutkan dibagi menjadi 2 bagian, dan di tempatkan di 2 array yang berbeda.
• Merge Sort membutuhkan 3 array, 1 array untuk menempatkan hasilnya, dan sisanya merupakan data yang akan di urutkan.
• Ke-2 array tersebut di urutkan kemudian disimpan pada masing-masing array, lalu digabungkan pada array yang pertama.
• Misal : Data a, dipecah dalam array ke-2 dan array ke-3, kemudian array ke-2 dan array ke-3 melakukan proses pengurutan. Setelah mendapatkan hasil, hasil pengurutan dari array ke-2 dan ke-3digabungkan dalam array ke-1.

Procedure Merge Sort

class Merge {
public mergeSort(int numbers[], int temp[], int array_size)
{
new m_sort(numbers, temp, 0, array_size - 1);
}

private m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
new m_sort(numbers, temp, left, mid);
new m_sort(numbers, temp, mid+1, right);

new merge(numbers, temp, left, mid+1, right);
}
}

private merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
}

QUICK SORT
• Merupakan metode yang sangat cepat dengan teori algoritma yang mudah, tetapi dalam penulisan programnya sangat sulit.
• Merupakan kombinasi antara metode Exchange Sort dan metode Merge Sort.
• Ada empat langkah dalam melakukan metode ini, yaitu:
o If (n<=1), maka kembali ke awal atau mengehentikan proses.
o Ambil satu elemen dari array sebagai Pusat (Pivot) seperti halnya di metode Exchange Sort.
o Array dipecah menjadi dua bagian, pecahan array pertama terdiri dari elemen yang lebih besar dari Pivot, sedangkan pecahan array ke-2 memiliki elemen yang lebih kecil dari Pivot.
o Kemudian, kedua pecahan tersebut melakukan proses pengurutan.

Procedure Quick Sort

Class Quick {
public quickSort(int numbers[], int array_size)
{
new q_sort(numbers, 0, array_size - 1);
}

private q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
new q_sort(numbers, left, pivot-1);
if (right > pivot)
new q_sort(numbers, pivot+1, right);
}
}

SHELL SORT
• Merupakan metode O(n2) yang sangat efisien dan komplek.
• Diciptakan oleh Donald Shell tahun 1959.
• Merupakan metode berupa Increment Sort, dan lebih dikenal dengan “comb sort” dalam dunia pemrograman yang belum sempurna.
• Konsepnya hampir sama dengan metode Insertion Sort.

Procedure Shell Sort

class Shell_Sort {
public shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;

increment = 3;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}
}