Announcements

Sorry about the lack of pre-recorded lectures.

• Have literally had no available time to do them lately. I will try my hardest to get back on track ASAP. Feedback on the surveys seems to think that the webcasts are OK (though not as good).

​

Seems unreasonable for students to spend 20 hours of time and earn almost no credit, so Project 2A/2B will have a point recovery policy. Details TBA.

datastructur.es

Announcements: yellkey.com/national

Sorry about the lack of pre-recorded lectures.

• Have literally had no available time to do them lately. I will try my hardest to get back on track ASAP. Feedback on the surveys seems to think that the webcasts are OK (though not as good).

​

Project 2A/2B will have a point recovery policy, but details TBA.

​

If you had two choices, which would you prefer? Assume your final score is the same either way:

1. Try again: One more submission to the autograder to fix your bugs.
2. Just let it go: Effort points where you get a fixed number of “effort” points added to your AG score.�

datastructur.es

Announcements

Phase 3 of the course starts today: Algorithms and Software Engineering.

​

Lectures in this phase:

• Algorithms on M/W.
• Software engineering on Friday.

​

Same optional textbook for M/W: “Algorithms” by Wayne/Sedgewick.

​

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

datastructur.es

Announcements

Phase 3 of the course starts today: Algorithms and Software Engineering.

​

Assignments in this phase:

• HW4: A* Algorithm (due Wednesday 4/10). This is relatively short if you’ve already understood A* from before the midterm.
• Project 2C: Bear Maps (due Wednesday 4/17). You combine your work from Proj2A, Proj2B, and HW4 into a mapping application. Hoping it’s not too big.
• Project 3: Build Your Own World (more soon).
• Partner project, so try to find a partner soon.

datastructur.es

CS61B

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 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: http://yellkey.com/couple

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

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: http://yellkey.com/response

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

• Extra for experts, show that bottom-up heapification is Θ(N) in the worst case.
• More extra for experts, show heapsort is Θ(N log N) in the worst case.

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: http://yellkey.com/tell

What is the memory complexity of Heapsort?

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

​

Incorrect answer given by student during lecture: Θ(N): Creating N spots for a min heap.

• Actually I’m not, I’m reusing the same array that I was given. In other words, the algorithm is in-place.

​

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

datastructur.es

Mergesort

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.

datastructur.es

Insertion Sort

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: http://yellkey.com/arrive

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: http://yellkey.com/machine

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 (Extra)

(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