NOW Hiring

Quick links

Share

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 than the array is sorted.

If the array contains more than one element than:

  • 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 then 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 then 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 then the pivot
                        // element then get the next element from the right list
                        while (numbers[j] > pivot) {
                                j--;
                        }

                        // If we have found a values in the left list which is larger then
                        // the pivot element and if we have found a value in the right list
                        // which is smaller then 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[0]);
        }

        @Test
        public void testSimpleElement() {
                Quicksort sorter = new Quicksort();
                int[] test = new int[1];
                test[0] = 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).

4. About this website

5. Links and Literature

5.1. Source Code

Not listed yet.

5.3. vogella GmbH training and consulting support

TRAINING SERVICE & SUPPORT

The vogella company provides comprehensive training and education services from experts in the areas of Eclipse RCP, Android, Git, Java, Gradle and Spring. We offer both public and inhouse training. Whichever course you decide to take, you are guaranteed to experience what many before you refer to as “The best IT class I have ever attended”.

The vogella company offers expert consulting services, development support and coaching. Our customers range from Fortune 100 corporations to individual developers.

Copyright © 2012-2016 vogella GmbH. Free use of the software examples is granted under the terms of the EPL License. This tutorial is published under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Germany license.

See Licence.