Given an array \$A = (a_1, a_2, \dots, a_n)\$, the number of inversions in \$A\$ is the number of index pairs \$i,j\$ (\$i < j\$) such that \$a_i > a_j\$. We can find the number of inversions in an array by running it through a slightly modified mergesort, which runs in \$\Theta(n \log n)\$. Even better, we can deploy a natural mergesort which runs in \$\Theta(n \log m)\$ time where \$m\$ is the number of runs in the input array. As a reminder, a run is a contiguous subsequence that is ascending. Needless to say, \$m \leq n\$. Without further ado, let's proceed to code:
BruteForceInversionCounter.java
package net.coderodde.util;
import java.util.Comparator;
import java.util.Objects;
import static net.coderodde.util.Utils.NATURAL_ORDER;
import static net.coderodde.util.Utils.checkIndices;
/**
* This class implements a brute force inversion counting algorithm that runs in
* quadratic time.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public final class BruteForceInversionCounter {
public static <T> int count(T[] array,
int fromIndex,
int toIndex,
Comparator<? super T> comparator) {
Objects.requireNonNull(array);
Objects.requireNonNull(comparator);
checkIndices(array.length, fromIndex, toIndex);
int inversions = 0;
for (int i = fromIndex; i < toIndex; ++i) {
for (int j = i + 1; j < toIndex; ++j) {
if (comparator.compare(array[i], array[j]) > 0) {
inversions++;
}
}
}
return inversions;
}
public static <T> int count(T[] array, int fromIndex, int toIndex) {
return count(array, fromIndex, toIndex, NATURAL_ORDER);
}
public static <T> int count(T[] array, Comparator<? super T> comparator) {
Objects.requireNonNull(array);
return count(array, 0, array.length, comparator);
}
public static <T> int count(T[] array) {
return count(array, NATURAL_ORDER);
}
private BruteForceInversionCounter() {}
}
MergesortInversionCounter.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import static net.coderodde.util.Utils.NATURAL_ORDER;
import static net.coderodde.util.Utils.checkIndices;
/**
* This class implements a modification of merge sort that sorts an input array
* range and returns the number of inversions in the input range.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public final class MergesortInversionCounter {
public static <T> int count(T[] array,
int fromIndex,
int toIndex,
Comparator<? super T> comparator) {
Objects.requireNonNull(array);
checkIndices(array.length, fromIndex, toIndex);
int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
return 0;
}
T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
return count(aux, array, 0, fromIndex, rangeLength, comparator);
}
private static <T> int count(T[] sourceArray,
T[] targetArray,
int sourceOffset,
int targetOffset,
int rangeLength,
Comparator<? super T> comparator) {
if (rangeLength < 2) {
return 0;
}
int halfRangeLength = rangeLength >>> 1;
int inversions = count(targetArray,
sourceArray,
targetOffset,
sourceOffset,
halfRangeLength,
comparator);
inversions += count(targetArray,
sourceArray,
targetOffset + halfRangeLength,
sourceOffset + halfRangeLength,
rangeLength - halfRangeLength,
comparator);
return inversions + merge(sourceArray,
targetArray,
sourceOffset,
targetOffset,
halfRangeLength,
rangeLength - halfRangeLength,
comparator);
}
public static <T> int count(T[] array, int fromIndex, int toIndex) {
return count(array, fromIndex, toIndex, NATURAL_ORDER);
}
public static <T> int count(T[] array, Comparator<? super T> comparator) {
Objects.requireNonNull(array);
return count(array, 0, array.length);
}
public static <T> int count(T[] array) {
return count(array, NATURAL_ORDER);
}
private static <T> int merge(T[] sourceArray,
T[] targetArray,
int sourceOffset,
int targetOffset,
int leftRunLength,
int rightRunLength,
Comparator<? super T> comparator) {
int inversions = 0;
int leftRunIndex = sourceOffset;
int leftRunEndIndex = sourceOffset + leftRunLength;
int rightRunIndex = sourceOffset + leftRunLength;
int rightRunEndIndex = rightRunIndex + rightRunLength;
int targetIndex = targetOffset;
while (leftRunIndex < leftRunEndIndex
&& rightRunIndex < rightRunEndIndex) {
if (comparator.compare(sourceArray[rightRunIndex],
sourceArray[leftRunIndex]) < 0) {
inversions += leftRunEndIndex - leftRunIndex;
targetArray[targetIndex++] = sourceArray[rightRunIndex++];
} else {
targetArray[targetIndex++] = sourceArray[leftRunIndex++];
}
}
System.arraycopy(sourceArray,
leftRunIndex,
targetArray,
targetIndex,
leftRunEndIndex - leftRunIndex);
System.arraycopy(sourceArray,
rightRunIndex,
targetArray,
targetIndex,
rightRunEndIndex - rightRunIndex);
return inversions;
}
private MergesortInversionCounter() {}
}
NaturalMergesortInversionCounter.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Objects;
import static net.coderodde.util.Utils.NATURAL_ORDER;
import static net.coderodde.util.Utils.checkIndices;
/**
* This class implements a modification of the natural mergesort that counts
* inversion in the input array range.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public final class NaturalMergesortInversionCounter {
public static <T> int count(T[] array,
int fromIndex,
int toIndex) {
return count(array, fromIndex, toIndex, NATURAL_ORDER);
}
public static <T> int count(T[] array) {
Objects.requireNonNull(array);
return count(array, 0, array.length);
}
public static <T> int count(T[] array, Comparator<? super T> comparator) {
Objects.requireNonNull(array);
return count(array, 0, array.length, comparator);
}
public static <T> int count(T[] array,
int fromIndex,
int toIndex,
Comparator<? super T> comparator) {
Objects.requireNonNull(array);
Objects.requireNonNull(comparator);
checkIndices(array.length, fromIndex, toIndex);
int rangeLength = toIndex - fromIndex;
if (rangeLength < 2) {
return 0;
}
RunLengthQueue runLengthQueue =
buildRunLengthQueue(array,
fromIndex,
toIndex,
comparator);
T[] bufferArray = Arrays.copyOfRange(array, fromIndex, toIndex);
T[] sourceArray;
T[] targetArray;
int sourceOffset;
int targetOffset;
int mergePasses = getNumberOfMergePasses(runLengthQueue.size());
if ((mergePasses & 1) == 1) {
// Odd amount of merge passes over the entire input array range.
// Set the buffer array as the source array so that the sorted
// result ends in in the input array.
sourceArray = bufferArray;
targetArray = array;
sourceOffset = 0;
targetOffset = fromIndex;
} else {
sourceArray = array;
targetArray = bufferArray;
sourceOffset = fromIndex;
targetOffset = 0;
}
int runsLeftInCurrentMergePass = runLengthQueue.size();
int offset = 0;
int inversions = 0;
// While there are runs to merge, iterate:
while (runLengthQueue.size() > 1) {
int leftRunLength = runLengthQueue.dequeue();
int rightRunLength = runLengthQueue.dequeue();
inversions += merge(sourceArray,
targetArray,
sourceOffset + offset,
targetOffset + offset,
leftRunLength,
rightRunLength,
comparator);
runLengthQueue.enqueue(leftRunLength + rightRunLength);
runsLeftInCurrentMergePass -= 2;
offset += leftRunLength + rightRunLength;
switch (runsLeftInCurrentMergePass) {
case 1:
int lastRunLength = runLengthQueue.dequeue();
// In the target array, this 'unmarried' run might be
// in the form of two unmerged runs.
System.arraycopy(sourceArray,
sourceOffset + offset,
targetArray,
targetOffset + offset,
lastRunLength);
runLengthQueue.enqueue(lastRunLength);
// FALL THROUGH!
case 0:
runsLeftInCurrentMergePass = runLengthQueue.size();
offset = 0;
T[] tmpArray = sourceArray;
sourceArray = targetArray;
targetArray = tmpArray;
int tmpOffset = sourceOffset;
sourceOffset = targetOffset;
targetOffset = tmpOffset;
break;
}
}
return inversions;
}
static <T> RunLengthQueue
buildRunLengthQueue(T[] inputArray,
int fromIndex,
int toIndex,
Comparator<? super T> comparator) {
int last = toIndex - 1;
int left = fromIndex;
int right = left + 1;
RunLengthQueue runLengthQueue =
new RunLengthQueue(toIndex - fromIndex);
while (left < last) {
int head = left;
while (left < last
&& comparator.compare(inputArray[left],
inputArray[right]) <= 0) {
++left;
++right;
}
++left;
++right;
runLengthQueue.enqueue(left - head);
}
if (left == last) {
runLengthQueue.enqueue(1);
}
return runLengthQueue;
}
/**
* This static inner class implements a simple queue of integers used to
* represent the run sequence in the array to sort.
*/
private static final class RunLengthQueue {
/**
* The minimum capacity of the storage array.
*/
private static final int MINIMUM_CAPACITY = 256;
/**
* Stores the run lengths.
*/
private final int[] storage;
/**
* The index of the array component that will be dequeued next.
*/
private int head;
/**
* The index of the array component to which the next run length will
* be set.
*/
private int tail;
/**
* The current number of run lengths stored in this queue.
*/
private int size;
/**
* A bit mask used for simpler modulo calculation (at least at the level
* of hardware).
*/
private final int mask;
/**
* Creates a run length queue large enough to hold maximum of
* {@code capacity} elements.
*
* @param capacity the requested capacity, may be increased in the
* constructor.
*/
RunLengthQueue(int capacity) {
capacity = ceilPowerOfTwo(Math.max(capacity, MINIMUM_CAPACITY));
this.mask = capacity - 1;
this.storage = new int[capacity];
}
/**
* Enqueues a given run length to the tail of this queue.
*
* @param runLength the run length to enqueue.
*/
void enqueue(int runLength) {
storage[tail] = runLength;
tail = (tail + 1) & mask;
size++;
}
/**
* Dequeues the run length from the head of this queue.
*
* @return the run length stored in the head of this queue.
*/
int dequeue() {
int ret = storage[head];
head = (head + 1) & mask;
size--;
return ret;
}
/**
* Returns the number of run lengths stored in this queue.
*
* @return the number of run lengths.
*/
int size() {
return size;
}
/**
* Returns a smallest power of two no less than {@code number}.
*
* @param number the number to ceil.
* @return a smallest power of two no less than {@code number}.
*/
private static int ceilPowerOfTwo(int number) {
int ret = Integer.highestOneBit(number);
return ret != number ? (ret << 1) : ret;
}
}
/**
* Computes the required number of merge passes needed to sort an input
* array range containing {@code runs} runs.
*
* @param runs the number of runs in the input array range.
* @return the number of required merge passes.
*/
private static int getNumberOfMergePasses(int runs) {
return 32 - Integer.numberOfLeadingZeros(runs - 1);
}
private static <T> int merge(T[] sourceArray,
T[] targetArray,
int sourceOffset,
int targetOffset,
int leftRunLength,
int rightRunLength,
Comparator<? super T> comparator) {
int leftRunIndex = sourceOffset;
int rightRunIndex = leftRunIndex + leftRunLength;
int leftRunEndIndex = rightRunIndex;
int rightRunEndIndex = rightRunIndex + rightRunLength;
int targetIndex = targetOffset;
int inversions = 0;
while (leftRunIndex != leftRunEndIndex
&& rightRunIndex != rightRunEndIndex) {
if (comparator.compare(sourceArray[rightRunIndex],
sourceArray[leftRunIndex]) <0) {
inversions += leftRunEndIndex - leftRunIndex;
targetArray[targetIndex++] = sourceArray[rightRunIndex++];
} else {
targetArray[targetIndex++] = sourceArray[leftRunIndex++];
}
}
System.arraycopy(sourceArray,
leftRunIndex,
targetArray,
targetIndex,
leftRunEndIndex - leftRunIndex);
System.arraycopy(sourceArray,
rightRunIndex,
targetArray,
targetIndex,
rightRunEndIndex - rightRunIndex);
return inversions;
}
private NaturalMergesortInversionCounter() {}
}
Utils.java
package net.coderodde.util;
import java.util.Comparator;
/**
* This class contains generic facilities.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public final class Utils {
public static final Comparator NATURAL_ORDER = new Comparator() {
@Override
public int compare(Object o1, Object o2) {
return ((Comparable) o1).compareTo(o2);
}
};
public static void checkIndices(int arrayLength,
int fromIndex,
int toIndex) {
if (fromIndex < 0) {
throw new IndexOutOfBoundsException(
"fromIndex(" + fromIndex + ") < 0");
}
if (toIndex > arrayLength) {
throw new IndexOutOfBoundsException(
"toIndex(" + toIndex + ") > " +
"arrayLength(" + arrayLength + ")");
}
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
"fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
}
}
}
AbstractInversionCounterTest.java
package net.coderodde.util;
import java.util.Arrays;
import java.util.Random;
import org.junit.Test;
import static org.junit.Assert.*;
/**
* This abstract test class implements all the actual unit tests.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public abstract class AbstractInversionCounterTest {
private static final int TEST_ITERATIONS = 100;
private static final int MAXIMUM_ARRAY_LENGTH = 1000;
protected final InversionCounter<Integer> inversionCounter;
private final Random random = new Random();
public AbstractInversionCounterTest(
InversionCounter<Integer> inversionCounter) {
this.inversionCounter = inversionCounter;
}
@Test
public void test() {
for (int iteration = 0; iteration < TEST_ITERATIONS; iteration++) {
int length = random.nextInt(MAXIMUM_ARRAY_LENGTH + 1);
int fromIndex = random.nextInt(Math.max(1, length / 10));
int toIndex =
length - random.nextInt(
Math.max(1, (length - fromIndex) / 10));
Integer[] array1 = getRandomIntegerArray(length,
-length / 2 - 10,
+length / 2 + 10,
random);
Integer[] array2 = array1.clone();
assertEquals(BruteForceInversionCounter.count(array1,
fromIndex,
toIndex,
Integer::compareTo),
inversionCounter.count(array2,
fromIndex,
toIndex,
Integer::compareTo));
Arrays.sort(array1, fromIndex, toIndex);
assertTrue(Arrays.equals(array1, array2));
}
}
/**
* Creates a random integer array.
*
* @param length the desired length of the array.
* @param minValue the minimum integer value.
* @param maxValue the maximum integer value.
* @param random the random number generator.
* @return a randomly generated integer array.
*/
private Integer[] getRandomIntegerArray(int length,
int minValue,
int maxValue,
Random random) {
Integer[] array = new Integer[length];
for (int i = 0; i < length; ++i) {
array[i] = randomValue(minValue, maxValue, random);
}
return array;
}
/**
* Returns a random integer value from the range {@code minValue,
* minValue + 1, ..., maxValue - 1, maxValue}, according to the uniform
* distribution.
*
* @param minValue the minimum integer value.
* @param maxValue the maximum integer value.
* @param random the random number generator.
* @return a random integer value within the range.
*/
private Integer randomValue(int minValue, int maxValue, Random random) {
return minValue + random.nextInt(maxValue - minValue + 1);
}
}
InversionCounter.java
package net.coderodde.util;
import java.util.Comparator;
/**
* Defines the most specific API for inversion counting algorithms.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
* @param <T> the array component type.
*/
@FunctionalInterface
public interface InversionCounter<T> {
public int count(T[] array,
int fromIndex,
int toIndex,
Comparator<? super T> comparator);
}
MergesortInversionCounterTest.java
package net.coderodde.util;
/**
* This unit test tests the correctness of the mergesort-based inversion
* counter.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public class MergesortInversionCounterTest
extends AbstractInversionCounterTest {
public MergesortInversionCounterTest() {
super(MergesortInversionCounter::count);
}
}
NaturalMergesortInversionCounterTest.java
package net.coderodde.util;
/**
* This unit test tests the correctness of the mergesort-based inversion
* counter.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 30, 2017)
*/
public class NaturalMergesortInversionCounterTest
extends AbstractInversionCounterTest {
public NaturalMergesortInversionCounterTest() {
super(NaturalMergesortInversionCounter::count);
}
}
MyBenchmark.java
package net.coderodde;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import net.coderodde.util.MergesortInversionCounter;
import net.coderodde.util.NaturalMergesortInversionCounter;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
/**
* This class implements benchmark for inversion counter algorithms.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Dec 31, 2017)
*/
public class MyBenchmark {
private static final int ARRAY_LENGTH = 1_000_000;
private static final int MINIMUM_INTEGER_VALUE = -100_000;
private static final int MAXIMUM_INTEGER_VALUE = +100_000;
private static final int RUN_LENGTH_IN_PRESORTED_ARRAY = 2000;
@State(Scope.Thread)
public static class MyRandomState {
private final Random random = new Random();
Integer[] array;
@Setup(Level.Trial)
public void createRandomArray() {
array = createRandomIntegerArray(ARRAY_LENGTH,
MINIMUM_INTEGER_VALUE,
MAXIMUM_INTEGER_VALUE,
random);
}
}
@State(Scope.Thread)
public static class MyPresortedState {
private final Random random = new Random();
Integer[] array;
@Setup(Level.Trial)
public void createPresortedArray() {
array = createPresortedIntegerArray(ARRAY_LENGTH,
MINIMUM_INTEGER_VALUE,
MAXIMUM_INTEGER_VALUE,
random);
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void testMergesortOnRandomArray(MyRandomState state) {
MergesortInversionCounter.count(state.array);
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void testMergesortOnPresortedArray(MyPresortedState state) {
MergesortInversionCounter.count(state.array);
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void testNaturalMergesortOnRandomArray(MyRandomState state) {
NaturalMergesortInversionCounter.count(state.array);
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public void testNaturalMergesortOnPresortedArray(MyPresortedState state) {
NaturalMergesortInversionCounter.count(state.array);
}
private static Integer[] createRandomIntegerArray(int length,
int minimumIntegerValue,
int maximumIntegerValue,
Random random) {
Integer[] array = new Integer[length];
for (int i = 0; i < length; ++i) {
array[i] = getRandomIntegerValue(minimumIntegerValue,
maximumIntegerValue,
random);
}
return array;
}
private static Integer[]
createPresortedIntegerArray(int length,
int minimumIntegerValue,
int maximumIntegerValue,
Random random) {
Integer[] randomArray = createRandomIntegerArray(length,
minimumIntegerValue,
maximumIntegerValue,
random);
for (int i = 0; i < length; i += RUN_LENGTH_IN_PRESORTED_ARRAY) {
Arrays.sort(randomArray,
i,
Math.min(length, i + RUN_LENGTH_IN_PRESORTED_ARRAY));
}
return randomArray;
}
private static Integer getRandomIntegerValue(int minimumIntegerValue,
int maximumIntegerValue,
Random random) {
return minimumIntegerValue + random.nextInt(maximumIntegerValue -
minimumIntegerValue + 1);
}
public static void main(String[] args)
throws RunnerException {
Options options = new OptionsBuilder()
.include(MyBenchmark.class.getSimpleName())
.warmupIterations(5)
.measurementIterations(10)
.forks(1)
.build();
new Runner(options).run();
}
}
Benchmark figures
Benchmark Mode Cnt Score Error Units MyBenchmark.testMergesortOnPresortedArray avgt 10 317.640 ± 187.535 ms/op MyBenchmark.testMergesortOnRandomArray avgt 10 168.408 ± 37.833 ms/op MyBenchmark.testNaturalMergesortOnPresortedArray avgt 10 39.191 ± 17.872 ms/op MyBenchmark.testNaturalMergesortOnRandomArray avgt 10 50.237 ± 11.120 ms/op
Info
The actual counters live here. The benchmark lives here.
Critique request
Please tell me anything that comes to mind, be it related to algorithms, unit testing or benchmarking.
*Testdo not verify anything accept that the called constructors do not fail... \$\endgroup\$fail()into the abstract test. It gets called two times (once for each algo), so, yes, they are getting tested. \$\endgroup\$