Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this Quicksort implementation that sorts arrays of int (not Integer). It has comparable performance to Java's DualPivotQuicksort, especially when the size of the range is below one million elements or so.

IntegerQuicksort.java

package net.coderodde.util;

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

public class IntegerQuicksort {

    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(int[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        int pivot = array[fromIndex];
        int leftPartitionLength = 0;
        int rightPartitionLength = 0;
        int index = fromIndex;

        while (index < toIndex - rightPartitionLength) {
            int current = array[index];

            if (current > pivot) {
                ++rightPartitionLength;
                int tmp = array[toIndex - rightPartitionLength];
                array[toIndex - rightPartitionLength] = current;
                array[index] = tmp;
            } else if (current < pivot) {
                int tmp = array[fromIndex + leftPartitionLength];
                array[fromIndex + leftPartitionLength] = current;
                array[index] = tmp;

                ++index;
                ++leftPartitionLength;
            } else {
                ++index;
            }
        }

        sort(array, fromIndex, fromIndex + leftPartitionLength);
        sort(array, toIndex - rightPartitionLength, toIndex);
    }

    private static final int SIZE = 500_000;
    private static final int FROM = 100;
    private static final int TO = SIZE - 100;

    public static void main(final String... args) {
        long seed = System.nanoTime();
        Random random = new Random(seed);
        int[] array1 = getRandomArray(SIZE, -1000, 1000, random);
        int[] array2 = array1.clone();

        System.out.println("Seed: " + seed);
        long startTime = System.nanoTime();
        sort(array1, FROM, TO);
        long endTime = System.nanoTime();

        System.out.printf("IntegerQuicksort.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        startTime = System.nanoTime();
        Arrays.sort(array2, FROM, TO);
        endTime = System.nanoTime();

        System.out.printf("Arrays.sort in %.2f milliseconds.\n",
                          (endTime - startTime) / 1e6);

        System.out.println(Arrays.equals(array1, array2));
    }

    public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {
        int[] array = new int[size];

        for (int i = 0; i < size; ++i) {
            array[i] = random.nextInt(maximum - minimum + 1) + minimum;
        }

        return array;
    }
}

Some performance figures:

Seed: 347202193766632
IntegerQuicksort.sort in 61.21 milliseconds.
Arrays.sort in 131.72 milliseconds.

I am well aware that the current pivot selection rule will make the algorithm degrade to quadratic running-time on sorted input; please ignore this, I wanted to experiment a little bit.

So, is there room for improvement? Naming? Coding style? Please, tell everything that comes to mind.

share|improve this question
1  
I would possibly prefer rightPartitionIndex = toIndex to rightPartitionLength = 0 and then decrement it and use it as a direct index. – njzk2 Jan 29 at 0:39
up vote 6 down vote accepted

First of all, your benchmark is not really correct because it doesn't take into account any VM warmup and has only a single iteration.

Using JMH 1.11.3, I rewrote your benchmark: two integer arrays of length 10.000, 100.000, 1.000.000 and 10.000.000 are created with random values and then sorted with your implementation and Arrays.sort. The results are (Windows 10, JDK 1.8.0_66 64 bits, i5-3230M CPU @ 2.60GHz):

Benchmark            (length)  Mode  Cnt     Score    Error  Units
SortTest.arraysSort     10000  avgt   30     0,557 ±  0,015  ms/op
SortTest.arraysSort    100000  avgt   30     7,369 ±  0,267  ms/op
SortTest.arraysSort   1000000  avgt   30    86,435 ±  3,273  ms/op
SortTest.arraysSort  10000000  avgt   30  1039,120 ± 49,706  ms/op
SortTest.customSort     10000  avgt   30     0,905 ±  0,029  ms/op
SortTest.customSort    100000  avgt   30    11,152 ±  0,391  ms/op
SortTest.customSort   1000000  avgt   30   132,986 ±  5,581  ms/op
SortTest.customSort  10000000  avgt   30  1530,132 ± 42,771  ms/op

This shows that while Arrays.sort is indeed a little faster, your implementation has a very good performance, for small and large arrays.


I find your code is really good and easy to read. Only a few remarks if you intent to keep this code around:

  • The method sort(int[] array, int fromIndex, int toIndex) does not do any sanity checks on fromIndex and toIndex. This is well understandable because it introduces another level of complexity. You should then consider making that method private instead of public: this way, you ensure that no out of bounds exception can occur through the public API.
  • Consider perhaps renaming the utility class IntQuicksort to make it clear that is operates on primitive int array and not Integer objects. Also, since this is a utility class, consider making it final and adding a private constructor.
  • Regarding the code itself, I would add a swap method to refactor the code a little

    private static void swap(int[] array, int firstIndex, int secondIndex) {
        int tmp = array[firstIndex];
        array[firstIndex] = current;
        array[secondIndex] = tmp;
    }
    

    and use it like

    if (current > pivot) {
        ++rightPartitionLength;
        swap(array, toIndex - rightPartitionLength, index);
    } else if (current < pivot) {
        swap(array, fromIndex + leftPartitionLength, index);
        ++index;
        ++leftPartitionLength;
    }
    

Code of benchmark for completeness:

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;

import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Param;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;

@Warmup(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 700, timeUnit = TimeUnit.MILLISECONDS)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Fork(3)
public class SortTest {

    @State(Scope.Benchmark)
    public static class ArrayContainer {

        @Param({ "10000", "100000", "1000000", "10000000" })
        private int length;

        private int[] array;
        private int[] arrayToSort;

        @Setup(Level.Iteration)
        public void setUp() {
            ThreadLocalRandom random = ThreadLocalRandom.current();
            array = random.ints(length).toArray();
        }

        @Setup(Level.Invocation)
        public void cloneArray() {
            arrayToSort = array.clone();
        }

    }

    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    public static void sort(int[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        int pivot = array[fromIndex];
        int leftPartitionLength = 0;
        int rightPartitionLength = 0;
        int index = fromIndex;

        while (index < toIndex - rightPartitionLength) {
            int current = array[index];

            if (current > pivot) {
                ++rightPartitionLength;
                int tmp = array[toIndex - rightPartitionLength];
                array[toIndex - rightPartitionLength] = current;
                array[index] = tmp;
            } else if (current < pivot) {
                int tmp = array[fromIndex + leftPartitionLength];
                array[fromIndex + leftPartitionLength] = current;
                array[index] = tmp;

                ++index;
                ++leftPartitionLength;
            } else {
                ++index;
            }
        }

        sort(array, fromIndex, fromIndex + leftPartitionLength);
        sort(array, toIndex - rightPartitionLength, toIndex);
    }

    @Benchmark
    public int[] customSort(ArrayContainer container) {
        sort(container.arrayToSort);
        return container.arrayToSort;
    }

    @Benchmark
    public int[] arraysSort(ArrayContainer container) {
        Arrays.sort(container.arrayToSort);
        return container.arrayToSort;
    }

}
share|improve this answer
    
Thanks for your input! I will review your review soon, yet I have an acute question: would modern Java sort of "inline" that swap function or optimize it any other way? – coderodde Jan 28 at 18:24
1  
@coderodde Yes it probably would be inlined. Making a separate method is just for clarity, I don't think it has any impact on performance. – Tunaki Jan 28 at 18:25
    
So, in the average mode, the score represents the average running time over a number of iterations? – coderodde Jan 29 at 10:56
1  
@coderodde Yes, the table shows the time it took to sort with the corresponding error (both are in millis). Benchmark was done with 10 iterations (with also 10 warmup iterations) of 700 ms to reduce the error. – Tunaki Jan 29 at 10:58
  • No naked loops

    The while loop implements an important algorithm, known as partition, and deserves to have a name. I recommend to factor it out into a method

    int partition(int [] array, int fromIndex, int toIndex);
    

    returning a partition point.

  • Tail recursion

    AFAIK Java doesn't optimize tail recursive calls. You may want to eliminate second call to sort manually.

  • Indices vs lengths

    It seems that operating on partition boundaries instead of lengths may simplify the code. Mostly matter of taste I suppose.

Otherwise, LGTM.

share|improve this answer
1  
Very good point about simulating tail recursion. Thank you! – coderodde Jan 28 at 18:18

Implementation details:

Instead of using the length of each side of the partition it would be simpler to just to keep track of the index of the boundary. Also a swap function would make your code more readable.

     public static void  swap(int x, int y, int[] array) 
     {       
         int tmp = array[x];
         array[x] = array[y];
         array[y] = tmp;
     }

You would end with something like this:

   public static void sort(int[] array, int fromIndex, int toIndex) 
   {
        if (toIndex - fromIndex < 2) return;

        int l = fromIndex; 
        int g = toIndex;    
        int i = l + 1;
        int pivot = l;        
        while (i < g)
        {
            if (array[i] < pivot)
                swap(i++, l++, array);
            else if (array[i] > pivot)
                swap(i, --g, array);
            else
                i++;
        }

        sort(array, fromIndex, l);
        sort(array, g, toIndex);
  }

Also if java 8 is available you can change this function:

public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {

       int[] array = new int[size];

        for (int i = 0; i < size; ++i) {
            array[i] = random.nextInt(maximum - minimum + 1) + minimum;
        }

        return array;
    }

to:

 public static int[] getRandomArray(int size, 
                                       int minimum, 
                                       int maximum, 
                                       Random random) {     
     return random.ints(minimum, maximum + 1)
                  .limit(size)
                  .toArray();
 }

Partition algorithm :

This seams to be Dijkstra's 3-way partitioning, a better 3 way partitioning would be Bentley-Mcilroy's (is similar to Hoare's and unlike Dijkstra's it doesn't do extra swaps if there are no repeated pivot elements). For more information check this: QUICKSORT IS OPTIMAL.

Recursion:

You could avoid recursion using a stack (unboxing and autoboxing could make tail recursion a better choice though). Also by always pushing the smallest range into the stack you ensure that at any given time the number of ranges inside it are at most lg(n).

NOTE: Creating a fixed size int Stack would give you the best performance. You can use the fixed size 2*log2(n).

public static void sort(int[] array, int fromIndex, int toIndex) 
{

    Stack<Integer> stack = new Stack<>();
    stack.push(null);
    stack.push(null);
    while (!stack.empty()) 
    {
        while (fromIndex < toIndex - 1) 
        {
            int l = fromIndex;
            int g = toIndex;
            int i = l + 1;
            int pivot = l;
            while (i < g) 
            {
                if (array[i] < pivot) 
                    swap(i++, l++, array);
                else if (array[i] > pivot) 
                    swap(i, --g, array);
                else 
                    i++;
            }
            if ((l - fromIndex) > (toIndex - g)) 
            {
                stack.push(l);
                stack.push(fromIndex);
                fromIndex = g;
            } 
            else 
            {
                stack.push(toIndex);
                stack.push(g);
                toIndex = l;
            }

        }
        fromIndex = stack.pop();
        toIndex = stack.pop();
    }

}
share|improve this answer
1  
@greybeard Doing approximate string mathcing is an important skill for a programmer. – coderodde Jan 28 at 19:14
1  
I am not a native speaker but I guess any constructive criticism is welcome. I was trying to make a code review and ended up getting a spelling review, O well. – MAG Jan 28 at 21:35
    
you can also re-implement an array-based stack (it looks like the max size is log(n)) – njzk2 Jan 29 at 0:43
    
Yes exactly. And is pretty simple to implement. – MAG Jan 29 at 0:53
    
@MAG I was sarcastic towards greybeard, not you. :-) – coderodde Jan 29 at 7:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.