# Quick Sort #### Overview

Quick Sort is a very popular divide and conquer algorithm used for sorting collections. It works by selecting a pivot element and partition the array such that all the elements to the left of pivot are smaller that the pivot element. Quick Sort is preferred over Merge Sort as both algorithms have same run time complexity but Quick sort uses less space

#### Pseudo Code

• Pick a pivot (usually the last element of the array) and partition the array
• Left of the pivot should be all the elements smaller than the pivot
• Right of the pivot should be all the elements larger than the pivot
• After step 1 the pivot is at the correct position in the array and will not move
• Repeat step 1 with the left and right of partitioned array until the entire array is sorted

#### Implementation

``````public class QuickSortBlog {
public static void main(String[] args) {
int[] sampleArray = { 423, 99, 1, 5, 2, 7, 8, 9, 11, 3, 5 };

quickSort(sampleArray, 0, sampleArray.length - 1);
System.out.println(Arrays.toString(sampleArray));
//output: [1, 2, 3, 5, 5, 7, 8, 9, 11, 99, 423]
}

//Quick Sort algorithm - recursive
private static void quickSort(int[] array, int start, int end) {
//base condition for recursion to end
if(start >= end)
return;

//partition the array such that all the elements to the left of pivot are smaller than the pivot
var boundary = partition(array, start, end);

//repeat sorting for the partitioned arrays
quickSort(array, boundary + 1, end);
quickSort(array, start, boundary - 1);
}

public static int partition(int[] array, int start, int end) {
int pivot = array[end];
int boundary = start - 1;

for (int i = start; i <= end; i++) {
if (array[i] <= pivot) {
var temp = array[i];
array[i] = array[++boundary];
array[boundary] = temp;
}
}

return boundary;
}
}``````

#### Time Complexity

• Best/average case – O(n log n)
• Worst case O(n2)