Quicksort is an efficient comparison sort algorithm. It can operate in place on the array, requiring small additional amounts of memory to perform sorting.
Quicksort can be faster than merge sort and heap sort. Quicksort is one of the divides and conquers strategy algorithm. It requires careful selection of pivot element. Even if the array nearly sorted or sorted the quicksort takes the same complexity. If the array nearly sorted, we can choose insertion sort for better complexity.
Write a program to implement the quick sort.
source Code
package com.dsacode.Algorithm.sorting; import java.util.Arrays; public class Quicksort { private int[] numbers; public Quicksort(int[] values) { if (values ==null ){ return; } this.numbers = values; } public void quicksort(int low, int high) { int l = low, h = high; int pivot = numbers[low + (high-low)/2]; while (l <= h) { while (numbers[l] < pivot) { l++; } while (numbers[h] > pivot) { h--; } if (l <= h) { exchange(l, h); l++; h--; } } if (low < h) quicksort(low, h); if (l < high) quicksort(l, high); } private void exchange(int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } public static void main(String[] args) { int[] arr={12,34,56,23,45,78,46}; System.out.println("unsorted array before sorting : " + Arrays.toString(arr)); Quicksort q = new Quicksort(arr); q.quicksort(0, arr.length - 1); System.out.println("Sorted array After Quicksort sorting : " + Arrays.toString(arr)); } }
Output
Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 46] Sorted array After Quicksort sorting: [12, 23, 34, 45, 46, 56, 78]
Algorithm Explanation
![]() | Choose a pivot value from the array. |
![]() | Partition the array based on pivot element. Arrange all the elements less than pivot element to the left side and greater elements to the right side of the pivot element. |
![]() | Sort the left and right subarrays recursively. |
![]() | Merge the two solution subarrays. |
Algorithm Explanation
![]() | Choose a pivot value from the array. |
![]() | Partition the array based on pivot element. Arrange all the elements less than pivot element to the left side and greater elements to the right side of the pivot element. |
![]() | Sort the left and right subarrays recursively. |
![]() | Merge the two solution subarrays. |
Time Complexity
Best Case | Average Case | Worst Case |
---|---|---|
O(n log n) | O(n log n) | O(n2) |