Quick Sort in Java
Like merge sort, quick sort also uses the divide and conquer approach to sort the given array or list. In quick sort, the sorting of an array is achieved by taking an element from the input array as the pivot and then split the array using the pivot.
Algorithm
STEP 1: Take either the first or the last element as the pivot element.
STEP 2: Find and place the pivot element at its correct position, i.e., the elements that are on the left side of the pivot element must be less than the pivot element. Also, elements that are on the right side of the pivot element must be greater than the pivot element.
STEP 3: Recursively execute steps 1 and 2 till the whole array is sorted.
Pseudo Code
// start → Beginning index, end → Last index
quickSort(arr[], start, end)
{
if(start >= end) return; // base case
else
{
// The partition() method positions the pivot
// at the right place, i.e., left side of pivot contains
// elements that are less than pivot and right side of
// pivot contains elements that are greater than pivot
pivot = partition(arr, start, end);
// Invoking the method quickSort() for the left side of pivot
quickSort(arr, start, pivot — 1);
// Invoking the method quickSort() for the right side of pivot
quickSort(arr, pivot + 1, end);
}
}
