CSE 332 Section 5�Sorting

Announcements

• EX05 Hashing is due Friday 7/24 (tomorrow!)
• Midterm yesterday…
• How was it?

​

Amazing no clue Awful

Properties: How to choose a sorting method?

Comparison-based / non-comparison-based: <, >, =

Stable: preserve original order of elements if equal

In-place: no need for extra data structure to store values

Online: begin with an incomplete list

Adaptive: better running time for nearly sorted input

Worst-Case Running Time

​

​

Problem 0

0. Winner of Sorts

1. A total of 206 different nations have participated across 30 summer Olympics. The most gold medals ever won by a country in a single Olympics was U.S., which won 83 gold medals in 1984. Which algorithm should we use to sort all 6,000 country-year pairs by the number of gold medals won by that country in that year?

Properties: In Place, Stable, Adaptive, Online, Non-Comparison-Based

Algorithms: Quick Sort, Insertion Sort, Radix Sort

We can make additional assumptions about the country-year pairs beyond just the ability to compare # of gold medals, since we know that out of all the country-year pairs, the maximum number of gold medals is 83. Non comparison based lets us use “linear time” sorting algorithms: specifically, Radix sort.

0. Winner of Sorts

2. Suppose we had a list of all runners already sorted by their finish time in the 100 meter dash. A small number of runners incurred time penalties, so we need to sort the list again to adjust for those penalties. What algorithm should we use for this second sort?

​

​

Properties: In Place, Stable, Adaptive, Online, Non-Comparison-Based

Algorithms: Insertion Sort, Merge Sort, Radix Sort

We have a list of all runners that is already sorted. Since it’s already sorted, we want our algorithm to be adaptive, since adaptive algorithms have better running time for nearly/already sorted input. Specifically we want to use insertion sort, since it has the best best-case runtime.

0. Winner of Sorts

3. Suppose our list of nations is already sorted by the total number of silver medals won across the 30 summer Olympics. Which algorithm should we use to sort the nations by the total number of gold medals won, while ensuring that nations with the same number of gold medals are sorted based on their number of silver medals?

​

Properties: In Place, Stable, Adaptive, Online, Non-Comparison-Based

Algorithms: Merge Sort, Insertion Sort, Quick Sort

We have a list of nations that has existing ordering based on the number of silver medals won for each nation. To preserve this original silver-medal based ordering, our algorithm must be stable. So, we want to use merge sort since it has a better worst-case runtime than insertion sort (n log n vs. n^2).

Comparison-based Sorting Review

Insertion Sort

Insertion sort builds a sorted subarray at the front of the original array. Takes the first element of the unsorted subarray and inserts it into the sorted subarray.

Properties:

• In-place and stable
• Best-case runtime: O(n)
• Worst-case runtime: O(n²)

Heap Sort

Heap sort builds a max heap, extracting the largest one-by-one to fill the sorted list (sharing the same array as the heap) from end to beginning.

• sorted subarray at the back of the original array

Properties:

• In-place but not stable
• Best-case runtime: O(n log n)
• Worst-case runtime: O(n log n)

Merge Sort

Merge sort uses divide and conquer. It recursively splits an array into two halves, sorts them, and then merges them back together in sorted order.

Properties:

• Not in-place but stable
• Best-case runtime: O(n log n)
• Worst-case runtime: O(n log n)

mergeSort(input) -> sorted input:

1. sortedLeft = mergeSort(left half of input)

2. sortedRight = mergeSort(right half of input)

3. return (merged ‘sortedLeft’ and ‘sortedRight’)

Quick Sort

Quick sort recursively partitions an array based on a pivot element, recursively sorts the subarrays on either side of the pivot, and combines the results to obtain a sorted array.

​

Properties:

• In-place but not stable.
• Best-case runtime: O(n log n)
• Worst-case runtime: O(n²)

quickSort(input) -> void:

1. pick pivot

2. partition input into ‘lessThanPivot’ and

‘greaterThanPivot’ parts

3. quickSort(lessThanPivot)

4. quickSort(greaterThanPivot)

Problem 1

1. Sorting Hat

Suppose we sort an array of numbers, but it turns out every element of the array is the same (e.g. [17, 17, 17, …, 17]).

What is the asymptotic runtime of the following sorting algorithms?

​

1. Sorting Hat - Solution

Problem 2

2. Another Sort of Sorting…

Given an array of integers as such: {11, 13, 55, 67, 79, 10, 8, 6, 4, 2}. Please answer the following questions (assume all sorts to be done in ascending order):

What is the asymptotic runtime of the following sorting algorithms?

Here, assume we choose the leftmost element as the pivot each time for QS.

2. Another Sort of Sorting…

Given an array of integers as such: {11, 13, 55, 67, 79, 10, 8, 6, 4, 2}.

Please answer the following questions (assume all sorts to be done in

ascending order):

What is the asymptotic runtime of the following sorting algorithms?

Here, assume we choose the leftmost element as the pivot each time for QS.

Problem 3

3. Break it up and Sort it out

Suppose we have an array of size n divided into n/k subarrays of size k. The elements within each subarray are unsorted, but the subarrays themselves are ordered correctly.

What would be the worst-case runtime of:

1. Insertion sort on the whole array?

​

• Merge sort on the whole array?

​

• Merge sorting each subarray?

​

3. Break it up and Sort it out

Suppose we have an array of size n divided into n/k subarrays of size k. The elements within each subarray are unsorted, but the subarrays themselves are ordered correctly.

What would be the worst-case runtime of:

• Insertion sort on the whole array?

​

• Merge sort on the whole array?

​

​

• Merge sorting each subarray?

​

Non-Comparison Sorting Review

Bucket Sort

Distributes elements into their corresponding buckets. Buckets have an inherent ordering and are merged together in this ordering to produce the sorted array.

Properties:

• Not in-place but stable
• Runtime: O(n + B)
• Need to iterate over n elements and B buckets.
• Good when B << n or B ≈ n.
• Bad when B >> n.

bucketSort(input) -> sorted input:

1. create array of size B

2. put each element into their corresponding bucket

3. generate sorted array by iterating through the

buckets in order

Original Input:�[5₁, 1₁, 3₁, 4₁, 3₂, 2, 1₂, 1₃, 5₂, 4₂, 5₃]

Final output:

[1₁, 1₂, 1₃, 2, 3₁, 3₂, 4₁, 4₂, 5₁, 5₂, 5₃]

B: 5

Radix Sort - 1’s Digit

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 1’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

Bucket Sort on 10’s Digit

Radix Sort - 10’s Digit

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 10’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

• Notice how elements are now sorted with respect to their last two digits.
• By running bucket sort from the least to the most significant digit, the order of the more significant digits take precedence over the less significant digits.

Radix Sort - 100’s Digit

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Bucket Sort on 10’s Digit

Bucket Sort on 100’s Digit

Radix Sort - Final Output

Radix Sort repeatedly runs bucket sort on the elements for each significant digit, from least significant to most significant.

Original input: [478, 537, 9, 721, 3, 38, 143, 67], b: 10

Final output array:

• Not in-place but stable
• Runtime: O(p(n + b))
• Bucket sort has O(n + b) runtime, and we’re running it p = log_b(max(n)) times.

Problem 4

4. Radix Sort (a)

Original Input: [170, 45, 75, 90, 802, 24, 2, 66]

Bucket Sort on 1’s Digit

Bucket Sort on 1’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

4. Radix Sort (b)

Original Input: [170, 45, 75, 90, 802, 24, 2, 66]

Bucket Sort on 10’s Digit

​

Bucket Sort on 1’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

Bucket Sort on 10’s Digit

4. Radix Sort (c)

Original Input: [170, 45, 75, 90, 802, 24, 2, 66]

Bucket Sort on 100’s Digit

Bucket Sort on 10’s Digit

radixSort(input) -> sorted input:

1. create array of size b

2. for each significant digit:

3. run bucket sort on the elements using their

corresponding significant digit values

Bucket Sort on 100’s Digit

4. Radix Sort (d) Final Output!

Original Input: [170, 45, 75, 90, 802, 24, 2, 66]

Empty buckets into output array

Bucket Sort on 100’s Digit

Output Array

Decision Tree

Decision Tree: Quick Introduction

• A decision tree is a tree-like model representing all possible decisions or comparisons in a process.
• Nodes: points where a comparison or decision is made.
• Branches: possible outcomes of that comparison.
• Leaves: final outcomes after all decisions.
• Useful for visualizing sorting, searching, or algorithm paths.

Decision Tree Example

a<b<c; a<c<b; b<a<c; b<c<a; c<b<a; c<a<b

a<b<c; a<c<b; c<a<b

b<a<c; b<c<a; c<b<a

Ask: is a < b?

a<b<c

a<c<b; c<a<b

b<a<c

b<c<a; c<b<a

a<c<b

c<a<b

b<c<a

c<b<a

Ask: is b<c?

Ask: is a<c?

Ask: is a<c?

Ask: is b<c?

yes

no

yes

no

yes

no

yes

no

yes

no

Decision Tree Example

Thank You!