# Comparison Sorts

## 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) {
}
``````

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.

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

Explanation

Each iteration of selection sort will search for the smallest element in the unsorted portion of the array. It will then put that element in its final sorted position.

On the first iteration, we will find the value 0 at index 2 to be the smallest element and swap it with the item at index 0.

### Question 2

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

Explanation

On the second iteration, we will find the value 1 at index 2 to be the smallest element and swap it with the item at index 1.

### Question 3

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

Explanation

On the third iteration, we will find the value 4 at index 4 to be the smallest element and swap it with the item at index 2.

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

Explanation

On the first iteration of insertion sort, we don’t have to do anything since we are trying to insert the first value (1 at index 0) into the empty sorted section. So there’s nothing to swap in the first iteration!

### Question 2

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

Explanation

The two values at the front of the array, 1 and 9, are still sorted with respect to each other. So there’s nothing to swap in the second iteration either!

### Question 3

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

Explanation

Now we’re examining index 2 as the beginning of the unsorted portion of the array. We select the element 0, and insert it into the proper index in our sorted portion. Note that after 3 iterations, we now have the first 3 elements sorted!

## 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
Explanation

Verify your answer by running both sorts and stopping after 3 iterations.

Selection sort
``````[5, 2, 1, 4, 3]
[1, 2, 5, 4, 3]
[1, 2, 5, 4, 3]
[1, 2, 3, 4, 5] <--
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
``````
Insertion sort
``````[5, 2, 1, 4, 3]
[5, 2, 1, 4, 3]
[2, 5, 1, 4, 3]
[1, 2, 5, 4, 3] <--
[1, 2, 4, 5, 3]
[1, 2, 3, 4, 5]
``````

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

Explanation

Remove the minimum value 1 and move it to the end of the array with the new spot that opens up after swapping and sinking the last element (the value 5).

### Question 2

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

Explanation

Remove the minimum value 2 and move it to the end of the array with the new spot that opens up after swapping and sinking the last element (the value 5).

### Question 3

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

Explanation

Remove the minimum value 3 and move it to the end of the array with the new spot that opens up after swapping and sinking the last element (the value 5).

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