Algorithm Design

Quicksort, counting sorts, and binary heaps.

  1. Quicksort
    1. Partitioning
    2. Single-pivot quicksort
    3. Dual-pivot quicksort
  2. Counting Sorts
    1. Sorting decision tree
    2. Counting sorts and enumeration
    3. Radix sorts
    4. 3-way radix quicksort
  3. Binary Heaps
    1. Priority queue abstract data type
    2. Heap invariant
    3. Array representation

Quicksort

Quick.java

  1. Compare comparison sorting algorithms on efficiency and stability.
  2. Given the runtime of a partitioning algorithm, describe the runtime of quicksort.
  3. Describe the search trees analogies for quicksort algorithms.

Isomorphism not only inspires new ideas for data structures, but also new ideas for algorithms too. In our study of sorting algorithms, we learned that a sorting algorithm is considered stable if it preserves the original order of equivalent keys. Which sorting algorithms does Java use when you call Arrays.sort? It depends on whether we need stability.

Stable system sort
When sorting an array of objects (like emails), Java uses a sorting algorithm called Timsort, which is based on merge sort and has the same linearithmic worst-case runtime as merge sort.
Why is Timsort preferred over merge sort if they have the same worst-case runtime?

Timsort has the same worst-case asymptotic runtime as merge sort, but in experimental analysis it is often noticeably faster. It also has a linear-time best-case asymptotic runtime.

Timsort is a hybrid sort that combines ideas from merge sort with insertion sort. Experimental analysis reveals that the fastest sorting algorithm for small arrays is often insertion sort. Instead of merge sort’s base case of 1 element, Java Timsort uses a base case of 32 elements which are then insertion sorted. Insertion sort can be further sped up by using binary search to find the insertion point for the next unsorted element.

Timsort is also an adaptive sort that changes behavior depending on the input array. Many real-world arrays are not truly random. They often contain natural runs, or sorted subsequences of elements that could be efficiently merged. Rather than recursively dividing top-down, Timsort works bottom-up by identifying natural runs in the input array and combining them from left to right.

Unstable system sort
When sorting an array of numbers or booleans, Java uses a sorting algorithm called quicksort. Quicksort has many variants, but we’ll focus on two in this course:
  1. Single-pivot quicksort, which is isomorphic to binary search trees.
  2. Dual-pivot quicksort, which is like a 2-3 tree that only contains 3-nodes.

Partitioning

Quicksort relies on the idea of recursively partitioning an array around a pivot element, data[i].

A partitioning of an array rearranges its elements in a weaker way than sorting by requiring elements in the order:

  • All elements to the left of the pivot are less than or equal to the pivot element.
  • The pivot element, data[i], moves to position j. (The pivot might not need to move.)
  • All elements to the right of the pivot are greater than or equal to the pivot element.

Single-pivot quicksort

Partitioning an array around a pivot element in quicksort is like selecting a root element in a binary search tree. All the elements in the left subtree will be less than the root element, and all the elements in the right subtree will be greater than the root element.

Quicksort isomorphism to binary search trees

The quicksort on the left always chooses the leftmost element as the pivot element and uses an ideal partitioning that maintains the relative order of the remaining elements. The binary search tree on the right shows the result of inserting each element in the left-to-right input order given by the array.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose QUI from the top navigation bar to switch to quicksort. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization

Note that the visualization does not use an ideal partitioning algorithm for quicksort.

Dual-pivot quicksort

Dual-pivot quicksort chooses 2 pivots on each recursive call, just like how 3-child nodes in 2-3 trees maintain 2 keys and 3 children. If choosing 1 pivot element is like choosing 1 root element in a binary node, then choosing 2 pivot elements is like choosing 2 root elements in a 3-child node.

Strictly speaking, dual-pivot quicksort is not isomorphic to 2-3 trees because there does not exist a one-to-one correspondence. Consider 2-3 trees that only contain 2-child nodes: the corresponding quicksort is single-pivot quicksort, not dual-pivot quicksort.

Partitioning an array around 2 pivot elements, p1 and p2 where p1 ≤ p2, rearranges its elements by requiring elements in the order:

  • All elements less than p1.
  • The pivot element p1.
  • All elements x where p1 ≤ x ≤ p2.
  • The pivot element p2.
  • All elements greater than p2.

Dual-pivot quicksort is a relatively new algorithm published in 2009. Experimental analysis revealed that dual-pivot quicksort is significantly faster than single-pivot quicksort on modern computers. Computer scientists attribute the performance improvement due to advances in CPU caching and memory hierarchy since the 1960s and 1970s when single-pivot quicksort was first introduced.

Counting Sorts

MSD.javaLSD.java

  1. Explain the worst-case lower bound for comparison sorting.
  2. Describe counting sort, MSD radix sort, and LSD radix sort.
  3. Explain how the subsort is used in MSD and LSD radix sort.

In practice, Java’s system sorts like Timsort and dual-pivot quicksort have a linearithmic order of growth. Is it possible to sort in faster than worst case Θ(N log N) time? In the best case, we know that sorting algorithms like insertion sort can tell that an already-sorted array is indeed sorted in linear time. But can we design an algorithm that sorts an array of N elements in linear time in the worst case?

Sorting decision tree

We can start by asking, “How many comparisons do we need to make in order to know how to sort an array?” We’ve actually already asked this question before: in merge sort, we relied on knowing that a single element subarray is already sorted with respect to itself. In other words:

  • Sorting an array with 1 element requires 0 comparisons.
  • Sorting an array with 2 elements requires 1 comparison.
  • Sorting an array with 3 elements requires either 2 or 3 comparisons depending on the questions.

We can draw a sorting decision tree to see exactly what questions we need to ask to determine the sorted order for 3 elements. Each leaf in the decision tree represents a possible sorted order for the elements, and each branch represents a choice of answering either “Yes” or “No” to each comparison question.

Sorting decision tree for 3 elements

This decision tree is not only a conceptual visualization, but it can also be implemented as a program consisting of a hierarchy of nested if conditional statements. This decision tree represents the optimal comparison sorting algorithm: a comparison sort that requires the absolute least number of comparisons to sort a given input array.

if (a < b)
    if      (b < c) return {a, b, c};
    else if (a < c) return {a, c, b};
    else            return {c, a, b};
else
    if      (a < c) return {b, a, c};
    else if (b < c) return {b, c, a};
    else            return {c, b, a};
If 3 elements have 6 permutations, how many permutations are there for 4 elements?

For each of the 6 permutations in a, b, c, we can insert the fourth element d before, in-between, or after each element. For example, if we consider the permutation {a, b, c}, we can insert d in 4 different places: {d, a, b, c}, {a, d, b, c}, {a, b, d, c}, and {a, b, c, d}. Ultimately, we take the 6 permutations we had for 3 elements and multiply by 4 to get 24 total permutations for 4 elements. More generally, the number of permutations can be described using the factorial function: 4! = 4 ∙ 3 ∙ 2 ∙ 1.

If N elements have N! factorial potential permutations, and each potential permutation is a leaf in a balanced sorting decision tree, then the optimal comparison sorting algorithm in the worst case needs about log2 N! comparisons to determine the correct sorting of the elements. Stirling’s approximation can be used to show that log2 N! ∈ Θ(N log N).

In other words, the optimal comparison sorting algorithm requires Θ(N log N) comparisons in the worst case. It’s not possible to design a comparison sorting algorithm that takes linear time in the worst case.

Counting sorts and enumeration

The worst case lower bound on comparison sorting algorithms only apply to comparison sorts that use operations like <, >, or compareTo to determine the order of elements. A counting sort sorts an array of elements by relying on enumeration instead of comparison. Elements are considered comparable if they can be compared with one another. Elements are considered enumerable if they can be listed-out in a sequence from first to last.

Counting sort
  1. Create a count array that will be used to store the number of times each element occurs in the input array.
  2. Iterate over the input array, updating the count array to reflect the occurrence of each element.
  3. Iterate over the count array, unraveling the number of times each element occurs back into the input array.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose COU from the top navigation bar to switch to counting sort. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization

Radix sorts

Counting sorts work great with small integer values when we know the range between the smallest integer and the largest integer. But many other data types, like strings, are more difficult to enumerate because we can always make a more complicated string. For example, suppose we have a string “a” and we decide to put it at index 0 in the count array. Where would the string “b” belong in the count array? We know it comes after “a”, but how far after “a”? We might run into strings like “aa”, “aaa”, “aaaa”, etc. and not know how many spaces to reserve for these elements.

To address this issue, we can take inspiration from tries. Just as tries divided a string into its constituent letters and processed each letter individually, we can do the same and apply counting sort on each letter. Radix sorts represent a category of counting sorts that divide strings (or string-like objects) into individual subunits that can be separately counting-sorted.

Most-Significant Digit (MSD) radix sort
Starts from the leftmost (in English, the most significant) character and proceeds to the right.
Recursively counting sorts the characters separately, proceeding to the next index into the strings.
Least-Significant Digit (LSD) radix sort
Starts from the rightmost (in English, the least significant) character and proceeds to the left.
For each index into the strings, iteratively counting sorts all the elements again on the current index.

Open the VisuAlgo module to visualize sorting algorithms. Press Esc to exit the e-Lecture Mode, and choose RAD from the top navigation bar to switch to an LSD radix sort. Run the sorting algorithm using Sort from the bottom left menu.

Sorting Visualization

3-way radix quicksort

Is there a sorting algorithm analogy for ternary search trees? It exists, and it combines the ideas of radix sort with quicksort just like how ternary search trees represent a midpoint between tries and binary search trees.

3-way radix quicksort
Select a pivot element for the current index into the strings.
Partition the array into elements less than, equal to, and greater than the pivot element.
Recursively sort each of the less than, equal to, and greater than subarrays.

Binary Heaps

MinPQ.javaHeap.java

  1. Apply sink/swim operations to trace heap element insertion and removal.
  2. Identify possible binary heap indices for the n-th smallest value.
  3. Given an array index, find the parent, left child, and right child indexes.

Compared to binary search trees, 2-3 trees and left-leaning red-black trees provided two solutions to avoiding worst case height. But neither a 2-3 tree nor a left-leaning red-black tree maintain a perfectly-balanced binary search tree. A 2-3 tree maintains perfect balance, but needs 3-child nodes. A left-leaning red-black tree is a binary search tree, but it doesn’t maintain perfect balance: in the worst case, the left side can be up to double the height of the right side.

How do we even define perfect balance? One definition is called completeness.

Complete tree
A tree where every level, except possibly the last level, is completely filled. If the last level is not completely filled, all nodes must be as far left as possible.

It’s not easy maintaining a complete binary search tree: a tree that simultaneously satisfies all three of the definitions for a complete tree, a binary tree, and a search tree. In the worst case, adding a new element might require moving all its elements to new places.

Adding to a complete binary search tree

Of the tree data structures that we’ve studied, our best approaches only satisfy two out of three properties:

2-3 tree
A tree data structure that satisfies the definitions for a complete tree and a search tree, but it is not a binary tree.
LLRB tree
A tree data structure that satisfies the definitions for a binary tree and a search tree, but it is not a complete tree.

A binary heap is the final option in the 3-choose-2 data structure design.

Binary heap
A tree data structure that satisfies the definitions for a complete tree and a binary tree, but it is not a search tree.

What can we do with a binary tree without the search tree property? 2-3 trees and LLRB trees provided efficient implementations for sets and maps because of the combination of their search tree property and height invariants. Binary heaps instead implement a different abstract data type called priority queue.

Priority queue abstract data type

The priority queue is an abstract data type where elements are organized according to their associated priority values. Priority queues have direct real world applications. For example, they can be used to triage patients in a hospital emergency room. Rather than serving patients first-come, first-served (as in a regular queue), a priority queue can be used to ensure patients with the most severe or time-sensitive conditions are treated first even if someone else arrived earlier.

The min-oriented priority queue MinPQ interface supports 3 important operations:

void add(E element, double priority)
Adds the given element with the given priority value.
E peekMin()
Returns the element with the minimum priority value.
E removeMin()
Returns and removes the element with the minimum priority value.

Likewise, the max-oriented priority queue MaxPQ could be defined with methods that allow access to the element with the maximum priority value. Priority queues differ from sets in two ways.

  1. Multiple elements can share the same priority value. For example, two patients can be equally in need of care. Ties between priority value can go either way because either one is an element with the minimum (or maximum) priority value.
  2. In some implementations, duplicate elements are allowed. This doesn’t make sense for the emergency room application since you can’t have two copies of a person, but we’ll later see some algorithms that rely on storing duplicates.

Heap invariant

To implement a priority queue, binary heaps maintain a heap invariant that depends on whether the heap implements a MinPQ or a MaxPQ.

Min-heap invariant
The priority value of each node must be less than or equal to the priority values of all its children.
Max-heap invariant
The priority value of each node must be greater than or equal to the priority values of all its children.

For simplicity, our visualizations will only show the priority value. Implementations of the priority queue abstract data type typically require not just the priority value, but also the element associated with the priority value.

Implementing peekMin just requires returning the overall root element because the min-heap invariant ensures that the element with the minimum priority value will be stored at the very top of the tree.

Implementing removeMin, however, requires more work to maintain the completeness property.

  1. Swap the root with the last leaf.
  2. Remove the last leaf.
  3. Sink the new root to its proper place, promoting the lower-priority child.

Heaps defined two private helper methods called sink (percolate down) and swim (percolate up) that are used to restore heap invariants after the removal or addition of an element (respectively). The sink method repeatedly swaps the current node with the lower-priority child until heap invariants are restored. The swim method repeatedly swaps the current node with its parent until heap invariants are restored.

Finally, the add method can be implemented by adding the element to the next open position that maintains completeness before swimming the element to restore heap invariants.

Array representation

Despite all of this work, it turns out that binary heaps are not any more asymptotically efficient than using a balanced search tree like a 2-3 tree or a left-leaning red-black tree. In practice, the main advantage of using a binary heap to implement a priority queue is due to a way that we can represent the tree using an array.

Array representation is the default and assumed representation for a binary heap.

Node representation
Explicitly maintains tree structure through a hierarchy of references.
Only maintains parent-to-child references, which makes swim challenging to efficiently implement.
Array representation
Implicitly maintains tree structure through a mapping between array indices and tree location.
Both parent-to-child and child-to-parent indices can be computed using arithmetic.

The following slides and visualizations show a binary max-heap where the heap is organized around access to the maximum element at the top of the heap.

Open the VisuAlgo module to visualize binary max-heap operations. Press Esc to exit the e-Lecture Mode. Choose ExtractMax() from the bottom left menu and select 1x (Once) to see the result of removing the element associated with the maximum priority value. The red number under each node represents the index in the array representation of the tree.

Binary Heap Visualization