Quick Sort Algorithm
Quick sort (sometimes called partition-exchange sort) is an efficient sorting algorithm.
It is a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort.
Quick sort is a divide and conquer algorithm. Quick sort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quick sort can then recursively sort the sub-arrays.
The steps are as below.
(1) Pick an element, called a pivot, from the array.
(2) Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
(3) Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
There are many versions of this algorithm to select pivot, Here we are taking middle of the list as pivot element.
Performance
- Worst-case performance :- O(n2)
- Best-case performance :- O(n log n) (simple partition) or O(n) (three-way partition and equal keys)
- Average performance :- O(n log n)
- Worst-case space complexity :- O(n) auxiliary (naive), O(log n) auxiliary
Java Program of Quick Sort Algorithm
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
package com.codenuclear; public class QuickSort { private int[] array; private int length; public void sort(int[] inputArray) { // check for empty or null array if (inputArray == null || inputArray.length==0){ return; } this.array = inputArray; length = inputArray.length; quickSort(0, length - 1); } private void quickSort(int low, int high) { int i = low, j = high; // select the pivot element. Here we are taking middle of the list as pivot element. int pivot = array[low + (high-low)/2]; // Divide into two lists while (i <= j) { // If the current value from the left list is smaller than the pivot element then get the next element from the left list while (array[i] < pivot) { i++; } // If the current value from the right list is larger than the pivot element then get the next element from the right list while (array[j] > pivot) { j--; } // If we have found a value in the left list which is larger than the pivot element // and/or if we have found a value in the right list which is smaller than the pivot element // then we will exchange the values // We can now increase i and j if (i <= j) { exchangeElements(i, j); i++; j--; } } // Recursion if (low < j) quickSort(low, j); if (i < high) quickSort(i, high); } private void exchangeElements(int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } /* Printing sorted array */ void printArray(int inputArr[]) { int n = inputArr.length; for (int i = 0; i < n; ++i) System.out.print(inputArr[i] + " "); System.out.println(); } public static void main(String args[]) { QuickSort obj = new QuickSort(); int inputArr[] = { 25,10,30,15,20,10,5 }; System.out.println("Input Array before Quick Sort."); obj.printArray(inputArr); obj.sort(inputArr); System.out.println("\nSorted Array after Quick Sort."); obj.printArray(inputArr); } } |
Output
Some theory part of this article uses material from the Wikipedia article “Quick Sort”, which is released under the CC BY-SA 3.0.
Well, I’m Having A Doubt, As To Why At Line 46 And 48 If Conditions Have Been Specified
Great Explaination Though
Glad to know that you like the article.
Those if conditions are to decide which value to be passes in next recursive call…
Beauty of recursion…
Happy learning 🙂