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

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]