Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package yourid;
- import java.lang.reflect.Array;
- import java.util.*;
- public class QuickSort {
- //cutoffs, you should run experiments to find good values
- public static int a = 5;
- public static int b =1000000000;
- public static int c = 100;
- public static Random random = new Random();
- public static void sort(int[] array){
- sort(array,0,array.length-1);
- }
- //You need to implement this
- private static void shuffle(int[] a){
- for(int i = 0; i<a.length;i++){
- int randPos = random.nextInt(a.length);
- int temp = a[i];
- a[i]=a[randPos];
- a[randPos]=temp;
- }
- }
- //You need to implement this
- private static int partitionByMedianOf3(int[] array, int lo, int hi){
- int middle = (hi-lo)/2;
- int pivot = median3(array,lo,middle,hi);
- int temp = array[pivot];
- array[pivot] = array[lo];
- array[lo] = temp;
- return partition(array,lo,hi);
- }
- //You need to implement this
- private static int partitionByMedianOf9(int[] array, int lo, int hi){
- int middle = (hi-lo)/2;
- int m1 = median3(array,lo,middle,hi);
- int m2 = median3(array,lo+1,middle-1,hi-1);
- int m3 = median3(array,lo+2,middle+1,hi-2);
- int pivot = median3(array,m1,m2,m3);
- int temp = array[pivot];
- array[pivot] = array[lo];
- array[lo] = temp;
- return partition(array,lo,hi);
- }
- private static int median3(int[] array,int i,int j, int k){
- int temp[] = new int[]{array[i],array[j],array[k]};
- insertionSort(temp,0,2);
- if(temp[1]==array[i])return i;
- else if (temp[1]==array[j])return j;
- else return k;
- }
- //You need to implement this
- public static void insertionSort(int[] array, int lo, int hi){
- int compares = 0;
- for(int i = lo; i<=hi;i++){
- for(int j = compares;j>0;j--){
- if(array[j]<array[j-1]){
- int temp = array[j];
- array[j]=array[j-1];
- array[j-1]=temp;
- }else {
- break;
- }
- }
- compares++;
- }
- }
- //partion by the first element
- private static int partition(int[] array, int lo, int hi){
- int pivot = array[lo], i = lo, j = hi+1;
- while (true){
- while (array[++i] < pivot) if (i == hi) break;
- while (array[--j] > pivot) if (j == lo) break;
- if (i >= j) break;
- int tmp = array[i];
- array[i] = array[j];
- array[j] = tmp;
- }
- array[lo] = array[j];
- array[j] = pivot;
- return j;
- }
- //You should modify this to use the various cutoffs
- private static void sort(int[] array, int lo, int hi){
- int j;
- int N = hi-lo;
- if(N<a){
- insertionSort(array, lo, hi);
- return;
- }
- if (hi <= lo) return;
- j = partition(array, lo, hi);
- /*
- if(N<b){
- j = partition(array,lo,hi);
- }else if(N<c){
- j = partitionByMedianOf3(array, lo, hi);
- }
- else {
- j = partitionByMedianOf9(array,lo,hi);
- }*/
- //recursively sort the left and right subarray
- sort(array, lo, j-1);
- sort(array, j+1, hi);
- }
- //You can use this for testing, we will not grade it
- public static void main(String args[]) throws Exception{
- b = 1000000000;
- figureA(5);
- /* int[] ints = GenerateArray(1000);
- sort(ints);
- if(!test(ints)){
- System.err.println("not sorted");
- }
- int[] ints = GenerateArray(1000000);
- shuffle(ints);
- Utilities.startTimer();
- sort(ints);
- System.out.println(Utilities.checkTimer());
- for (int i:ints){
- System.out.println(i);
- }
- System.out.println(test(ints));*/
- }
- public static int[] GenerateArray(int size){
- int[] temp = new int[size];
- for(int i=0;i<size;i++){
- temp[i] = random.nextInt(2000000000);
- }
- return temp;
- }
- public static boolean test(int[] array){
- int k = array.length;
- for(int i = 1; i<k;i++){
- if(array[i-1]>array[i]){
- return false;
- }
- }
- return true;
- }
- public static void figureA(int k){
- b = 20;
- a = k;
- Utilities.startTimer();
- for(int i = 0;i<100000;i++){
- int[] ints = GenerateArray(1000);
- sort(ints);
- if(!test(ints)){
- System.err.println("not sorted");
- }
- }
- System.out.println("avgTime(a="+a+"): "+Utilities.checkTimer()/10.0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement