2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Rearranging if statements

This series of if statements puzzled me for a while:

        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;
        }

I know what it is doing - it's finding the maximum child (if any). It's just that certain branches when taken should mean that other branches are not reachable. For example, if the first if is taken, it means that the left child is a valid child. But that means that it can't be the case that maxChildIndex == index, which is checked immediately after.

In the worst case, the code has to go through 4 if statements. But I would rearrange the order of the if statements to prevent unnecessary checks, which reduces the worst case to 2 if statements:

        if (fromIndex + leftChildIndex < toIndex
                && array[fromIndex + leftChildIndex] > target) {
            maxChildIndex = leftChildIndex;
            if (fromIndex + rightChildIndex < toIndex
                    && array[fromIndex + rightChildIndex] >
                       array[fromIndex + leftChildIndex]) {
                maxChildIndex = rightChildIndex;
            }
        } else {
            if (fromIndex + rightChildIndex < toIndex
                    && array[fromIndex + rightChildIndex] > target) {
                maxChildIndex = rightChildIndex;
            } else {
                // No swap. Just insert the sifted element.
                array[fromIndex + maxChildIndex] = target;
                return;
            }
        }
\$\endgroup\$
0
\$\begingroup\$

I don't have much comment on the algorithm itself.

Java benchmarking is notoriously tricky since it does on-the-fly optimization. See this for example.

I would make Demo an actual class. I would not hard code LENGTH and ITERATION since you might want to benchmark with various values.

You might want to benchmark more than Arrays.sort and Heapsort.sort. So instead of hard coding those sorting functions, you can define a function Map<String, Double> benchmark(Map<String, Consumer<int[]>>... sortingFunctions). Arrays::sort and Heapsort::sort are instances of Consumer<int[]>.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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