Sort integer array in java using quicksort algorithm (example)

  • Given unsorted integer array in java.
  • We would like to sort integer array using quick sort algorithm in java.

1. What is quicksort algorithm in java?

  • Quicksort (or partition-exchange sort) is commonly used and efficient sorting algorithm.
  • The properties of quicksort algorithms are:
    • Quicksort is divide and conquer algorithm.
    • Quicksort is not stable algorithm,.
      • The relative order of equal keys may changed during sorting.
    • Quicksort in-place sort algorithm.

2. Performance analysis of quick sort algorithm

S. No.Cases  Complexity
1Best case O(n log n)
2Average case O(n log n)
3Worst case O(n^2)

3. Program – sort an array using quick sort algorithm

package org.learn.arrays;
 
import java.util.Arrays;
 
public class QuickSort {
 
    public static void main(String[] args) {
        int[] example1 = { 10, 7, 25, 25, 20, 12, 9 };
        System.out.println("Unsorted array is : " + Arrays.toString(example1));
        quickSort(example1, 0, example1.length - 1);
        System.out.println("Sorted Array is   : " + Arrays.toString(example1));
 
        int[] example2 = { 5, 4, 3, 2, 1, 0 };
        System.out.println("\nUnsorted array is : " + Arrays.toString(example2));
        quickSort(example2, 0, example2.length - 1);
        System.out.println("Sorted Array is   : " + Arrays.toString(example2));
    }
 
    private static void quickSort(int[] inputArray, int low, int high) {
         
        int iLowerIndex = low;
        int iHighIndex = high;
         
        // Take middle as pivot element.
        int middle = low + (high - low) / 2;
        int pivotElement = inputArray[middle];
 
        while (iLowerIndex <= iHighIndex) {
 
            // Keep scanning lower half till value is less than pivot element
            while (inputArray[iLowerIndex] < pivotElement) {
                iLowerIndex++;
            }
             
            // Keep scanning upper half till value is greater than pivot element
            while (inputArray[iHighIndex] > pivotElement) {
                iHighIndex--;
            }
 
            //swap element if they are out of place
            if (iLowerIndex <= iHighIndex) {
                swap(inputArray, iLowerIndex, iHighIndex);
                iLowerIndex++;
                iHighIndex--;
            }
        }
 
        // Sort lower half -- low to iHighIndex
        if (low < iHighIndex) {
            quickSort(inputArray, low, iHighIndex);
        }
 
        // Sort upper half -- iLowerIndex to high
        if (iLowerIndex < high) {
            quickSort(inputArray, iLowerIndex, high);
        }
    }
 
    //swap elements
    private static void swap(int[] arr, int iElement1, int iElement2) {
        int temp = arr[iElement1];
        arr[iElement1] = arr[iElement2];
        arr[iElement2] = temp;
    }
}

4. Output – quick sort algorithm in java

Unsorted array is : [10, 7, 25, 20, 12, 9]
Sorted Array is   : [7, 9, 10, 12, 20, 25]
 
Unsorted array is : [5, 4, 3, 2, 1, 0]
Sorted Array is   : [0, 1, 2, 3, 4, 5]