Comparison Sorts

Table of contents

1. Sorting definitions
2. Selection sort
3. Selection sort demo
4. Insertion sort
5. Insertion sort demo
6. Heap sort
7. Heap construction
8. Heap sort demo
9. Selection sort invariant
10. Insertion sort invariant
11. Selection vs insertion sort
12. Min-heap sort

Sorting definitions

Selection sort

Selection sort demo

Insertion sort

Insertion sort demo

Heap sort

Heap construction

The simplest way to construct a heap is to repeatedly add each element to the binary heap data structure.

PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 100; i >= 0; i -= 1) {
    pq.add(i);
}

Each call to add puts the element at the end of the array and calls swim to swap each element up to the root. The worst-case runtime for top-down heapification is in Θ(Nlog N). Each leaf node potentially needs to swim all the way up to the overall root.

Bottom-up heapification. Floyd’s buildHeap is a specialized algorithm that takes a given array and constructs a binary heap in-place. Instead of adding elements to one big heap, the algorithm works by successively building up larger heaps from smaller ones using sink—not swim—to build-up larger heaps.

The following demo shows this bottom-up heapification approach:

1. 3-node heaps are built-up by taking two leaf nodes and sinking their shared parent.
2. 7-node heaps are built-up by taking two 3-node heaps and sinking their shared parent.
3. And so forth.

The worst-case runtime for this bottom-up heapification approach is in Θ(N) using mathematics beyond the scope of this course. Here’s an informal/intuitive explanation: unlike top-down heapification that needed to swim every leaf node, in bottom-up heapification only a single node (the overall root) needs to sink log N levels—most of the leaves and lower-level nodes don’t need to sink very far at all.

The following video is optional; all you have to know is that bottom-up heapification is a linear-time algorithm for creating a heap from a given array of elements in-place.

Heap sort demo

Selection sort invariant

Assume we have the following elements that need to be sorted:

[1, 9, 0, 5, 4, 7]

Selection sort invariant. After k iterations of the loop, the k-smallest elements of the array will be sorted.

Question 1

What order will the elements be in after 1 iteration of selection sort?

Question 2

What order will the elements be in after 2 iterations of selection sort?

Question 3

What order will the elements be in after 3 iterations of selection sort?

Question 4

A sorting algorithm is stable if the relative order of equivalent keys is maintained after sorting. Is selection sort a stable sort? Why or why not?

Insertion sort invariant

Assume we have the following elements that need to be sorted:

[1, 9, 0, 5, 4, 7]

Insretion sort invariant. After k iterations of the loop, the first k elements of the array will be sorted.

Question 1

What order will the elements be in after 1 iteration of insertion sort?

Question 2

What order will the elements be in after 2 iterations of insertion sort?

Question 3

What order will the elements be in after 3 iterations of insertion sort?

Selection vs insertion sort

Let’s compare and contrast selection sort vs. insertion sort!

Question 1

Suppose we’re given this list of numbers.

[5, 2, 1, 4, 3]

Then, we run 3 iterations of either selection sort or insertion sort.

[1, 2, 5, 4, 3]

Based on this intermediate state, which sort is being run?

• Selection sort
• Insertion sort
• Not able to determine from the provided information

Question 2

Considering a more general version of the preceding question: What is a general rule or a hint you can use to tell the difference between selection sort and insertion sort based on the intermediate state of the arrays?

It’s not always possible to tell the sorts apart based on the intermediate state. Both sorts will look the same if you run them on a list that is already sorted. This question is just asking you to explain a more general pattern to help you in the cases you can tell them apart.

Question 3

Explain the best-case runtimes for selection sort and insertion sort.

Min-heap sort

The following questions will concern the implementation of in-place heap sort. We’ll assume that we use the bottom-up heapification algorithm to create a min-heap and then repeatedly removeMin from the heap. The resulting array will be in reverse sorted order, so we’ll need to reverse it at the end of the sorting procedure.

Consider the following (already heapified) array representation of a 5-element min-heap.

[1, 2, 4, 3, 5]

Question 1

What order will the elements be in after 1 iteration of heap sort?

Question 2

What order will the elements be in after 2 iterations of heap sort?

Question 3

What order will the elements be in after 3 iterations of heap sort?

Question 4

Just like selection sort, heap sort is not stable. Give a small example (at most 5 elements) that results in an unstable heap sort. Assume that we’re using the max-heap variant of heap sort that does not need to reverse the array at the end of the sorting procedure.