Quicksort with Java. This article describes how to implement Quicksort with Java.

## 1. Quicksort

### 1.1. Overview

Sort algorithms order the elements of an array according to a predefined order. Quicksort is a divide and conquer algorithm. In a divide and conquer sorting algorithm the original data is separated into two parts "divide" which are individually sorted and "conquered" and then combined.

### 1.2. Description of the algorithm

If the array contains only one element or zero elements then the array is sorted.

If the array contains more than one element then:

• Select an element from the array. This element is called the "pivot element". For example select the element in the middle of the array.

• All elements which are smaller than the pivot element are placed in one array and all elements which are larger are placed in another array.

• Sort both arrays by recursively applying Quicksort to them.

• Combine the arrays.

Quicksort can be implemented to sort "in-place". This means that the sorting takes place in the array and that no additional array needs to be created.

## 2. Quicksort in Java

### 2.1. Implementation

Create a Java project "de.vogella.algorithms.sort.quicksort" and create the following class.

``````package de.vogella.algorithms.sort.quicksort;

public class Quicksort  {
private int[] numbers;
private int number;

public void sort(int[] values) {
// check for empty or null array
if (values ==null || values.length==0){
return;
}
this.numbers = values;
number = values.length;
quicksort(0, number - 1);
}

private void quicksort(int low, int high) {
int i = low, j = high;
// Get the pivot element from the middle of the list
int pivot = numbers[low + (high-low)/2];

// Divide into two lists
while (i <= j) {
// If the current value from the left list is smaller than the pivot
// element then get the next element from the left list
while (numbers[i] < pivot) {
i++;
}
// If the current value from the right list is larger than the pivot
// element then get the next element from the right list
while (numbers[j] > pivot) {
j--;
}

// If we have found a value in the left list which is larger than
// the pivot element and if we have found a value in the right list
// which is smaller than the pivot element then we exchange the
// values.
// As we are done we can increase i and j
if (i <= j) {
exchange(i, j);
i++;
j--;
}
}
// Recursion
if (low < j)
quicksort(low, j);
if (i < high)
quicksort(i, high);
}

private void exchange(int i, int j) {
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
}``````

### 2.2. Test

You can use the following JUnit tests to validate the sort method. To learn about JUnit please see JUnit Tutorial.

``````package de.vogella.algorithms.sort.quicksort;

import java.util.Arrays;
import java.util.Random;

import org.junit.Before;
import org.junit.Test;

import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

public class QuicksortTest {

private int[] numbers;
private final static int SIZE = 7;
private final static int MAX = 20;

@Before
public void setUp() throws Exception {
numbers = new int[SIZE];
Random generator = new Random();
for (int i = 0; i < numbers.length; i++) {
numbers[i] = generator.nextInt(MAX);
}
}

@Test
public void testNull() {
Quicksort sorter = new Quicksort();
sorter.sort(null);
}

@Test
public void testEmpty() {
Quicksort sorter = new Quicksort();
sorter.sort(new int);
}

@Test
public void testSimpleElement() {
Quicksort sorter = new Quicksort();
int[] test = new int;
test = 5;
sorter.sort(test);
}

@Test
public void testSpecial() {
Quicksort sorter = new Quicksort();
int[] test = { 5, 5, 6, 6, 4, 4, 5, 5, 4, 4, 6, 6, 5, 5 };
sorter.sort(test);
if (!validate(test)) {
fail("Should not happen");
}
printResult(test);
}

@Test
public void testQuickSort() {
for (Integer i : numbers) {
System.out.println(i + " ");
}
long startTime = System.currentTimeMillis();

Quicksort sorter = new Quicksort();
sorter.sort(numbers);

long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Quicksort " + elapsedTime);

if (!validate(numbers)) {
fail("Should not happen");
}
assertTrue(true);
}

@Test
public void testStandardSort() {
long startTime = System.currentTimeMillis();
Arrays.sort(numbers);
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("Standard Java sort " + elapsedTime);
if (!validate(numbers)) {
fail("Should not happen");
}
assertTrue(true);
}

private boolean validate(int[] numbers) {
for (int i = 0; i < numbers.length - 1; i++) {
if (numbers[i] > numbers[i + 1]) {
return false;
}
}
return true;
}

private void printResult(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
System.out.print(numbers[i]);
}
System.out.println();
}
}``````

## 3. Complexity Analysis

The following describes the runtime complexity of quicksort.

Quicksort is a fast, recursive, non-stable sort algorithm which works by the divide and conquer principle. Quicksort will in the best case divide the array into almost two identical parts. It the array contains n elements then the first run will need O(n). Sorting the remaining two sub-arrays takes 2* O(n/2). This ends up in a performance of O(n log n).

In the worst case quicksort selects only one element in each iteration. So it is O(n) + O(n-1) + (On-2).. O(1) which is equal to O(n^2).

The average case of quicksort is O(n log n). 