Announcements

If you earned a low score on project 2, do not worry too much.

• I’ll be taking a close look tomorrow at students who were unable to complete the assignment.
• If there’s a clear need, I’ll create a mechanism for awarding partial credit for what you did finish, even if you didn’t pass the autograder tests.
• This may take some time.

datastructur.es

Announcements

We are now in Phase 3 of the course:

• Algorithms and Software Engineering.

​

Lectures in this phase:

• Algorithms.
• 3 software engineering lectures (we already did #1).

​

Optional textbook for software engineering lectures: “A Philosophy of Software Design” by John Ousterhout.

​

datastructur.es

Announcements

We are now in Phase 3 of the course:

• Algorithms and Software Engineering.

​

Only one assignment in this phase: Project 3: Build Your Own World

• (partners required except by exception).
• Second chance to do some software engineering (after project 2B).
• Lots more design practice.
• You’ll decide your own task and approach.
• Includes “class design” (picking classes) AND data structure selection.
• Just like project 2B, your choices will make a huge difference in code efficiency as well as ease of writing code.

datastructur.es

CS61B, 2023

Lecture 29: Sorting I

• The Sorting Problem
• Selection Sort, Heapsort
• Mergesort
• Insertion Sort
• Shell’s Sort (Extra)

datastructur.es

Our Major Focus for Several Lectures: Sorting

For many of our remaining lectures, we’ll discuss the sorting problem.

• Informally: Given items, put them in order.

​

This is a useful task in its own right. Examples:

• Equivalent items are adjacent, allowing rapid duplicate finding.
• Items are in increasing order, allowing binary search.
• Can be converted into various balanced data structures (e.g. BSTs, KdTrees).

​

Also provide interesting case studies for how to approach basic computational problems.

• Some of the solutions will involve using data structures we’ve studied.

datastructur.es

Sorting - Definitions (from Donald Knuth’s TAOCP)

An ordering relation < for keys a, b, and c has the following properties:

• Law of Trichotomy: Exactly one of a < b, a = b, b < a is true.
• Law of Transitivity: If a < b, and b < c, then a < c.

​

An ordering relation with the properties above is also known as a “total order”.

​

A sort is a permutation (re-arrangement) of a sequence of elements that puts the keys into non-decreasing order relative to a given ordering relation.

• x₁ ≤ x₂ ≤ x₃≤ ...≤ x_N

datastructur.es

Example: String Length

Example of an ordering relation: The length of strings.

• Law of Trichotomy: Exactly one of the following is true:
• len(a) < len(b)
• len(a) = len(b)
• len(b) < len(a)
• Law of Transitivity: If len(a) < len(b) and len(b) < len(c), then len(a) < len(c).

​

Two valid sorts for [“cows”, “get”, “going”, “the”] for the ordering relation above:

• [“the”, “get”, “cows”, “going”]
• [“get”, “the”, “cows”, “going”]

​

Under this relation, “the” is considered = to “get”, since len(“the”) = len(“get”).

= under the relation, not the Java idea of .equals

datastructur.es

Java Note

Ordering relations are typically given in the form of compareTo or compare methods.

​

​

​

​

​

​

�Note that with respect to the order defined by the method above “the” = “get”.

• This usage of = is not the same as the equals given by the String method.

import java.util.Comparator;

public class LengthComparator implements Comparator<String> {

public int compare(String x, String b) {

return x.length() - b.length();

}

}

datastructur.es

Sorting: An Alternate Viewpoint

An inversion is a pair of elements that are out of order with respect to <.

Another way to state the goal of sorting:

• Given a sequence of elements with Z inversions.
• Perform a sequence of operations that reduces inversions to 0.

0 1 1 2 3 4 8 6 9 5 7

8-6 8-5 8-7 6-5 9-5 9-7

​

(6 inversions out of 55 max)

Gabriel Cramer

Yoda

datastructur.es

Performance Definitions

Characterizations of the runtime efficiency are sometimes called the time complexity of an algorithm. Example:

• Dijkstra’s has time complexity O(E log V).

​

Characterizations of the “extra” memory usage of an algorithm is sometimes called the space complexity of an algorithm.

• Dijkstra’s has space complexity Θ(V) (for queue, distTo, edgeTo).
• Note that the graph takes up space Θ(V+E), but we don’t count this as part of the space complexity of Dijkstra since the graph itself already exists and is an input to Dijkstra’s.

datastructur.es

Selection Sort and Heapsort

datastructur.es

Selection Sort

We’ve seen this already.

• Find smallest item.
• Swap this item to the front and ‘fix’ it.
• Repeat for unfixed items until all items are fixed.
• Demo: https://goo.gl/g14Cit

​

Sort Properties:

• Θ(N²) time if we use an array (or similar data structure).

​

Seems inefficient: We look through entire remaining array every time to find the minimum.

datastructur.es

Naive Heapsort: Leveraging a Max-Oriented Heap

Idea: Instead of rescanning entire array looking for minimum, maintain a heap so that getting the minimum is fast!

​

For reasons that will become clear soon, we’ll use a max-oriented heap.

​

Naive heapsorting N items:

• Insert all items into a max heap, and discard input array. Create output array.
• Repeat N times:
• Delete largest item from the max heap.
• Put largest item at the end of the unused part of the output array.

​

Naive Heapsort Demo: https://goo.gl/EZWwSJ

​

A min heap would work as well, but wouldn’t be able to take advantage of the fancy trick in a few slides.

datastructur.es

Naive Heapsort Runtime

Naive heapsorting N items:

• Insert all items into a max heap, and discard input array. Create output array.
• Repeat N times:
• Delete largest item from the max heap.
• Put largest item at the end of the unused part of the output array.

​

What is the TOTAL runtime of naive heapsort?

1. Θ(N)
2. Θ(N log N)
3. Θ(N²), but faster than selection sort.

datastructur.es

Heapsort Runtime Analysis

Use the magic of the heap to sort our data.

• Getting items into the heap O(N log N) time.
• Selecting largest item: Θ(1) time.
• Removing largest item: O(log N) for each removal.

​

Overall runtime is O(N log N) + Θ(N) + O(N log N) = O(N log N)

• Far better that selection sort!

​

Memory usage is Θ(N) to build the additional copy of all of our data.

• Worse than selection sort, but probably no big deal (??).
• Can eliminate this extra memory cost with same fancy trickery.

datastructur.es

In Place Heapsort

datastructur.es

In-place Heapsort

Alternate approach, treat input array as a heap!

• Rather than inserting into a new array of length N + 1, use a process known as “bottom-up heapification” to convert the array into a heap.
• To bottom-up heapify, just sink nodes in reverse level order.
• Avoids need for extra copy of all data.
• Once heapified, algorithm is almost the same as naive heap sort.

​

​

​

​

​

In-place heap sort: Demo

32

15

2

17

19

26

41

17

17

41

19

32

17

15

26

2

17

17

heapification

For this algorithm we don’t leave spot 0 blank.

datastructur.es

In-place Heapsort Runtime

Use the magic of the heap to sort our data.

• Bottom-up Heapification: O(???) time.
• Selecting largest item: Θ(1) time.
• Removing largest item: O(log N) for each removal.

​

Give the time complexity of in-place heapsort in big O notation.

1. O(N)
2. O(N log N)
3. O(N²)

datastructur.es

In-place Heapsort Runtime

Use the magic of the heap to sort our data.

• Bottom-up Heapification: O(N log N) time.
• Selecting largest item: Θ(1) time.
• Removing largest item: O(log N) for each removal.

​

Give the time complexity of in-place heapsort in big O notation.

• O(N log N)

​

Bottom-up heapification is N sink operations, each taking no more than O(log N) time, so overall runtime for heapification is O(N log N).

• More extra for experts, show heapsort is Θ(N log N) in the worst case.

datastructur.es

In-place Heapsort

What is the memory complexity of Heapsort?

• Also called “space complexity”.
• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(N log N)
• Θ(N²)

​

datastructur.es

In-place Heapsort: http://yellkey.com/tell

What is the memory complexity of Heapsort?

• Also called “space complexity”.
• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(N log N)
• Θ(N²)

​

​

datastructur.es

In-place Heapsort

What is the memory complexity of Heapsort?

• Also called “space complexity”.
• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(N log N)
• Θ(N²)

​

The only extra memory we need is a constant number instance variables, e.g. size.

• Unimportant caveat: If we employ recursion to implement various heap operations, space complexity is Θ(log N) due to the need to track recursive calls. The difference between Θ(log N) and Θ(1) space is effectively nothing.

datastructur.es

Sorts So Far

*: An array of all duplicates yields linear runtime for heapsort.

**: Assumes heap operations implemented iteratively, not recursively.

datastructur.es

Mergesort (Review)

datastructur.es

Mergesort

We’ve seen this one before as well.

​

Mergesort: Demo

• Split items into 2 roughly even pieces.
• Mergesort each half (steps not shown, this is a recursive algorithm!)
• Merge the two sorted halves to form the final result.

​

Time complexity, analysis from previous lecture: Θ(N log N runtime)

• Space complexity with aux array: Costs Θ(N) memory.

​

Also possible to do in-place merge sort, but algorithm is very complicated, and runtime performance suffers by a significant constant factor.

datastructur.es

Sorts So Far

*: An array of all duplicates yields linear runtime for heapsort.

**: Assumes heap operations implemented iteratively, not recursively.

datastructur.es

Insertion Sort

Note: Based on Spring 2019 timing, it is unlikely we will finish this section. Thus we will probably finish this section on Wednesday.

datastructur.es

Insertion Sort

General strategy:

• Starting with an empty output sequence.
• Add each item from input, inserting into output at right point.

​

Naive approach, build entirely new output: Demo (Link)

​

32

15

2

17

19

26

41

17

17

Input:

Output:

datastructur.es

Insertion Sort

General strategy:

• Starting with an empty output sequence.
• Add each item from input, inserting into output at right point.

​

Naive approach, build entirely new output: Demo (Link)

​

32

15

2

17

19

26

41

17

17

Input:

Output:

32

15

2

17

19

26

41

17

17

datastructur.es

Insertion Sort

General strategy:

• Starting with an empty output sequence.
• Add each item from input, inserting into output at right point.

​

For naive approach, if output sequence contains k items, worst cost to insert a single item is k.

• Might need to move everything over.

​

More efficient method:

• Do everything in place using swapping: Demo (Link)

datastructur.es

In-place Insertion Sort

Two more examples.

7 swaps:

36 swaps:

P O T A T O

P O T A T O (0 swaps)

O P T A T O (1 swap )

O P T A T O (0 swaps)

A O P T T O (3 swaps)

A O P T T O (0 swaps)

A O O P T T (3 swaps)

S O R T E X A M P L E

S O R T E X A M P L E (0 swaps)

O S R T E X A M P L E (1 swap )

O R S T E X A M P L E (1 swap )

O R S T E X A M P L E (0 swaps)

E O R S T X A M P L E (4 swaps)

E O R S T X A M P L E (0 swaps)

A E O R S T X M P L E (6 swaps)

A E M O R S T X P L E (5 swaps)

A E M O P R S T X L E (4 swaps)

A E L M O P R S T X E (7 swaps)

A E E L M O P R S T X (8 swaps)

Purple: Element that we’re moving left (with swaps).

Black: Elements that got swapped with purple.

Grey: Not considered this iteration.

datastructur.es

Insertion Sort Runtime

What is the runtime of insertion sort?

1. Ω(1), O(N)
2. Ω(N), O(N)
3. Ω(1), O(N²)
4. Ω(N), O(N²)
5. Ω(N²), O(N²)

36 swaps:

datastructur.es

Insertion Sort Runtime

What is the runtime of insertion sort?

• Ω(1), O(N)
• Ω(N), O(N)
• Ω(1), O(N²)
• Ω(N), O(N²)
• Ω(N²), O(N²)

​

You may recall Ω is not “best case”.

So technnnniically you could also say � Ω(1)

​

36 swaps:

datastructur.es

Picking the Best Sort

Suppose we do the following:

• Read 1,000,000 integers from a file into an array of length 1,000,000.
• Mergesort these integers.
• Select one integer randomly and change it.
• Sort using algorithm X of your choice.

​

Which sorting algorithm would be the fastest choice for X?

1. Selection Sort
2. Heapsort
3. Mergesort
4. Insertion Sort

datastructur.es

Observation: Insertion Sort on Almost Sorted Arrays

For arrays that are almost sorted, insertion sort does very little work.

• Left array: 5 inversions, so only 5 swaps.
• Right array: 3 inversion, so only 3 swaps.

​

​

​

datastructur.es

Picking the Best Sort (Poll Everywhere)

Suppose we do the following:

• Read 1,000,000 integers from a file into an array of length 1,000,000.
• Mergesort these integers.
• Select one integer randomly and change it.
• Sort using algorithm X of your choice.
• In the worst case, we have 999,999 inversions: Θ(N) inversions.

​

Which sorting algorithm would be the fastest choice for X? Worst case run-times:

• Selection Sort: Θ(N²)
• Heapsort: Θ(N log N)
• Mergesort: Θ(N log N)
• Insertion Sort: Θ(N)

datastructur.es

Insertion Sort Sweet Spots

On arrays with a small number of inversions, insertion sort is extremely fast.

• One exchange per inversion (and number of comparisons is similar). Runtime is Θ(N + K) where K is number of inversions.
• Define an almost sorted array as one in which number of inversions ≤ cN for some c. Insertion sort is excellent on these arrays.

​

Less obvious: For small arrays (N < 15 or so), insertion sort is fastest.

• More of an empirical fact than a theoretical one.
• Theoretical analysis beyond scope of the course.
• Rough idea: Divide and conquer algorithms like heapsort / mergesort spend too much time dividing, but insertion sort goes straight to the conquest.
• The Java implementation of Mergesort does this (Link).

datastructur.es

Sorts So Far

datastructur.es

Shell’s Sort (Bonus)

(Not on Exam)

datastructur.es

Optimizing Insertion Sort: Shell’s Sort

Big idea: Fix multiple inversions at once.

• Instead of comparing adjacent items, compare items that are one stride length h apart.
• Start with large stride, and decrease towards 1.
• Example: h = 7, 3, 1.

Optimizing Insertion Sort: Shell’s Sort

7-sorting:

3-sorting:

3 swaps

5 swaps

1-sorting:

6 swaps

Total swaps: 14 (vs. 31)

S O R T E X A M P L E

M O R T E X A S P L E (1 swap, > 1 inversion)

M O R T E X A S P L E (0 swaps)

M O L T E X A S P R E (1 swap, > 1 inversion)

M O L E E X A S P R T (1 swap, > 1 inversion)

M O L E E X A S P R T

E O L M E X A S P R T (1 swap, >1 inversions)

E E L M O X A S P R T (1 swap, >1 inversions)

E E L M O X A S P R T (0 swaps, 0 inversions)

A E L E O X M S P R T (2 swaps, >1 inversions)

A E L E O X M S P R T (0 swaps, 0 inversions)

A E L E O P M S X R T (1 swaps, >1 inversions)

A E L E O P M S X R T (0 swaps, 0 inversions)

A E L E O P M S X R T (0 swaps, 0 inversions)

Example from Algorithms 4th Edition

A E L E O P M S X R T

A E L E O P M S X R T

A E L E O P M S X R T

A E L E O P M S X R T

A E E L O P M S X R T

A E E L O P M S X R T

A E E L O P M S X R T

A E E L M O P S X R T

A E E L M O P S X R T

A E E L M O P S X R T

A E E L M O P R S X T

A E E L M O P R S T X

Shell’s Sort: Generalization and Performance

h=1 is just normal insertion sort.

• By using large strides first, fixes most of the inversions.

​

We used 7, 3, 1. Can generalize to 2^k - 1 from some k down to 1.

• Requires Θ(N^1.5) time in the worst case (see CS170).
• Other stride patterns can be faster.

Sorts So Far

An earlier version of this slide assumed that Heapsort was always given an array with no duplicate elements. If we omit this assumption, heapsort’s best case is Θ(N).

​

datastructur.es

Citations

Lego man: http://thetechnicgear.com/wp-content/uploads/2014/02/sorting-lego.jpg

​

Keynote Animations of Algorithms courtesy of Kevin Wayne

datastructur.es