Quicksort is a divide-and-conquer algorithm which centers around efficiently choosing the pivot value from the input data set. Based on this pivot value, list is divided into two sub lists - first sub list containing all values less than or equal to the pivot and second sub list containing all values greater than the pivot. This procedure is recursively called on these two sub lists.

Wikipedia has an interesting animation.

Below algorithm sorts array

**in-place**and without using any extra space ( except the temporary holder, tmp). Algorithm selects

**first element of the array as pivot value**, but you can chose any value as pivot.

### Java Implementation

package algo; /** * QuickSort implemention * * @author Siddheshwar * */ public class QuickSort { /** * This method actually partitions the array in two sub parts. Doing * recursively the same, sorts the array as well * */ static int[] partition(int[] a, int low, int high) { int pi = low; int pivot = a[pi]; int i = low, j = high; while (i < j) { // i should not exceed the high bound while (a[i] <= pivot && i < high) i++; // j should not reduce below low bound while (a[j] > pivot && j >= i) j--; if (i < j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } // j is the final position for pivot element int tmp = a[j]; a[j] = pivot; a[pi] = tmp; pi = j; // just for testing logging(a, pi); // do the same for lower and higher sub arrays if (low < pi - 1) { partition(a, low, pi - 1); } if (pi + 1 < high) { partition(a, pi + 1, high); } return a; } /** * Print array after each iteration to see how this sort works * */ public static void logging(int[] a, int pi) { for (int t : a) { System.out.print(t + " "); } System.out.println("\nPivot index :" + pi + "; Pivot :" + a[pi]); } public static void main(String[] args) { // int[] a = {0,666,1, 10, 30, 5, 19, 10}; // int[] a = {1,1,1,1,1,1,1}; // int[] a = {1,2,1,2,1,2,1}; int[] a = { 0, 666, 2, 2, 2, 2, 45, 2, 3, 3, 3, 3 }; a = QuickSort.partition(a, 0, a.length - 1); System.out.println("\nsorted array"); for (int t : a) { System.out.print(t + " "); } } }

**Output:**

*0 666 2 2 2 2 45 2 3 3 3 3*

Pivot index :0; Pivot :0

0 3 2 2 2 2 45 2 3 3 3 666

Pivot index :11; Pivot :666

0 3 2 2 2 2 3 2 3 3 45 666

Pivot index :9; Pivot :3

0 3 2 2 2 2 3 2 3 3 45 666

Pivot index :8; Pivot :3

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :7; Pivot :3

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :5; Pivot :2

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :4; Pivot :2

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :3; Pivot :2

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :2; Pivot :2

sorted array

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :0; Pivot :0

0 3 2 2 2 2 45 2 3 3 3 666

Pivot index :11; Pivot :666

0 3 2 2 2 2 3 2 3 3 45 666

Pivot index :9; Pivot :3

0 3 2 2 2 2 3 2 3 3 45 666

Pivot index :8; Pivot :3

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :7; Pivot :3

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :5; Pivot :2

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :4; Pivot :2

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :3; Pivot :2

0 2 2 2 2 2 3 3 3 3 45 666

Pivot index :2; Pivot :2

sorted array

0 2 2 2 2 2 3 3 3 3 45 666

### Important points

- Performance of algorithm depends a lot on the choice of pivot value. If it divides the array in two almost equal sized array, run time complexity will be O(n log n). Worst case complexity for Quicksort is O(n^2).
- It also takes O(log n) stack space on an average.
- You can also consider using stack to eliminate recursion.
- On small array , Insertion Sort is faster than Quick sort. So you can consider using Insertion sort if the size of the array is small.

## No comments:

## Post a Comment