Merge Sort, Quick Sort and finding Kth largest element in an unsorted array

Let’s begin with Merge Sort.

Running Time :

Average Case : O(n log n)

Worst Case : O(n log n)

Here is the implementation in java:

package com.pract.sorting;

public class MergeSort {

    private int[] array;
    private int[] tempMergArray;
    private int length;
    private int countInversion = 0;
    
    
    public static void main(String[] args) {
        int inputArray[] = {45, 23, 11, 15, 8};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(inputArray);
        for(int i:inputArray){
            System.out.print(i);
            System.out.print(" ");
        }
        System.out.println("\n" + mergeSort.countInversion);
    }
   
    
    private void sort(int inputArray[]){
        this.array = inputArray;
        this.length = inputArray.length;
        this.tempMergArray = new int[length];
        doMergeSort(0, length - 1 );
    }
    
    private void doMergeSort(int lowerIndex, int higherIndex){
        if(lowerIndex < higherIndex){
            int middle = lowerIndex + (higherIndex - lowerIndex)/2;
            //below step sort the left hand side
            doMergeSort(lowerIndex, middle);
            //below step sort the right hand side
            doMergeSort(middle + 1, higherIndex);
            // now merge both sides
            mergeParts(lowerIndex, middle, higherIndex);
        }
        
        
    }
    
    private void mergeParts(int lowerIndex, int middle, int higherIndex){
        // Copy both parts into the helper array
        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArray[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        // Copy the smallest values from either the left or the right side back
        // to the original array
        while (i <= middle && j <= higherIndex) {
            if (tempMergArray[i] <= tempMergArray[j]) {
                array[k] = tempMergArray[i];
                i++;
            } else {
                array[k] = tempMergArray[j];
                j++;
            }
            k++;
        }
     // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            array[k] = tempMergArray[i];
            k++;
            i++;
        }
        
        
    }
    
}

 

Now lets check quick sort:

Running time:

Average case : O(n log n)

Worst Case : O(n2)

Here is the implementation in java:

package com.pract.sorting;

public class QuickSort {

    private static int[] initialArray = {2, 8, 7, 1, 3, 5, 6, 4};
    
    
    
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        quickSort.quickSort(initialArray, 0, initialArray.length - 1);
        
        for(int i = 0; i < initialArray.length; i++)
            System.out.println(initialArray[i]);
    }
    
    //partition method partitions the array around pivot element. Here r location denotes the pivot element location.
    // i denotes the index upto which all elements will remain less than pivot. 
    private int partition(int[] array, int p, int r){
        int x = array[r];
        int i = p - 1 ;
        
        for(int j = p; j <= r-1; j++){
            if(array[j] <= x){
                i++;
                exchange(array, i, j);
            }
        }
        exchange(array, i + 1, r);
        return i + 1;
    }
    
    private void quickSort(int[] array, int p, int r){
        if(p < r){
            int q = partition(array, p, r);
            quickSort(array, p, q - 1); 
            quickSort(array, q + 1, r);
        }
        
    }
    private void exchange(int[] array, int i, int j){
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
    
    
}

Now lets solve finding kth max element in an unsorted array with the help of quick sort:

In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n2), but it works in O(n) on average.

Here is the implementation in java:

package com.pract.sorting;

public class RandomizedSelection {

    private static int[] array = { 5,7,6,4,9 };
//    private static int orderStatistics = 5;


    public static void main(String[] args) {
        int x = doRandomized(array, 0, array.length - 1, 2);
        System.out.println(x);
    }


    private static int doRandomized(int[] array, int l, int r, int k) {
        if (r == 1)
            return array[r];
        if (k > 0 && k <= r - l + 1) {
            int pos = doPartition(array, l, r);
            if (pos-l == k-1)
                return array[pos];
            else if (pos-l > k-1)  
                return doRandomized(array, l, pos - 1, k);
            else 
                return doRandomized(array, pos + 1, r, k-pos+l-1);
            
        }
        return -1;
    }


    private static int doPartition(int[] array, int p, int r) {
        int pivot = array[r];
        int i = p - 1;

        for (int j = p; j <= r - 1; j++) {
            if (array[j] <= pivot) {
                i++;
                exchange(array, i, j);
            }
        }
        exchange(array, i + 1, r);
        return i + 1;
    }


    private static void exchange(int[] array, int i, int j) {
        int temp = array[j];
        array[j] = array[i];
        array[i] = temp;
    }
}

Leave a Reply