Hetalia: Axis Powers - Liechtenstein

Kamis, 14 Mei 2015

quick sort


public class QuicksortMedianExample {

    private static int[] a;

    public static void main(String[] args) {
        // Get a random generated array
        a = getArray();

        // prints the given array
        printArray();

        sort();

        System.out.println("");

        //prints the sorted array
        printArray();

    }

    // This method sorts an array and internally calls quickSort
    public static void sort() {
        int left = 0;
        int right = a.length - 1;

        quickSort(left, right);
    }

    // This method is used to sort the array using quicksort algorithm.
    // It takes left and the right end of the array as two cursors
    private static void quickSort(int left, int right) {
        // If both cursor scanned the complete array, quicksort exits
        if (left >= right) {
            return;
        }
        // Pivot using median of 3 approach
       
        int pivot = getMedian(left, right);
       
        int partition = partition(left, right, pivot);
       
       

        // Recursively, calls the quicksort with the different left and right parameters of the sub-array

        quickSort(0, partition - 1);
       
        quickSort(partition + 1, right);
       
    }
    // This method is used to partition the given array and returns the integer which points to the sorted pivot index
    private static int partition(int left, int right, int pivot) {
        int leftCursor = left - 1;
        int rightCursor = right;
        while (leftCursor < rightCursor) {
        while (a[++leftCursor] < pivot);
        while (rightCursor > 0 && a[--rightCursor] > pivot);
            if (leftCursor >= rightCursor) {
                break;
            } else {
                swap(leftCursor, rightCursor);
            }
        }

        swap(leftCursor, right);
        return leftCursor;
 
    }
    public static int getMedian(int left, int right) {
        int center = (left + right) / 2;
        if (a[left] > a[center]) {
        }
        swap(left, center);
        if (a[left] > a[right]) {
           
        }
        swap(left, right);
        if (a[center] > a[right]) {
           
        }
        swap(center, right);
        swap(center, right);
        return a[right];
    }
    // This method is used to swap the values between the two given index
    public static void swap(int left, int right) {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
       
    }

    public static void printArray() {
     
        for (int i : a) {
     
            System.out.print(i + " ");
         
        }
     
    }

    public static int[] getArray() {
        int size = 10;
        int[] array = new int[size];
        int item = 0;
        for (int i = 0; i < size; i++) {
            item = (int) (Math.random() * 100);
            array[i] = item;
        }
        return array;
    }
}

Tidak ada komentar:

Posting Komentar