I plan to work on Introsort, which requires a working implementation of heap sort. Also, the heap sort implementation must be able to sort arbitrary ranges within an array, which, in turn, requires some more involved index manipulation.
Heapsort.java:
package net.coderodde.util.sorting;
/**
* This class implements heap sort.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class Heapsort {
/**
* Sorts the entire integer array.
*
* @param array the array to sort.
*/
public static void sort(int[] array) {
sort(array, 0, array.length);
}
/**
* Sorts a particular range {@code array[fromIndex], array[fromIndex + 1],
* ..., array[toIndex - 2], array[toIndex - 1]}.
*
* @param array the array containing the target range.
* @param fromIndex the starting, inclusive index of the target range.
* @param toIndex the ending, exclusive index of the target range.
*/
public static void sort(int[] array, int fromIndex, int toIndex) {
if (toIndex - fromIndex < 2) {
return;
}
// CLRS says 'BUILD-MAX-HEAP' is O(n).
buildMaxHeap(array, fromIndex, toIndex);
// And this is O(n log n).
for (int i = toIndex - 1; i > fromIndex; --i) {
int tmp = array[i];
array[i] = array[fromIndex];
array[fromIndex] = tmp;
maxSiftDown(array, fromIndex, i, 0);
}
}
/**
* Makes sure the range {@code array[fromIndex], array[fromIndex + 1], ...,
* array[toIndex - 2], array[toIndex - 1]} forms a maximum heap.
*
* @param array the array holding the target range.
* @param fromIndex the starting, inclusive index of the range to rebuild
* as a heap.
* @param toIndex the ending, exclusive index of the range to rebuild as
* a heap.
*/
private static void buildMaxHeap(int[] array, int fromIndex, int toIndex) {
int rangeLength = toIndex - fromIndex;
for (int i = rangeLength / 2; i >= 0; --i) {
maxSiftDown(array, fromIndex, toIndex, i);
}
}
/**
* Sifts down the element {@code array[index]} in order to restore the max
* heap property. The heap is assumed to occupy the range
* {@code array[fromIndex ... toIndex - 1]}.
*
* @param array the array holding the heap.
* @param fromIndex the starting, inclusive index of the heap.
* @param toIndex the ending, exclusive index of the heap.
* @param index the index of the element to sift down.
*/
private static void maxSiftDown(int[] array,
int fromIndex,
int toIndex,
int index) {
int leftChildIndex = left(index);
// Right child index is one position from left child index towards
// larger indices.
int rightChildIndex = leftChildIndex + 1;
int maxChildIndex = index;
// Save the array component we want to sift down.
int target = array[fromIndex + index];
for (;;) {
if (fromIndex + leftChildIndex < toIndex
&& array[fromIndex + leftChildIndex] > target) {
maxChildIndex = leftChildIndex;
}
if (maxChildIndex == index) {
if (fromIndex + rightChildIndex < toIndex
&& array[fromIndex + rightChildIndex] > target) {
maxChildIndex = rightChildIndex;
}
} else {
if (fromIndex + rightChildIndex < toIndex
&& array[fromIndex + rightChildIndex] >
array[fromIndex + leftChildIndex]) {
maxChildIndex = rightChildIndex;
}
}
if (maxChildIndex == index) {
// No swap. Just insert the sifted element.
array[fromIndex + maxChildIndex] = target;
return;
}
// No swap here neither.
// Just move up the maximum to current position.
array[fromIndex + index] = array[fromIndex + maxChildIndex];
index = maxChildIndex;
leftChildIndex = left(index);
rightChildIndex = leftChildIndex + 1;
}
}
/**
* Returns the index of the left child of the element at index
* {@code index}.
*
* @param index the index of the target element.
* @return the index of the left child of the target element.
*/
private static int left(int index) {
return (index << 1) + 1;
}
}
Demo.java:
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;
import net.coderodde.util.sorting.Heapsort;
/**
* This class implements a demonstration of Introsort's and heap sort's
* performance as compared to {@link java.util.Arrays.sort}.
*
* @author Rodion "rodde" Efremov
* @version 1.6
*/
public class Demo {
private static final int LENGTH = 500000;
private static final int ITERATIONS = 30;
public static void main(String[] args) {
long seed = System.currentTimeMillis();
Random random = new Random(seed);
long totalArraysSort = 0L;
long totalHeapsort = 0L;
System.out.println("Seed: " + seed);
for (int iteration = 0; iteration < ITERATIONS; ++iteration) {
int[] array1 = getRandomIntegerArray(LENGTH, random);
int[] array2 = array1.clone();
int fromIndex = random.nextInt(LENGTH / 10);
int toIndex = LENGTH - random.nextInt(LENGTH / 10);
long startTime = System.currentTimeMillis();
Arrays.sort(array1, fromIndex, toIndex);
long endTime = System.currentTimeMillis();
totalArraysSort += endTime - startTime;
System.out.println("Arrays.sort in " + (endTime - startTime) +
" milliseconds.");
startTime = System.currentTimeMillis();
Heapsort.sort(array2, fromIndex, toIndex);
endTime = System.currentTimeMillis();
totalHeapsort += endTime - startTime;
System.out.println("Heapsort.sort in " + (endTime - startTime) +
" milliseconds");
System.out.println("Arrays identical: " + Arrays.equals(array1,
array2));
System.out.println("---");
}
System.out.println("Total Arrays.sort time: " + totalArraysSort +
" milliseconds.");
System.out.println("Total Heapsort.sort time: " + totalHeapsort +
" milliseconds.");
}
private static int[] getRandomIntegerArray(int size, Random random) {
return IntStream.range(0, size)
.map((i) -> random.nextInt(2 * size))
.toArray();
}
}
After I run the Demo, it prints:
Total Arrays.sort time: 1929 milliseconds. Total Heapsort.sort time: 3588 milliseconds.
Slower, but no can do. Hopefully introsort may come closer.
