Site icon

Sort integer array in java using quicksort algorithm (example)

1. What is quicksort algorithm in java?

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]
Exit mobile version