3
\$\begingroup\$

I have refactored this. Once again, the running time can be anything between \$\Omega(n)\$ and \$\mathcal{O}(n^2)\$, yet it adapts to "smoothness" of the input array.

AdaptiveCountingSort.java:

package net.coderodde.util.sorting;

/**
 * This class implements an adaptive counting sort that adapts to the input.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6
 */
public class AdaptiveCountingSort {

    /**
     * Sorts the entire input integer array.
     * 
     * @param array the integer array to sort.
     */
    public static void sort(int[] array) {
        sort(array, 0, array.length);
    }

    /**
     * Sorts the range {@code array[fromIndex], array[fromIndex + 1], ...,
     * array[toIndex - 2], array[toIndex - 1]}.
     * 
     * @param array     the array containing the range to sort.
     * @param fromIndex the starting, inclusive range index.
     * @param toIndex   the ending, exclusive range index.
     */
    public static void sort(int[] array, int fromIndex, int toIndex) {
        if (toIndex - fromIndex < 2) {
            return;
        }

        AdaptiveCountingSort sort = new AdaptiveCountingSort(array, 
                                                             fromIndex, 
                                                             toIndex);
        sort.count();
        sort.buildRange();
    }

    /**
     * The node containing the least integer so far.
     */
    private Node head;

    /**
     * The node containing the largest integer so far.
     */
    private Node tail;

    /**
     * The node updated or created at previous array component.
     */
    private Node previous;

    /**
     * The actual array containing the range to sort.
     */
    private final int[] array;

    /**
     * The starting, inclusive index of the range to sort.
     */
    private final int fromIndex;

    /**
     * The ending, exclusive index of the range to sort.
     */
    private final int toIndex;

    /**
     * This field caches the previous array component.
     */
    private int previousElement;

    /**
     * Constructs the state needed for sorting.
     * 
     * @param array     the array containing the range to sort.
     * @param fromIndex the starting index of the range to sort.
     * @param toIndex   the ending index of the range to sort.
     */
    private AdaptiveCountingSort(int[] array, int fromIndex, int toIndex) {
        this.previousElement = array[fromIndex];
        this.array = array;
        this.fromIndex = fromIndex;
        this.toIndex = toIndex;
        this.head = this.tail = this.previous = new Node(previousElement);
    }

    // Handles 'currentElement' by inserting it in the proper location.
    private void findAndUpdateSmallerNode(int currentElement) {
        Node tmp = previous.prev;

        // Go down the node chain towards the nodes with smaller keys.
        while (tmp != null && tmp.element > currentElement) {
            tmp = tmp.prev;
        }

        if (tmp == null) {
            // 'currentElement' is the new minimum. Create new head node and put
            // the integer in it.
            Node newnode = new Node(currentElement);
            newnode.next = head;
            head.prev = newnode;
            head = newnode;
            previous = newnode;
        } else if (tmp.element == currentElement) {
            // The node containing 'currentElement' exists. Just increment the
            // counter.
            tmp.count++;
            previous = tmp;
        } else {
            // Insert a new node between 'tmp' and 'tmp.next'.
            Node newnode = new Node(currentElement);
            newnode.prev = tmp;
            newnode.next = tmp.next;
            newnode.prev.next = newnode;
            newnode.next.prev = newnode;
            previous = newnode;
        }
    }

    private void findAndUpdateLargerNode(int currentElement) {
        Node tmp = previous.next;

        // Go up the chain towards the nodes with larger keys.
        while (tmp != null && tmp.element < currentElement) {
            tmp = tmp.next;
        }

        // 'currentElement' is the new maximum. Create new tail node and put the
        // integer in it.
        if (tmp == null) {
            Node newnode = new Node(currentElement);
            newnode.prev = tail;
            tail.next = newnode;
            tail = newnode;
            previous = newnode;
        } else if (tmp.element == currentElement) {
            // The node containing 'currentElement' exists. Just increment the 
            // counter.
            tmp.count++;
            previous = tmp;
        } else {
            // Insert a new node between 'tmp.prev' and 'tmp'.
            Node newnode = new Node(currentElement);
            newnode.prev = tmp.prev;
            newnode.next = tmp;
            tmp.prev.next = newnode;
            tmp.prev = newnode;
            previous = newnode;
        }
    }

    // Constructs a sorted counter chain.
    private void count() {
        for (int i = fromIndex + 1; i < toIndex; ++i) {
            int currentElement = array[i];

            if (currentElement < previousElement) {
                findAndUpdateSmallerNode(currentElement);
            } else if (currentElement > previousElement) {
                findAndUpdateLargerNode(currentElement);
            } else {
                previous.count++;
            }

            previousElement = currentElement;
        }
    }

    // Reconstructs the node chain by dumping its content into input range.
    private void buildRange() {
        int index = fromIndex;

        for (Node node = head; node != null; node = node.next) {
            int element = node.element;
            int count = node.count;

            for (int i = 0; i < count; ++i) {
                array[index++] = element;
            }
        }
    }

    private static final class Node {

        Node(int element) {
            this.element = element;
            this.count = 1;
        }

        Node prev;
        Node next;
        int element;
        int count;
    }
}

Demo.java:

import java.util.Arrays;
import net.coderodde.util.sorting.AdaptiveCountingSort;

public class Demo {

    private static final int LENGTH = 10_000_000;

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

    private static void testSin() {
        System.out.println("testSin():");
        int[] array1 = new int[LENGTH];

        for (int i = 0; i < array1.length; ++i) {
            array1[i] = (int)(20_000 * Math.sin(1.0 * i / 100_000));
        }

        int[] array2 = array1.clone();

        long startTime = System.currentTimeMillis();
        AdaptiveCountingSort.sort(array1, 10, array1.length - 10);
        long endTime = System.currentTimeMillis();

        System.out.println("Adaptive counting sort in " + (endTime - startTime) +
                           " milliseconds.");

        startTime = System.currentTimeMillis();
        Arrays.sort(array2, 10, array2.length - 10);
        endTime = System.currentTimeMillis();

        System.out.println("Arrays.sort in " + (endTime - startTime) + 
                           " milliseconds.");

        System.out.println("Equal: " + Arrays.equals(array1, array2));
    }
}

The performance figures may be as optimistic as this:

testSin():
Adaptive counting sort in 76 milliseconds.
Arrays.sort in 633 milliseconds.
Equal: true

Please, tell me anything that comes to mind.

\$\endgroup\$

Your Answer

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

Browse other questions tagged or ask your own question.