Algorithm - Quick Sort

Quick Sort
Quicksort  is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than merge sort and heapsort.

Solution
public class QuickSort {

    static void sort(int[] inputArr) {
         
        if (inputArr == null || inputArr.length == 0) {
            return;
        }
        doQuickSort(inputArr,0, inputArr.length - 1);
    }

    static void doQuickSort(int[] array, int lowerIndex, int higherIndex) {
         
        int i = lowerIndex;
        int j = higherIndex;
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        while (i <= j) {
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchangeNumbers(array,i, j);
                i++;
                j--;
            }
        }
        if (lowerIndex < j)
            doQuickSort(array,lowerIndex, j);
        if (i < higherIndex)
            doQuickSort(array, i, higherIndex);
    }

    static void exchangeNumbers(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
     
    public static void main(String a[]){
        int[] input = {47, -5, 84, -3, 2, 32, 27, 5, 2};
        sort(input);
        for (int i = 0; i < input.length; i++) {
            if (i > 0) {
                System.out.print(", ");
            }
            System.out.print(input[i]);
        }
    }
}

Result
-5, -3, 2, 2, 5, 27, 32, 47, 84

Comments

Popular posts from this blog

Clear the app data programmatically in android

convert an integer to a string in java

Print the large string values in android log cat.