Announcements

Proj3: It’s out. TIme to get started.

• Last semester’s students requested a walkthrough/getting-started video, so I’ll be making one of those tomorrow.

​

Midterm 2 grades will be out late Tuesday/early Wednesday.

• Grading is effectively done, but some makeups tomorrow.

CS61B

Lecture 32: Sorting I

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

Sorting - Definitions

A sort is a permutation (re-arrangement) of a sequence of elements that brings them into order according to some total order. A total order ≼ is:

• Total: x ≼ y or y ≼ x for all x, y
• Reflexive: x ≼ x
• Antisymmetric: x ≼ y and y ≼ x iff x = y (x and y are equivalent).
• Transitive: x ≼ y and y ≼ z implies x ≼ z.

​

Unequal items may be ‘equivalent’ under these definitions:

• Example: Given strings, sorted by length, either may be put first.�

Sorting: An Alternate Viewpoint

An inversion is a pair of elements that are out of order.

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)

Performance Definitions

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

• DFS has time complexity Θ(V+E)

​

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

• DFS has space complexity Θ(V)
• Note that the graph takes up space Θ(V+E), but we don’t count this as part of the runtime of DFS, since we’re only accounting for the extra space that DFS uses.

Selection Sort and Heapsort

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.

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.

Naive Heapsort Runtime: http://shoutkey.com/any

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.

Heapsort Runtime Analysis

Use the magic of the heap to sort our data.

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

​

Informally, overall runtime is Θ(N Log N) + Θ(N) + O(N log N) = Θ(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.

If every swim fails…. Then it’d be theta(N) in that case. So maybe best to say that this is O(N log N).

A thing to ponder. I’ll put on the study guide with answers.

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.

In-place Heapsort Runtime: http://shoutkey.com/salad

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

In-place Heapsort Runtime

Use the magic of the heap to sort our data.

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

In-place Heapsort: http://shoutkey.com/scream

What is the memory complexity of Heapsort?

1. Θ(1)
2. Θ(log N)
3. Θ(N)
4. Θ(N log N)
5. Θ(N²)

​

In-place Heapsort

What is the memory complexity of Heapsort?

• Θ(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.

Sorts So Far

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

Mergesort

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.

Sorts So Far

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

Insertion Sort

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:

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

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)

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

Grey: Not considered this iteration.

Insertion Sort Runtime: http://shoutkey.com/drink

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:

Picking the Best Sort: http://shoutkey.com/kiwi

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

(Expected stop here unless we have extra time)

To Be Continued

​

(slides that follow this point are for next time)

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.

​

​

​

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)

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 and mergesort spend too much time dividing, whereas insertion sort goes straight to the conquest.

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

​

Shell’s Sort (Extra)

(Not on Exam)

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

​

Citations

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

​

Keynote Animations of Algorithms courtesy of Kevin Wayne