- 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 |
---|---|---|
1 | Best case | O(n log n) |
2 | Average case | O(n log n) |
3 | Worst 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 ] |