# Quick Sort Algorithm in Java This article gives provides an overview on Quick Sort together with an implementation in Java.

Quick Sort, also known as partition-exchange sort, is an efficient divide and conquer sorting algorithm. The algorithm can be implemented making use of loops or recursions. The algorithm performs the sorting in-place. Quick Sort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation is defined.

The algorithm divides the array into two smaller sub-arrays. To divide the algorithm into two array, an pivot or element within the array is chosen. The partition phase consist of reordering 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. After the partition phase, the pivot is in its final position. The pivot logically splits the original array into two sub-arrays. The Quick Sort algorithm then recursively sort the sub-arrays by selecting a new pivot and move the values accordingly. Every element will be selected as the pivot and will be placed in the correct position.

## Algorithm Classification

The following table contains information about the analysis of the Quick Sort algorithm. It defines the worst, average and best cases in terms of time complexity and also the worst case in space complexity.

AttributeValue
ClassSorting Algorithm
ClassificationInternal, In-place, Unstable Algorithm
Data StructureArray
Time Complexity: BestΩ(n log(n))
Time Complexity: AverageΘ(n log(n))
Time Complexity: WorstO(n2)
Space Complexity: WorstO(n log(n))

Algorithm Classification: Quick Sort

Please use the following link for an explanation on Big-O notation and what is good, fair and bad.

## Quick Sort In Java

The QuickSort class implements the Quick Sort algorithm for sorting an array of integers.

public final class QuickSort {

public void sort(int[] collection) {
if (collection != null) {
quickSort(collection, 0, collection.length-1);
} else {
throw new IllegalArgumentException("Input paramenter for array to sort is null.");
}
}

private void quickSort(int[] collection, int firstPosition, int lastPosition) {
if (firstPosition >= lastPosition) {
return;
} else {
int pivotIndex = partition(collection, firstPosition, lastPosition);
quickSort(collection, firstPosition, pivotIndex-1);
quickSort(collection, pivotIndex+1, lastPosition);
}
}

private int partition(int[] collection, int firstPosition, int lastPosition) {
int pivotIndex = selectPivot(firstPosition, lastPosition);
swap (collection, pivotIndex, lastPosition);
int store = firstPosition;
pivotIndex = lastPosition;
for (int i = firstPosition; i <= lastPosition-1 ; i++) {
if (collection[i] <= collection[pivotIndex]) {
swap (collection, i, store);
store++;
}
}
swap (collection, store, pivotIndex);
pivotIndex = store;
return pivotIndex;
}

private void swap(int[] collection, int x, int y) {
int temp = collection[x];
collection[x] = collection[y];
collection[y] = temp;
}

private int selectPivot(int first, int last) {
return (first+last)/2;
}

}