Unlike comparison-based algorithms in Sections 3.2 and 3.3, distribution-based sorting algorithms do not make comparisons between keys in the input array; instead, they distribute keys into ordered buckets and merge keys in the buckets.

Bucket Sort

Let us create an abstract class, AbstractBucketSort inheriting AbstractSort:

public abstract class BucketSort<T extends Comparable<T>> extends AbstractSort<T> {
    protected List<Deque<T>> buckets;

    /** @param numBuckets the total number of buckets. */
    public BucketSort(int numBuckets) {
        super(null);
        buckets = Stream.generate(ArrayDeque<T>::new).limit(numBuckets).collect(Collectors.toList());
    }
}

• L2: declares a list of buckets where each bucket is represented by a Deque.

• L6: does not pass any comparator to AbstractSort since no comparison is needed.

• L7: creates a pre-defined number of buckets.

What kind of input keys can work with distribution-based sorting algorithms?

We then define a helper method sort():

/**
 * @param array       the input array.
 * @param beginIndex  the index of the first key to be sorted (inclusive).
 * @param endIndex    the index of the last key to be sorted (exclusive).
 * @param bucketIndex takes a key and returns the index of the bucket that the key to be added.
 */
protected void sort(T[] array, int beginIndex, int endIndex, Function<T, Integer> bucketIndex) {
    // add each element in the input array to the corresponding bucket
    for (int i = beginIndex; i < endIndex; i++)
        buckets.get(bucketIndex.apply(array[i])).add(array[i]);

    // merge elements in all buckets to the input array
    for (Deque<T> bucket : buckets) {
        while (!bucket.isEmpty())
            array[beginIndex++] = bucket.remove();
    }
}

• L7: bucketIndex is a function that takes a comparable key and returns the appropriate bucket index of the key.

• L9-10: adds the keys within the range in the input array to the buckets.

• L13-16: puts all keys in the buckets back to the input array while keeping the order.

How many assignments are made by the sort() method in BucketSort?

Integer Bucket Sort

Let us create the IntegerBucketSort class inheriting BucketSort that sorts integers within a specific range in ascending order:

public class IntegerBucketSort extends BucketSort<Integer> {
    private final int MIN;

    /**
     * @param min the minimum integer (inclusive).
     * @param max the maximum integer (exclusive).
     */
    public IntegerBucketSort(int min, int max) {
        super(max - min);
        MIN = min;
    }
}

• L2: takes the smallest integer in the range.

• L8: passes the number of buckets, max - min, to be initialized to the super constructor.\

We then override the sort() method:

@Override
public void sort(Integer[] array, int beginIndex, int endIndex) {
    sort(array, beginIndex, endIndex, key -> key - MIN);
}

• L3: passes a lambda expression that takes key and returns key - MIN indicating the index of the bucket that key should be assigned to.

Is it possible to implement DoubleBucketSort that can handle double instead of integer keys?

Radix Sort

Let us create an abstract class, RadixSort, inheriting BucketSort<Integer>:

public abstract class RadixSort extends BucketSort<Integer> {
    public RadixSort() {
        super(10);
    }
    
    protected int getMaxBit(Integer[] array, int beginIndex, int endIndex) {
        Integer max = Arrays.stream(array, beginIndex, endIndex).reduce(Integer::max).orElse(null);
        return (max != null && max > 0) ? (int)Math.log10(max) + 1 : 0;
    }
}

• L3: creates 10 buckets to sort any range of integers.

• L6: returns the order of the most significant digit in the input array.

LSD Radix Sort

Let us create the LSDRadixSort class inheriting RadixSort that sorts the integer keys from the least significant digit (LSD) to the most significant digit (MSD):

public class LSDRadixSort extends RadixSort {
    @Override
    public void sort(Integer[] array, int beginIndex, int endIndex) {
        int maxBit = getMaxBit(array, beginIndex, endIndex);
        for (int bit = 0; bit < maxBit; bit++) {
            int div = (int)Math.pow(10, bit);
            sort(array, beginIndex, endIndex, key -> (key / div) % 10);
        }
    }
}

• L5: iterates from LSD to MSD.

Benchmarks

The followings compare runtime speeds between advanced sorting algorithms where the input arrays consist of random integer keys:

Selection-based Sort

Selection-based sorting algorithms take the following steps:

• For each key $A_i$ where $|A| = n$ and $i \in [n, 0)$:

  • Search the maximum key $A_m$ where $m \in [1, i)$.

  • Swap $A_i$ and $A_m$

The complexities differ by different search algorithms:

Selection Sort uses linear search to find the minimum (or maximum) key, whereas Heap Sort turns the input array into a heap, so the search complexity becomes $O(\log n)$ instead of $O(n)$ .

Can the search be faster than $O(\log n)$?

Selection Sort

Let us create the SelectionSort class inheriting AbstractSort:

public class SelectionSort<T extends Comparable<T>> extends AbstractSort<T> {
    public SelectionSort() {
        this(Comparator.naturalOrder());
    }

    public SelectionSort(Comparator<T> comparator) {
        super(comparator);
    }
}

Let us then override the sort() method:

@Override
public void sort(T[] array, final int beginIndex, final int endIndex) {
    for (int i = endIndex; i > beginIndex; i--) {
        int max = beginIndex;

        for (int j = beginIndex + 1; j < i; j++) {
            if (compareTo(array, j, max) > 0)
                max = j;
        }

        swap(array, max, i - 1);
    }
}

How does the sort() method work with Comparator.reverseOrder()?

Heap Sort

Let us create the HeapSort class inheriting AbstractSort:

public class HeapSort<T extends Comparable<T>> extends AbstractSort<T> {
    public HeapSort() {
        this(Comparator.naturalOrder());
    }

    public HeapSort(Comparator<T> comparator) {
        super(comparator);
    }
}

Before we override the sort() method, let us define the following helper methods:

private void sink(T[] array, int k, int beginIndex, int endIndex) {
    for (int i = getLeftChildIndex(beginIndex, k); i < endIndex; k = i, i = getLeftChildIndex(beginIndex, k)) {
        if (i + 1 < endIndex && compareTo(array, i, i + 1) < 0) i++;
        if (compareTo(array, k, i) >= 0) break;
        swap(array, k, i);
    }
}

private int getParentIndex(int beginIndex, int k) {
    return beginIndex + (k - beginIndex - 1) / 2;
}

private int getLeftChildIndex(int beginIndex, int k) {
    return beginIndex + 2 * (k - beginIndex) + 1;
}

• L1-7: finds the right position of the k'th key by using the sink operation.

• L9-11: finds the parent index of the k'th key given the beginning index.

• L13-15: finds the left child index of the k'th key given the beginning index.

How is this sink() method different from the one in the BinaryHeap class?

Finally, we override the sort() method:

@Override
public void sort(T[] array, int beginIndex, int endIndex) {
    // heapify all elements
    for (int k = getParentIndex(beginIndex, endIndex - 1); k >= beginIndex; k--)
        sink(array, k, beginIndex, endIndex);

    // swap the endIndex element with the root element and sink it
    while (endIndex > beginIndex + 1) {
        swap(array, beginIndex, --endIndex);
        sink(array, beginIndex, beginIndex, endIndex);
    }
}

What is the worst-case scenario for Selection Sort and Heap Sort?

Insertion-based Sort

Insertion-based sorting algorithms take the following steps:

The complexities differ by different sequences:

Insertion Sort

Let us create the InsertionSort class inheriting AbstractSort:

public class InsertionSort<T extends Comparable<T>> extends AbstractSort<T> {
    public InsertionSort() {
        this(Comparator.naturalOrder());
    }

    public InsertionSort(Comparator<T> comparator) {
        super(comparator);
    }
}

Let us then define an auxiliary method, sort():

protected void sort(T[] array, int beginIndex, int endIndex, final int h) {
    int begin_h = beginIndex + h;

    for (int i = begin_h; i < endIndex; i++)
        for (int j = i; begin_h <= j && compareTo(array, j, j - h) < 0; j -= h)
            swap(array, j, j - h);
}

• L6: swaps the two keys.

Given the auxiliary method, the sort() method can be defined as follows where h = 1:

@Override
public void sort(T[] array, int beginIndex, int endIndex) {
    sort(array, beginIndex, endIndex, 1);
}

How many swaps does Insertion Sort make for the following array? [7, 1, 2, 3, 4, 5, 6, 14, 8, 9, 10, 11, 12, 13, 0]

Shell Sort

Gap Sequence

Shell Sort groups keys whose gap is defined by a particular gap sequence:

For the above example, by using the Hibbard sequence, it first groups keys whose gap is 7:[7, 14, 0], [1, 8], [2, 9], [3, 10], [4, 11], [5, 12], [6, 13]

It then sorts each group using Insertion Sort, which results in the following array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

The above procedure is repeated for gaps 3 and 1; however, the array is already sorted, so no more swapping is necessary.

Implementation

Let us create an abstract class, ShellSort, inheriting AbstractSort:

public abstract class ShellSort<T extends Comparable<T>> extends InsertionSort<T> {
    protected List<Integer> sequence;

    public ShellSort(Comparator<T> comparator) {
        super(comparator);
        sequence = new ArrayList<>();
        populateSequence(10000);
    }
}

• L2: stores a particular gap sequence.

• L7: pre-populate the gap sequence that can handle the input size up to 10000.

Then, let us define two abstract methods, populateSequence() and getSequenceStartIndex():

/**
 * Populates the gap sequence with respect to the size of the list.
 * @param n the size of the list to be sorted.
 */
protected abstract void populateSequence(int n);

/**
 * @param n the size of the list to be sorted.
 * @return the starting index of the sequence with respect to the size of the list.
 */
protected abstract int getSequenceStartIndex(int n);

• L5: populates a particular sequence for the input size n.

• L11: returns the index of the first gap to be used given the input size n.

Let us then override the sort() method:

@Override
 public void sort(T[] array, int beginIndex, int endIndex) {
     int n = endIndex - beginIndex;
     populateSequence(n);

     for (int i = getSequenceStartIndex(n); i >= 0; i--)
         sort(array, beginIndex, endIndex, sequence.get(i));
 }

• L4: should not re-populate the sequence unless it has to.

• L7: sorts the gap group by using the auxiliary method.

Knuth Sequence

Let us create the ShellSortKnuth class that populates the Knuth Sequence for ShellSort:

public class ShellSortKnuth<T extends Comparable<T>> extends ShellSort<T> {
    public ShellSortKnuth() {
        this(Comparator.naturalOrder());
    }

    public ShellSortKnuth(Comparator<T> comparator) {
        super(comparator);
    }
}

The two abstract methods can be overridden as follows:

@Override
protected void populateSequence(int n) {
    n /= 3;

    for (int t = sequence.size() + 1; ; t++) {
        int h = (int) ((Math.pow(3, t) - 1) / 2);
        if (h <= n) sequence.add(h);
        else break;
    }
}

@Override
protected int getSequenceStartIndex(int n) {
    int index = Collections.binarySearch(sequence, n / 3);
    if (index < 0) index = -(index + 1);
    if (index == sequence.size()) index--;
    return index;
}

Demonstration

Unit Tests & Benchmarks

The codes for unit testing and benchmarking are available in SortTest:

Contents

1. Abstraction

2. Comparison-based Sort

3. Divide & Conquer Sort

4. Distribution-based Sort

5. Quiz

6. Homework

Resources

• Main: src/main/java/edu/emory/cs/sort

• Test: src/test/java/edu/emory/cs/sort

References

• Comparison-based Algorithms

  • Selection Sort $\rightarrow$ Heap Sort

  • Insertion Sort $\rightarrow$ Shell Sort

• Divide and Conquer Algorithms

  • Merge Sort $\rightarrow$ Tim Sort

  • Quick Sort $\rightarrow$ Intro Sort

• Distribution-based Algorithms

  • Bucket Sort

  • Radix Sort

Abstract Sort

Let us create an abstract class :

• 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.

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

• 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():

• 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?

Coding

Shell Sort: Hibbard

• Create the class under the package that inherits .

• Override the populateSequence() and getSequenceStartIndex() methods such that it performs Shell Sort by using the Hibbard sequence: .

• Feel free to use the code in .

Radix Sort: MSD

• Create the class under the package that inherits .

• Override the sort() method such that it performs Radix Sort from the most significant digit (MSD) to the least significant digit (LSD).

• Feel free to use the code in .

Testing

• Create the class under the test package.

• Test the correctness of your TernaryHeapQuiz using the method.

• Add more tests for a more thorough assessment if necessary.

Benchmarking

• Compare runtime speeds between LSDRadixSort and RadixSortQuiz for random cases.

• Create a PDF file quiz3.pdf and write a report that includes charts and explanations to compare runtime speeds between:

  • ShellSortKnuth and ShellSortQuiz.

  • LSDRadixSort and RadixSortQuiz.

Submission

• Push everything under the sort package to your GitHub repository:
• Submit quiz3.pdf to Canvas.

Divide & Conquer

• Divide the problem into sub-problems (recursively).

• Conquer sub-problems, which effectively solve the super problem.

Why do people ever want to use QuickSort?

Merge Sort

• Divide the input array into two sub-arrays.

• Sort each of the sub-arrays and merge them into the back.

Let us create the class inheriting AbstractSort:

• L2: holds the copy of the input array.

Let us then override the sort() method that calls the helper method:

• L4-5: increases the size of the temp array if necessary.

  • L5: unchecked type Object to T[].

What is the advantage of declaring the member field temp?

The helper method can be defined as follows:

• L11: sorts the left sub-array.

• L12: sorts the right sub-array.

• L13: merges the left and right sub-arrays.

Finally, the merge() method can be defined as follows:

• L10-11: copies the input array to the temporary array and counts the assignments.

• L14-15: no key left in the 1st half.

• L16-17: no key left in the 2nd half.

• L18-19: the 2nd key is greater than the 1st key.

• L20-21: the 1st key is greater than or equal to the 2nd key.

Quick Sort

• Pick a pivot key in the input array.

• Exchange keys between the left and right partitions such that all keys in the left and right partitions are smaller or bigger than the pivot key, respectively.

• Repeat this procedure in each partition, recursively.

Let us then override the sort() method:

• L3: stops when the pointers are crossed.

• L6: sorts the left partition.

• L7: sorts the right partition.

The partition() method can be defined as follows:

• L5: finds the left pointer where endIndex > fst > pivot.

• L6: finds the right pointer where beginIndex < snd < pivot.

• L7: the left and right pointers are crossed.

• L8: swaps between keys in the left and right partitions.

• L11: swaps the keys in the beginIndex and pivot.

Intro Sort

How can we determine if Quick Sort is meeting the worse-case?

Let us define the IntroSoft class inheriting QuickSort:

• L2: declares a sorting algorithm to handle the worst cases.

• L14: resets the counters for both the main and auxiliary sorting algorithms.

We then override the sort() method by passing the maximum depth to the auxiliary method:

Finally, the auxiliary method sort() can be defined as follows:

• L4-5: switches to the other sorting algorithm if the depth of the partitioning exceeds the max depth.

Benchmarks

The following shows runtime speeds, assignment costs, and comparison costs between several sorting algorithms for the random, best, and worst cases.

Hybrid Sort

Your task is to write a program that sorts a 2D-array of comparable keys into an 1D-array where all the keys are sorted in ascending order. Here is a sample input to your program:

Here is the expected output given the sample input:

Each row in the input array has one of the following properties:

• Sorted in ascending order (e.g., the 1st row).

• Sorted in descending order (e.g., the 2nd row).

• Mostly sorted in ascending order (e.g., the 3rd row).

• Mostly sorted in descending order (e.g., the 4th row).

• Randomly distributed (e.g., the 5th row).

The easiest way is to merge all rows in the input array into an 1D-array then sort it using . The implementation of this strategy is provided to establish the baseline: . Your goal is to design a sorting mechanism that gives a noticeable speed-up over this baseline.

Tasks

• • Try different input arrays; you are responsible for the robustness of your program.

  • Try different configurations for speed comparison (e.g., row size, column size, shuffle ratio).

• Write the report hw1.pdf describing the logic behind your mechanism and the speed comparison against the baseline.

Submission

• Submit hw1.pdf to Canvas.

Notes

• You are not allowed to:

  • Use any implementation that is not written by you nor provided by this course.

  • Call any sorting methods built-in Java or 3rd-party libraries.

  • Merge all rows first and apply a fancy sorting algorithm to the 1D array as the baseline does.

• The input matrix can:

  • Contain an arbitrary number of rows, where the size of each row is also arbitrary.

Results

Baseline: 20697

• Cannot run: 7

• Extremely slow: 6

• Code not found: 1