/*
This is an implementation of the quick sort algorithm.
Let n be the size of the list to sort
Best: O(nlog2(n)) time | O(log2(n)) space
Average: O(nlog2(n)) time | O(log2(n)) space
Worst: O(n^2) time | O(log2(n)) space
*/
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = { 1, 10, 5, 3, 6 };
quickSort(arr);
// Below prints: [1, 3, 5, 6, 10]
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] array) {
// Sort array recursively
quickSortUtil(array, 0, array.length - 1);
}
private static void quickSortUtil(int[] array, int startIdx, int endIdx) {
// Base case: at this point array is sorted
if (startIdx >= endIdx) {
return;
}
// Let first value be pivot
// Sort every other number wrt to pivot
int pivotIdx = startIdx;
int leftIdx = startIdx + 1;
int rightIdx = endIdx;
// Make sure that element at leftIdx <= to one at pivotIdx
// and element at rightIdx is >= to one at pivotIdx
while (leftIdx <= rightIdx) {
if (array[leftIdx] > array[pivotIdx] && array[rightIdx] < array[pivotIdx]) {
swap(leftIdx, rightIdx, array);
}
if (array[leftIdx] <= array[pivotIdx]) {
leftIdx++;
}
if (array[rightIdx] >= array[pivotIdx]) {
rightIdx--;
}
}
swap(pivotIdx, rightIdx, array);
// At the end of current iteration, element at
// pivot is in its final sorted position
quickSortUtil(array, startIdx, rightIdx - 1);
quickSortUtil(array, rightIdx + 1, endIdx);
}
private static void swap(int i, int j, int[] array) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Java implementation of QuickSort
import java.io.*;
class GFG{
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
static int partition(int[] arr, int low, int high)
{
// pivot
int pivot = arr[high];
// Index of smaller element and
// indicates the right position
// of pivot found so far
int i = (low - 1);
for(int j = low; j <= high - 1; j++)
{
// If current element is smaller
// than the pivot
if (arr[j] < pivot)
{
// Increment index of
// smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index
*/
static void quickSort(int[] arr, int low, int high)
{
if (low < high)
{
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print an array
static void printArray(int[] arr, int size)
{
for(int i = 0; i < size; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("Sorted array: ");
printArray(arr, n);
}
}
// This code is contributed by Ayush Choudhary
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
// Index of smaller element and
// indicates the right position
// of pivot found so far
int i = (low - 1);
for(int j = low; j <= high - 1; j++) {
// If current element is smaller
// than the pivot
if (arr[j] < pivot) {
// Increment index of
// smaller element
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return (i + 1);
}
static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p]
// is now at right place
int pi = partition(arr, low, high);
// Separately sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}