3.1. Abstraction

The abstract class for all sorting algorithms.

Abstract Sort

Let us create an abstract class AbstractSort:

public abstract class AbstractSort<T extends Comparable<T>> {
    private final Comparator<T> comparator;
    protected long comparisons;
    protected long assignments;

    /** @param comparator specifies the precedence of comparable keys. */
    public AbstractSort(Comparator<T> comparator) {
        this.comparator = comparator;
        resetCounts();
    }

    /** @return the total number of comparisons performed during sort. */
    public long getComparisonCount() {
        return comparisons;
    }

    /** @return the total number of assignments performed during sort. */
    public long getAssignmentCount() {
        return assignments;
    }

    public void resetCounts() {
        comparisons = assignments = 0;
    }
}

• L2-4: member fields:

  • comparator: specifies the precedence of comparable keys.

  • comparisons: counts the number of comparisons performed during sorting.

  • assignments: counts the number of assignments performed during sorting.

The two-member fields, comparisons and assignments, are used to micro-benchmark sorting algorithms inheriting AbstractSort.

Let us define three helper methods, compareTo(), assign(), and swap():

/**
 * @param array an array of comparable keys.
 * @param i     the index of the first key.
 * @param j     the index of the second key.
 * @return array[i].compareTo(array[j]).
 */
protected int compareTo(T[] array, int i, int j) {
    comparisons++;
    return comparator.compare(array[i], array[j]);
}

/**
 * array[index] = value.
 * @param array an array of comparable keys.
 * @param index the index of the array to assign.
 * @param value the value to be assigned.
 */
protected void assign(T[] array, int index, T value) {
    assignments++;
    array[index] = value;
}

/**
 * Swaps array[i] and array[j].
 * @param array an array of comparable keys.
 * @param i     the index of the first key.
 * @param j     the index of the second key.
 */
protected void swap(T[] array, int i, int j) {
    T t = array[i];
    assign(array, i, array[j]);
    assign(array, j, t);
}

• L7: compares two keys in the array and increments the count.

• L18: assigns the value to the specific position in the array and increments the count.

• L29: swaps the values of the specific positions in the array by calling the assign() method.

These helper methods allow us to analyze the exact counts of those operations performed by different sorting algorithms.

How is it different to benchmark runtime speeds from counting these two operations?

Finally, let us define the default sort() that calls an overwritten abstract method, sort():

/**
 * Sorts the array in ascending order.
 * @param array an array of comparable keys.
 */
public void sort(T[] array) {
   sort(array, 0, array.length);
}

/**
 * Sorts the array[beginIndex:endIndex].
 * @param array      an array of comparable keys.
 * @param beginIndex the index of the first key to be sorted (inclusive).
 * @param endIndex   the index of the last key to be sorted (exclusive).
 */
abstract public void sort(T[] array, int beginIndex, int endIndex);

• L5: calls the abstract method sort() that overwrites it.

• L15: sorts the array in the range of (beginIndex, endIndex) as specified in comparator.

When would it be useful to sort a specific range in the input array?