Sunday, December 22, 2013

Quick Sort (in java)

public class QuickSort {

    public int A[] = null;

    public int partition(int A[], int low, int high) {
        int left, right, pivot_item = A[low];
        left = low;
        right = high;

        while (left < right) {
       
            while (left < right && A[left] <= pivot_item) {
                left++;
            }
            while (A[right] > pivot_item) {
                right--;
            }

            if (left < right) {
                int temp = A[right];
                A[right] = A[left];
                A[left] = temp;
            }
        }
     
        A[low] = A[right];
        A[right] = pivot_item;
        return right;
    }

    public void printArr() {
        System.out.print("Sorted: ");
        for (int i = 0; i < this.A.length; i++) {
            System.out.print(this.A[i] + ", ");
        }
        System.out.println();
    }

    public void quickSort(int A[], int low, int high) {
        int pivot;
        if (high > low) {
            pivot = partition(A, low, high);
           // System.out.println("Pivot: " + pivot);
            quickSort(A, low, pivot - 1);
            quickSort(A, pivot + 1, high);
        }
       // this.printArr();
    }

    public static void main(String args[]) {
        QuickSort sort = new QuickSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.quickSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}

No comments:

Post a Comment