Quick Sort in java

Quicksort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm.
In quick sort, we first choose a pivot and divide into two sublists,one will contain elements lower than pivot and other will have elements greater than pivot.

Quick sort algorithm:

Lets say array is arr[]
  • Choose a pivot, it is generally mid element of the list.
  • Initialise two index variable , left=0 and right=arr.length-1
  • Increment left variable until you get element higher than pivot. 
  • Decrement right variable until you get element lesser than pivot
  • swap arr[left] and arr[right] 
  • Recursively sort sublists(sublist with less than pivot, sublist greater than pivot) using above algorithm.
  • In the end , you will get sorted array.

Java program to implement quick sort:

package org.arpit.java2blog;

import java.util.Arrays;

public class QuickSortMain {
     
    private static int array[];

    public static void sort(int[] arr) {
         
        if (arr == null || arr.length == 0) {
            return;
        }
        array = arr;
        quickSort(0, array.length-1);
    }
 
    private static void  quickSort(int left, int right) {
         
        int i = left;
        int j = right;
        // find pivot number, we will take it as mid
        int pivot = array[left+(right-left)/2];
    
        while (i <= j) {
            /**
             * In each iteration, we will increment left until we find element greater than pivot
             * We will decrement right until we find element less than pivot
             */
            while (array[i] < pivot) {
                i++;
            }
            while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
             exchange(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (left < j)
            quickSort(left, j);
        if (i < right)
            quickSort(i, right);
    }
 
    private static void exchange(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
     
    public static void main(String a[]){
        int[] input = {33,21,45,64,55,34,11,8,3,5,1};
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(input));
        sort(input);
        System.out.println("==================");
        System.out.println("After Sorting : ");
        System.out.println(Arrays.toString(array));
        
    }
}
Before Sorting : 
[33, 21, 45, 64, 55, 34, 11, 8, 3, 5, 1]
==================
After Sorting : 
[1, 3, 5, 8, 11, 21, 33, 34, 45, 55, 64]
Time complexity : 
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012