Thursday, April 7, 2016

Sorting: Quick Sort

Quick sort is a divide and conquer approach to sorting just like Merge sort, however this method is more efficient but it does take up more memory space.
The method divides a list of integers, picks an integer of an array to be a pivot, then moves the integers that are larger in value and moves it to the right of the pivot, and then does that to the smaller ones.

Quick Sort
public class MyQuickSort {
    private int array[];
    private int length;
    public void sort(int[] inputArr) {
        if (inputArr == null || inputArr.length == 0) {
        this.array = inputArr;
        length = inputArr.length;
        quickSort(0, length - 1);
    private void quickSort(int lowerIndex, int higherIndex) {
        int i = lowerIndex;
        int j = higherIndex;
        // calculate pivot number, I am taking pivot as middle index number
        int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
        // Divide into two arrays
        while (i <= j) {
             * In each iteration, we will identify a number from left side which
             * is greater then the pivot value, and also we will identify a number
             * from right side which is less then the pivot value. Once the search
             * is done, then we exchange both numbers.
            while (array[i] < pivot) {
            while (array[j] > pivot) {
            if (i <= j) {
                exchangeNumbers(i, j);
                //move index to next position on both sides
        // call quickSort() method recursively
        if (lowerIndex < j)
            quickSort(lowerIndex, j);
        if (i < higherIndex)
            quickSort(i, higherIndex);
    private void exchangeNumbers(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    public static void main(String a[]){
        MyQuickSort sorter = new MyQuickSort();
        int[] input = {24,2,45,20,56,75,2,56,99,53,12};
        for(int i:input){
            System.out.print(" ");

1 comment:

  1. Thanks man for the information, I understand so much more about programming from reading your blog.