0
\$\begingroup\$

See the previous and initial iteration.

I got rid of Run objects and just maintain two integer arrays in the RunHeap: one for starting indices, and another for ending indices. Also, thanks to a great suggestion by @maaartinus, the algorithm is now stable.

The last, but not least: I do not longer sift up a newly pushed run as soon it is added, but rather append it to the tail of the array, and once all runs are considered, I do a bulk heapify, which (according to Introduction to Algorithms) runs in \$\Theta(N)\$ time instead of \$\Theta(N \log N)\$, which is an improvement.

HeapSelectionSort.java:

package net.coderodde.util.sorting;

import java.util.Arrays;
import java.util.Comparator;

/**
 * This class implements a sorting algorithm called 
 * <b><i>heap selection sort</i></b>. The worst case complexity is linearithmic
 * O(n log n), best case complexity linear O(n). Linear space complexity and is
 * now <b>stable</b>.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.61
 */
public class HeapSelectionSort {

    /**
     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
     * array[toIndex - 2], array[toIndex - 1]} using the specified comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     * @param fromIndex  the starting (inclusive) index of the range to sort.
     * @param toIndex    the ending (exclusive) index of the range to sort.
     * @param comparator the array component comparator.
     */
    public static <T> void sort(T[] array, 
                                int fromIndex, 
                                int toIndex, 
                                Comparator<? super T> comparator) {
        rangeCheck(array.length, fromIndex, toIndex);

        if (toIndex - fromIndex < 2) {
            return;
        }

        T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
        RunHeap<T> heap = createRunHeap(aux, comparator);

        for (; fromIndex < toIndex; ++fromIndex) {
            array[fromIndex] = heap.popElement();
        }
    }

    /**
     * Sorts the entire array using the specified comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     * @param comparator the array component comparator.
     */
    public static <T> void sort(T[] array, Comparator<? super T> comparator) {
        sort(array, 0, array.length, comparator);
    }

    /**
     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
     * array[toIndex - 2], array[toIndex - 1]} using the natural comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     * @param fromIndex  the starting (inclusive) index of the range to sort.
     * @param toIndex    the ending (exclusive) index of the range to sort.
     */
    public static <T> void sort(T[] array, int fromIndex, int toIndex) {
        sort(array, fromIndex, toIndex, NaturalOrder.INSTANCE);
    }

    /**
     * Sorts the entire array using the natural comparator.
     * 
     * @param <T>        the array component type.
     * @param array      the array holding the range to sort.
     */
    public static <T> void sort(T[] array) {
        sort(array, 0, array.length);
    }

    /**
     * Builds the actual run heap. A run is any contiguous subsequence that is
     * either ascending or (strictly) descending. We need descending runs to be
     * strictly descending because we will reverse them in order. Thus, if we
     * ever had contiguous equal elements, they would have been reversed and 
     * stability gone.
     * 
     * @param <T>        the array component type.
     * @param array      the actual array.
     * @param comparator the comparator.
     * @return the run heap.
     */
    private static <T> RunHeap<T> 
        createRunHeap(T[] array, Comparator<? super T> comparator) {
        RunHeap<T> heap = new RunHeap<>(array, comparator);

        int head;
        int left = 0;
        int last = array.length - 1;

        while (left < last) {
            head = left;

            // Decide the direction of the next run.
            if (comparator.compare(array[left], array[left + 1]) <= 0) {
                ++left;

                // Scanning ascending run.
                while (left < last
                        && comparator.compare(array[left], 
                                              array[left + 1]) <= 0) {
                    ++left;
                }

                heap.pushRun(head, left);
            } else {
                // Scanning strictly descending run.
                while (left < last
                        && comparator.compare(array[left], 
                                              array[left + 1]) > 0) {
                    ++left;
                }

                reverseRun(array, head, left);
                heap.pushRun(head, left);
            }

            ++left;
        }

        // A special case: the very last element may be left without buddies
        // so make it (the only) 1-element run.
        if (left == last) {
            heap.pushRun(left, left);
        }

        // Heapify. O(N) as described in "Introduction to Algorithms."
        heap.buildHeap();
        return heap;
    }

    /**
     * This class implements the actual run heap.
     * 
     * @param <T> the array component type.
     */
    private static class RunHeap<T> {
        private int size;
        private final T[] array;
        private final int[] fromIndexArray;
        private final int[] toIndexArray;
        private final Comparator<? super T> comparator;

        RunHeap(T[] array, Comparator<? super T> comparator) {
            this.array = array;
            this.fromIndexArray = new int[array.length / 2 + 1];
            this.toIndexArray = new int[array.length / 2 + 1];
            this.comparator = comparator;
        }

        /**
         * Removes and returns the minimal element.
         * 
         * @return the minimal element.
         */
        T popElement() {
            T ret = array[fromIndexArray[0]];

            if (fromIndexArray[0] == toIndexArray[0]) {
                // The topmost run is exhausted.
                int last = fromIndexArray[--size];
                fromIndexArray[0] = last;
                last = toIndexArray[size];
                toIndexArray[0] = last;
            } else {
                // Increment to the next element.
                fromIndexArray[0]++;
            }

            // Possibly sift down the top element in order to restore the
            // heap invariant.
            siftDown(0);
            return ret;
        }

        /**
         * Appends the run to the tail of this heap.
         * 
         * @param fromIndex the starting inclusive index of a run.
         * @param toIndex   the ending inclusive index of a run.
         */
        void pushRun(int fromIndex, int toIndex) {
            int nodeIndex = size++;
            fromIndexArray[nodeIndex] = fromIndex;
            toIndexArray[nodeIndex] = toIndex;
        }

        /**
         * Heapifies the entire heap run, restoring the heap property. Runs in
         * O(N) time, where N is the amount of runs.
         */
        void buildHeap() {
            for (int i = size / 2; i >= 0; --i) {
                siftDown(i);
            }
        }

        private boolean isLessThan(int runIndex1, int runIndex2) {
            T element1 = array[fromIndexArray[runIndex1]];
            T element2 = array[fromIndexArray[runIndex2]];

            int cmp = comparator.compare(element1, element2);

            if (cmp != 0) {
                return cmp < 0;
            }

            return fromIndexArray[runIndex1] < fromIndexArray[runIndex2];
        }

        private void siftDown(int index) {
            int nodeIndex = index;
            int leftChildIndex = (index << 1) + 1;
            int rightChildIndex = leftChildIndex + 1;
            int minIndex = index;

            for (;;) {
                if (leftChildIndex < size 
                        && isLessThan(leftChildIndex, nodeIndex)) {
                    minIndex = leftChildIndex;
                }

                if (rightChildIndex < size
                        && isLessThan(rightChildIndex, minIndex)) {
                    minIndex = rightChildIndex;
                }

                if (minIndex == nodeIndex) {
                    return;
                }

                int tmp = fromIndexArray[minIndex];
                fromIndexArray[minIndex] = fromIndexArray[nodeIndex];
                fromIndexArray[nodeIndex] = tmp;

                tmp = toIndexArray[minIndex];
                toIndexArray[minIndex] = toIndexArray[nodeIndex];
                toIndexArray[nodeIndex] = tmp;

                nodeIndex = minIndex;
                leftChildIndex = (nodeIndex << 1) + 1;
                rightChildIndex = leftChildIndex + 1;
            }
        }
    }

    private static <T> void reverseRun(T[] array, int fromIndex, int toIndex) {
        for (; fromIndex < toIndex; ++fromIndex, --toIndex) {
            T tmp = array[fromIndex];
            array[fromIndex] = array[toIndex];
            array[toIndex] = tmp;
        }
    }

    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
        if (fromIndex > toIndex) {
            throw new IllegalArgumentException(
                    "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
        }

        if (fromIndex < 0) {
            throw new ArrayIndexOutOfBoundsException(
                    "'fromIndex' is negative: " + fromIndex);
        }

        if (toIndex > arrayLength) {
            throw new ArrayIndexOutOfBoundsException(
                    "'toIndex' is too large: " + toIndex + ", array length: " +
                    arrayLength);
        }
    }

    private static final class NaturalOrder implements Comparator<Object> {

        @SuppressWarnings("unchecked")
        @Override
        public int compare(Object first, Object second) {
            return ((Comparable<Object>) first).compareTo(second);
        }

        private static final NaturalOrder INSTANCE = new NaturalOrder();
    }
}

Demo.java:

package net.coderodde.util.sorting;

import java.util.Arrays;
import java.util.Random;
import static net.coderodde.util.sorting.HeapSelectionSort.sort;

public class Demo {

    public static void main(final String... args) {
        demo();
    }

    private static Integer[] createRandomIntegerArray(int size, Random random) {
        Integer[] ret = new Integer[size];

        for (int i = 0; i < size; ++i) {
            ret[i] = random.nextInt(size / 2);
        }

        return ret;
    }

    private static Integer[] createPresortedArray(int size, 
                                                  int runs, 
                                                  Random random) {
        Integer[] ret = createRandomIntegerArray(size, random);
        int runLength = size / runs;

        for (int i = 0; i < runs; ++i) {
            Arrays.sort(ret, runLength * i, 
                        Math.min(size, runLength * (i + 1)));
        }

        return ret;
    }

    private static boolean isSorted(Integer[] array, 
                                    int fromIndex, 
                                    int toIndex) {
        for (int i = fromIndex; i < toIndex - 1; ++i) {
            if (array[i].compareTo(array[i + 1]) > 0) {
                return false;
            }
        }

        return true;
    }

    private static boolean isSorted(Integer[] array) {
        return isSorted(array, 0, array.length);
    }

    private static <T> boolean arraysEqual(T[] array1, T[] array2) {
        if (array1.length != array2.length) {
            return false;
        }

        for (int i = 0; i < array1.length; ++i) {
            if (array1[i] != array2[i]) {
                return false;
            }
        }

        return true;
    }    

    private static void demo() {
        long arraysSortTotal = 0L;
        long heapSelectionSortTotal = 0L;
        long seed = 3706213852107L; System.nanoTime();

        System.out.println("Seed: " + seed);
        System.out.println("-------------------");

        for (int op = 0; op < 10; ++op) {
            Random random = new Random(System.nanoTime());

            Integer[] array1 = createRandomIntegerArray(100000, random);
            Integer[] array2 = array1.clone();

            long ta = System.currentTimeMillis();
            Arrays.sort(array1);
            long tb = System.currentTimeMillis();

            System.out.println("Random array:");
            System.out.println("Arrays.sort in " + (tb - ta) + " ms, sorted: " +
                               isSorted(array1));
            arraysSortTotal += tb - ta;

            ta = System.currentTimeMillis();
            sort(array2);
            tb = System.currentTimeMillis();

            heapSelectionSortTotal += tb - ta;

            System.out.println("Heap insertion sort in " + (tb - ta) + " ms, " +
                               "sorted: " + isSorted(array2));
            System.out.println("Arrays same: " + arraysEqual(array1, array2));

            for (int i = 0; i < 80; ++i) {
                System.out.print("-");
            }

            System.out.println();

            array1 = createPresortedArray(150000, 100, random);
            array2 = array1.clone();

            ta = System.currentTimeMillis();
            Arrays.sort(array1);
            tb = System.currentTimeMillis();

            System.out.println("Presorted array:");
            System.out.println("Arrays.sort in " + (tb - ta) + " ms, sorted: " +
                               isSorted(array1));
            arraysSortTotal += tb - ta;

            ta = System.currentTimeMillis();
            sort(array2);
            tb = System.currentTimeMillis();

            heapSelectionSortTotal += tb - ta;

            System.out.println("Heap insertion sort in " + (tb - ta) + " ms, " +
                               "sorted: " + isSorted(array2));
            System.out.println("Arrays same: " + arraysEqual(array1, array2));

            for (int i = 0; i < 80; ++i) {
                System.out.print("-");
            }

            System.out.println();
        }

        System.out.println("Total of Arrays.sort: " + arraysSortTotal + " ms.");
        System.out.println("Total of heap insertion sort: " + 
                           heapSelectionSortTotal + " ms.");
    }
}

Digits I got:

 Seed: 3706213852107
 -------------------
 Random array:
 Arrays.sort in 222 ms, sorted: true
 Heap insertion sort in 148 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 183 ms, sorted: true
 Heap insertion sort in 91 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 33 ms, sorted: true
 Heap insertion sort in 109 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 30 ms, sorted: true
 Heap insertion sort in 57 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 44 ms, sorted: true
 Heap insertion sort in 108 ms, sorted: true
 Arrays identical: true
 ------------------
 Presorted array:
 Arrays.sort in 46 ms, sorted: true
 Heap insertion sort in 39 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 53 ms, sorted: true
 Heap insertion sort in 95 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 29 ms, sorted: true
 Heap insertion sort in 73 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 33 ms, sorted: true
 Heap insertion sort in 111 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 29 ms, sorted: true
 Heap insertion sort in 58 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 42 ms, sorted: true
 Heap insertion sort in 68 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 31 ms, sorted: true
 Heap insertion sort in 35 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 35 ms, sorted: true
 Heap insertion sort in 70 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 34 ms, sorted: true
 Heap insertion sort in 36 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 32 ms, sorted: true
 Heap insertion sort in 71 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 30 ms, sorted: true
 Heap insertion sort in 38 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 35 ms, sorted: true
 Heap insertion sort in 114 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 29 ms, sorted: true
 Heap insertion sort in 39 ms, sorted: true
 Arrays identical: true
 -------------------
 Random array:
 Arrays.sort in 32 ms, sorted: true
 Heap insertion sort in 81 ms, sorted: true
 Arrays identical: true
 -------------------
 Presorted array:
 Arrays.sort in 35 ms, sorted: true
 Heap insertion sort in 42 ms, sorted: true
 Arrays identical: true
 -------------------
 Total of Arrays.sort: 1037 ms.
 Total of heap insertion sort: 1483 ms.
\$\endgroup\$
2
\$\begingroup\$

I'm afraid @maaartinus is right about the odds to improve on the state of the art in sorting in his comment to his answer to the initial iteration.

With runs at most half as numerous as elements, the heap stays a bit smaller. The number of operations doesn't decrease as much, as runs need to be re-sifted.
If you declare the "non-Comparator-sorts" using <T extends Comparable<T>>, you can use Comparator.naturalOrder() (rendering class NaturalOrder dispensable) - you're casting, anyway.

I tried to reduce code multiplication in createRunHeap, but was not entirely successful:

for ( ; left < last ; left++) {
    final int head = left;
// Decide the direction of the next run.
    final boolean strictlyDecreasing =
        comparator.compare(array[left++], array[left]) < 0;
    while (left < last
           && strictlyDecreasing
              == comparator.compare(array[left++], array[left]) < 0) {
    }
// reversing strictly decreasing runs, only
//  keeps forming runs stable while increasing run count
//  by two for every run of "equal" elements
//  wedged between two strictly decreasing runs
    if (strictlyDecreasing) {
        reverseRun(array, head, left);
    }
    heap.pushRun(head, left);
}

But, then:

/** Detects changes in parameter value to the one used
 * in the constructor or first invocation, respectively */
static class ChangeDetector {
    boolean set;
    Object previous;
/** Will detect changes
 *   from the parameter of the first invocation */
    ChangeDetector(){}
/** Will detect changes from {@code initial} */
    ChangeDetector(Object initial) {
        previous = initial;
        set = true;
    }
/** @return {@code thisTime}
 *          equals parameter in constructor/first invocation */
    boolean same(Object thisTime) {
        if (!set) {
            previous = thisTime;
            return set = true;
        }
        return previous == thisTime
            || previous != null && previous.equals(thisTime);
    }
}
…
    for ( ; left < last ; left++) {
        final int head = left;
    // Decide the direction of the next run.
        ChangeDetector stays = new ChangeDetector();
        while (left < last
               && stays.same(comparator.compare(
                   array[left++], array[left]) < 0)) {
        }
        if (stays.same(Boolean.TRUE)) {
            reverseRun(array, head, left);
        }
        heap.pushRun(head, left);
    }
\$\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.