- 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]