Showing posts with label divide and conquer. Show all posts
Showing posts with label divide and conquer. Show all posts

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();
    }
}

Merge Sort in Java

public class MergeSort {

    public int A[], temp[]; //, size=0;

    MergeSort(int n) {
        A = new int[n];
        temp = new int[n];
        //size = n;
    }

    MergeSort() {
        A = null;
        temp = null;
        //size = 0;
    }

    public void mergeSort(int A[], int left, int right) {
        int mid;
        //System.out.println("A-len: " + this.A.length + " Temp-len: " + this.temp.length);
        if (left < right) {
            mid = (right + left) / 2;
            mergeSort(A, left, mid);
            mergeSort(A, mid + 1, right);
            merge(A, left, mid, right);
        }
    }

    public void merge(int A[], int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;
        int L1[] = new int[n1];
        int L2[] = new int[n2];
     
        for (int i = 0; i < n1; i++) {
            L1[i] = A[left + i];
        }

        for (int i = 0; i < n2; i++) {
            L2[i] = A[mid + i + 1];
        }

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (L1[i] <= L2[j]) {
                A[k] = L1[i];
                i++;
            } else {
                A[k] = L2[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            A[k] = L1[i];
            i++;
            k++;
        }

        while (j < n2) {
            A[k] = L2[j];
            j++;
            k++;
        }

    }

    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 static void main(String args[]) {
        MergeSort sort = new MergeSort();
        sort.A = new int[]{2, 4, 5, 7, 1, 2, 3, 6};
        sort.temp = new int[8];
        sort.mergeSort(sort.A, 0, 7);
        // print sorted Array
        sort.printArr();
    }
}