Algoritma Sorting merupakan algoritma yang digunakan untuk mengurutkan data baik secara ascending maupun descending. Efesiensi algoritma sorting sangat penting untuk optimasi dalam penggunaan dengan algoritma yang lain, contohnya algoritma seraching dan merge yang memerlukan pengurutan secara benar dan cepat. Terdapat berbagai algoritma sorting yang sering digunakan. Algoritma-algoritma tersebut adalah :

•   Bubble sort
•   Insertion sort
•   Shell sort
•   Merge sort
•   Heapsort
•   Quicksort
•   Counting Sort
•   Bucket sort
•   Radix sort
•   Distribution sort

Dalam analisa run time algoritma sorting ini, penulis menggunakan 4 algoritma yaitu :
•   Selection Sort
•   Insertion Sort
•   Buble Sort
•   Merge Sort

Metode yang digunakan untuk uji coba analisa running time ini adalah dengan mengimplementasikan algoritma sorting ke dalam bahasa Java dengan editor Netbeans. Selanjutnya akan diberikan input yang sama untuk membandingkan aktu yang diperlukan masing-masing algoritma untuk mengurutkan data. Input data dalam analisa algoritma sorting ini menggunakan bilangan random dari 0 sampai 1000. Bilangan random ini digenerate oleh sebuah method yang diberi nama generateInput(); Netbeans dilengkapi dengan fasilitas profiling yang bisa digunakan untuk menganalisa performance dari program yang diekskusi. Fasilitas profiling ini yang digunakan penulis untuk menganalisa running time masing-masing algoritma.

Analisa Running Time ( dalam satuan ms)

Jumlah Input	Selection Sort	Insertion Sort	Merge Sort	Quick Sort
100	0.141	0.104	0.036	0.011
1000	2.16	1.80	0.043	0.030
10000	141	67.7	0.351	0.046
100000	12866	5982	1.53	0.029
1000000	1327757	677715	4.97	0.032

Berikut adalah Source Code Sorting dengan Java :

/**
* @author resika arthana
*/ package daa;
import java.util.Random;
public class Sorting {
public int[] selectionSort(int[] arr) {
int i, j, minIndex, tmp;
int n = arr.length;
for (i = 0; i < n – 1; i++) {
minIndex = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
if (minIndex != i) {
tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
return arr;
}

public int[] insertionSort(int[] arr) {
int i, j, newValue;
for (i = 1; i < arr.length; i++) {
newValue = arr[i];
j = i;
while (j > 0 && arr[j – 1] > newValue) {
arr[j] = arr[j – 1];
j–;
}
arr[j] = newValue;
}
return arr;
} public int[] bubbleSort(int[] arr) {
boolean swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < arr.length – j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
return arr;
}

int partition(int arr[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i < = j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j–;
if (i < = j) {
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j–;
}
};
return i;
}
public int[] quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index – 1)
quickSort(arr, left, index – 1);
if (index < right)
quickSort(arr, index, right);
return arr;
} public int[] generateInput(int jum){
int[] arr= new int[jum];
Random ran=new Random();
for (int i=0; i<jum;i++){
arr[i]=ran.nextInt(100000000);
}
return arr;
}
public void printArray(int arr[]){
for (int i=0;i<arr.length;i++){
System.out.println("data ke "+i+" : "+arr[i]);
}
}
public static void main(String[] args){
Sorting sort=new Sorting();
int jumInput=1000000; //jumlah input
int[] inputArr=sort.generateInput(jumInput);
int[] outputArr;

System.out.println("JUM INPUT : "+jumInput);
outputArr=sort.insertionSort(inputArr);
outputArr=sort.bubbleSort(inputArr);
outputArr=sort.quickSort(inputArr,0,0);
outputArr=sort.selectionSort(inputArr);
//sort.printArray(outputArr);

}

}