korayucar
7/7/2016 - 7:37 AM
Naive recursive quicksort implementation with some benchmarking code. Note that this implementation is for demonstration only. It will fail
Naive recursive quicksort implementation with some benchmarking code. Note that this implementation is for demonstration only. It will fail a long reverse ordered sequence since it always picks the last element for partitioning around. The call stack depth will be too high in that case. Long number of equal elements will also fail. Code does not implement three way partitioning.
public class QuickSort{
public static void sort(int[] arr){
quickSort(arr , 0 , arr.length-1);
}
private static void quickSort(int[] arr , int start , int end){
if(start >= end)
return;
int p = partition(arr, start , end);
quickSort(arr , start , p-1);
quickSort(arr, p+1, end);
}
private static int partition(int[] arr , int start , int end) {
assert end < arr.length;
assert end > start;
assert end >= start;
pickMediumElement(arr,start , end);
int origin = arr[end];
int p = start;
for(int i = start ; i < end ; i++){
if(arr[i] < origin)
{
swap (arr , p , i);
p++;
}
}
swap(arr , p , end);
return p;
}
private static void swap (int [] arr , int i , int j){
int dummy = arr[i];
arr[i] = arr[j];
arr[j] = dummy;
}
/** picks the medium element to partition around and puts it to end index */
private static void pickMediumElement(int arr[] , int start , int end){
}
static Runtime instance = Runtime.getRuntime();
static int mb = 1024 * 1024;
public static void main(String... args){
Random r = new Random();
for(int j = 1 ; j < 100000002 ; j*=10) {
System.out.println();
System.gc();
System.out.println("Used Memory after gc: "
+ (instance.totalMemory() - instance.freeMemory()) / mb);
int[] arr = new int[j];
for (int i = 0; i < arr.length; i++) {
arr[i] = r.nextInt();
}
System.out.println("Used Memory after array creation: "
+ (instance.totalMemory() - instance.freeMemory()) / mb);
long startTime = System.nanoTime();
QuickSort.sort(arr);
long endTime = System.nanoTime();
System.out.println("Used Memory after sort: "
+ (instance.totalMemory() - instance.freeMemory()) / mb);
System.out.println("time passed : " +(endTime - startTime)/1000+" μs");
for (int i = 1; i < arr.length; i++) {
if(arr[i] < arr[i-1] )
throw new IllegalStateException("sort failed");
}
}
}
}