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]
Scroll to Top