CSE 373 Su23 Section 8
Sorting out SortingTM
Agenda
Announcements
Mon (8/7) | Tues (8/8) | Wed (8/9) | Thurs (8/10) | Fri (8/11) | Sat (8/12) |
EX5 due @ 11:59 pm | | | | | |
Mon (8/14) | Tues (8/15) | Wed (8/16) | Thurs (8/17) | Fri (8/18) | Sat (8/19) |
EX6 due @ 11:59 pm | | | | P4 due @ 11:59 pm | |
MicroTeach: Sorting!
Sorting Buzz Words
3A
2A
3B
2B
2A
2B
3A
3B
Sorting Study Guide!
Sorting Cheat Sheet
| insertion | selection | merge | quick | heap |
worst | n^2 | n^2 | n*logn | n^2 | n*logn |
In practice | n^2 | n^2 | n*logn | n*logn | n*logn |
best | n | n^2 | n*logn | n*logn | n |
In place | yes | yes | no | yes | yes |
stable | yes | no | yes | no | no |
In-Depth Sorting Walkthroughs
Input:
32
15
2
17
19
26
41
17
17
Non-Comparison Sorts
Recap
(Recap) Bucket Sort
* can be used only when values to be sorted are integers between 1 and K (or any small range)
bucketSort(input):
Count array | |
1 | |
2 | |
3 | |
4 | |
5 | |
K = 5
Input = 5, 1, 3, 4, 3, 2, 1, 1, 5, 4, 5
(Recap) Bucket Sort
* can be used only when values to be sorted are integers between 1 and K (or any small range)
bucketSort(input):
Count array | |
1 | 3 |
2 | 1 |
3 | 2 |
4 | 2 |
5 | 3 |
K = 5
Input = 5, 1, 3, 4, 3, 2, 1, 1, 5, 4, 5
Output = 1, 1, 1, 2, 3, 3, 4, 4, 5, 5, 5
(Recap) Radix Sort
radixSort(input):
(eg. 10)
B = 10
Input = 478, 537, 9, 721, 3, 38, 143, 67
Bucket Sort on 1’s digit:
Bucket Sort on 10’s digit:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| | | | | | | | | |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| | | | | | | | | |
(Recap) Radix Sort
radixSort(input):
(eg. 10)
B = 10
Input = 478, 537, 9, 721, 3, 38, 143, 67
Bucket Sort on 1’s digit:
Bucket Sort on 10’s digit:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 721 | | 3 143 | | | | 537 67 | 478 38 | 9 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| | | | | | | | | |
(Recap) Radix Sort
radixSort(input):
(eg. 10)
B = 10
Input = 478, 537, 9, 721, 3, 38, 143, 67
Bucket Sort on 1’s digit:
Bucket Sort on 10’s digit:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 721 | | 3 143 | | | | 537 67 | 478 38 | 9 |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
3 9 | | 721 | 537 38 | 143 | | 67 | 478 | | |
(Recap) Radix Sort
radixSort(input):
(eg. 10)
B = 10
Input = 478, 537, 9, 721, 3, 38, 143, 67
Bucket Sort on 10’s digit:
Bucket Sort on 100’s digit:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
3 9 | | 721 | 537 38 | 143 | | 67 | 478 | | |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| | | | | | | | | |
(Recap) Radix Sort
B = # digits
N = # input
radixSort(input):
(eg. 10)
B = 10
Input = 478, 537, 9, 721, 3, 38, 143, 67
Bucket Sort on 10’s digit:
Bucket Sort on 100’s digit:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
3 9 | | 721 | 537 38 | 143 | | 67 | 478 | | |
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
3 9 38 67 | 143 | | | 478 | 537 | | 721 | | |
Output = 3, 9, 38, 67, 143, 478, 537, 721
Problems 11A-C: Sorting Puzzle
Sorting Puzzle A
Initial array
0, 4, 2, 7, 6, 1, 3, 5
During execution
0, 2, 4, 7, 6, 1, 3, 5
Sorted result
0, 1, 2, 3, 4, 5, 6, 7
How can we identify which sorting is being used?
Sorting Puzzle A
During execution
0, 2, 4,| 7, 6, 1, 3, 5
Sorted
Subarray
Unsorted Subarray
We can see there is a subarray that is sorted and unsorted subarray. The items are only sorted within its subarray
Sorting Puzzle A
During execution
0, 2, 4,| 7, 6, 1, 3, 5
Sorted
Subarray
Unsorted
Subarray
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part.
Values from the unsorted part are picked and placed at the correct position in the sorted part
Sorting Puzzle B
Initial array
0, 4, 2, 7, 6, 1, 3, 5
During execution
0, 1, 2, 3, 6, 4, 7, 5
Sorted result
0, 1, 2, 3, 4, 5, 6, 7
How can we identify which sorting is being used?
Sorting Puzzle B
Initial array
0, 4, 2, 7, 6, 1, 3, 5
During execution
0, 1, 2, 3,|6, 4, 7, 5
We can see that 1 which is the smallest item was placed at index 1. It is clear that the item is chosen among the items in the entire array.
Second smallest item in the entire array.
Sorting Puzzle B
Initial array
0, 4, 2, 7, 6, 1, 3, 5
During execution
0, 1, 2, 3,|6, 4, 7, 5
Second smallest item in the entire array
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
Sorting Puzzle C
Below you will find intermediate steps in performing a sorting algorithm on the given input array. The steps do not necessarily represent consecutive steps in the algorithm (that is, many steps are missing), but they are in the correct sequence. Select the algorithm it illustrates from among the following choices
Initial Array
During execution
11429, 3291, 192, 1337, 7683, 594, 4242, 9001, 129, 1000, 439
192, 1337, 1429, 3291, 7683, 129, 594, 1000, 4242, 4392, 9001
1429, 3291, 7683, 192, 1337, 594, 4242, 9001, 4392, 129, 1000
1429, 3291, 192, 1337, 7683, 594, 4242, 9001, 129, 1000, 4392
192, 1337, 1429, 3291, 7683, 129, 594, 1000, 4242, 4392, 9001
How can we identify which sorting is being used?
Sorting Puzzle C
Initial array
During execution
192, 1337, 1429, Sorted
, 7683, 129, 594, 1000, 4242, 4392, 9001
1429, 3291, 7683, 192, 1337, 594, 4242, 9001, 4392, 129, 1000
1429, 3291, 192, 1337, 7683, 594, 4242, 9001, 129, 1000, 4392
Sorted
Sorted
Sorted
Our items are divided into four sorted subarrays and later two sorted subarrays.
192, 1337, 1429, 3291, 7683, 129, 594, 1000, 4242, 4392, 9001
Sorted
Sorted
Sorting Puzzle C
During execution
192, 1337, 1429, 3291, 7683, 129, 594, 1000, 4242, 4392, 9001
1429, 3291, 192, 1337, 7683, 594, 4242, 9001, 129, 1000, 4392
Sorted
Sorted
Sorted
Like QuickSort, Merge Sort is a Divide and Conquer algorithm.
It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
One identifying feature of mergesort is that the left and right halves do not interact with each other until the very end.
Sorted
Problems 10A-D: Sorting Design Decision 2
�
� �
Problem 10: Sorting Design Decision 2
What sorting have same worst and best case run time? Merge Sort
What sorting has similar best case run time to Merge Sort? Quick Sort
Can we do any better? Almost Sorted means the high chance of minimum number of operation is guaranteed
Best run time of Insertion sort is O(N)
�
� �
Problem 10: Sorting Design Decision 2
�
� �
Problem 10: Sorting Design Decision 2
�
� �
Problem 10: Sorting Design Decision 2
How does limited space related to sorting?
Avoid extra DS to store information -> In-Place Sort!
�
� �
Problem 10: Sorting Design Decision 2
Insertion Sort: Uses In-Place sort
Perhaps, we can improve the runtime while meeting the requirements
�
� �
Problem 10: Sorting Design Decision 2
Insertion Sort: Uses In-Place sort
Perhaps, we can improve the runtime while meeting the requirements
Heap Sort: Uses In-Place sort
�
� �
Problem 10: Sorting Design Decision 2
Problem 10: Sorting Design Decision 2
What kind of input would you expect from your users?
Expect the worst! People may be malicious and try to submit worst-case input
How should we protect ourselves against worst case input?
Pick a sort with an efficient worst case runtime
Finally, what sorts could accomplish this for us?
Heapsort and Merge sort both have O(n log n) runtimes and would be good choices in this case!
Problem 10: Sorting Design Decision 2
What kind of input should we expect?
We are going to have to sort every ordering of the numbers 1-15. This means worst case input, best case input, and everything in between.
What should we optimize for then?
Since we are expecting every single possible ordering of a set of numbers, and best and worst case inputs are uncommon, a sorting algorithm with a good average case runtime will be most useful to us here!
What algorithm is this?
Quicksort! It’s in the name! Quicksort is O(n log n) in the average case.
Note: Although heapsort and merge sort have O(n log n) worst case runtime, they tend to be slower in the average case compared to Quicksort! Of course, this all depends on implementation!
Problems 5: Insertion Sort Worst Runtime
Problems 5: Insertion Sort Worst Runtime
Give the worst possible order of input for insertion sort with the following integers: 1, 2, 3, 4, 5, 6, 7. Assume that the result of sorting should be in ascending order.
Problems 5: Insertion Sort Worst Runtime
Give the worst possible order of input for insertion sort with the following integers: 1, 2, 3, 4, 5, 6, 7. Assume that the result of sorting should be in ascending order.
Solution: 7, 6, 5, 4, 3, 2, 1
The worst case scenario happens when the input list is in decreasing order. To sort the last element, we need n-1 comparisons and n-1 swaps. To sort the second last element, we need to n - 2 comparisons and n-2 swaps, and so on.
Worst case run time of Insertion sort is O(N^2)
Problem 6A-E: Corner-Case Inputs
Problem 6A: Selection Sort
Selection Sort: Trick Question!
��
� �
Sort does the same thing each time.
��
� �
Problem 6B: Insertion Sort
Insertion Sort: Best Case
��
� �
Notice: List is already sorted!
��
� �
Problem 6B: Insertion Sort
Insertion Sort: Worst Case
��
� �
Notice: List is reverse sorted!
��
� �
Problem 6C: Merge Sort
Merge Sort: Trick Question!
��
� �
Sort does the same thing each time.
Problem 6D: Quicksort
Quick Sort worst-case runtime:
Pivot always puts everything to one side.
N
N - 1
N - 2
Problem 6D: Quicksort
Quick Sort best-case runtime: Pivot always divides input in half.
N/2
N/4
N
Problem 6E: Heap Sort
Heap Sort: Best Case
��
� �
��
� �
The best case runtime is O(n): a heap with all duplicates means no percolating down so every removeMin() becomes O(1)!�
� �
Problem 6E: Heap Sort
Heap Sort: Worst Case
� �
The worst case runtime is O(nlog n). This is when every item needs to percolate down so every removeMin() becomes O(log n)
��
��
� �