Sorting Algorithms Overview
Explore the concepts of selection sort, stability, and insertion sort with detailed explanations and visuals. Understand the importance of stable sorting and in-place sorting in algorithms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 373 Section 8 Sorting out Sorting
Sorting Buzz Words Stable: Any equal items remain in the same relative order before and after the sort. In-Place: Requires only O(1) extra space to perform the sort. 3A 2A 3B 2B 2A 2B 3A 3B
Selection Sort Repeatedly select the smallest remaining item and swap it to its proper index. 1. Find the smallest item in the array, and swap it with the first item. 2. Find the next smallest item in the array, and swap it with the next item. 3. Continue until all items in the array are sorted. We look through entire remaining array every time to find the minimum.
Selection Sort section_7_selection_sort.mov
Selection Sort Stability Question Repeatedly select the smallest remaining item and swap it to its proper index. 1. Find the smallest item in the array, and swap it with the first item. 2. Find the next smallest item in the array, and swap it with the next item. 3. Continue until all items in the array are sorted. Selection sort is not stable. Give an example.
Selection Sort Stability Answer Repeatedly select the smallest remaining item and swap it to its proper index. 1. Find the smallest item in the array, and swap it with the first item. 2. Find the next smallest item in the array, and swap it with the next item. 3. Continue until all items in the array are sorted. Selection sort is not stable. Give an example. 2A 2B 2C 1
Selection Sort Stability Answer Repeatedly select the smallest remaining item and swap it to its proper index. 1. Find the smallest item in the array, and swap it with the first item. 2. Find the next smallest item in the array, and swap it with the next item. 3. Continue until all items in the array are sorted. Selection sort is not stable. Give an example. sorted 1 2B 2C 2A 2A and 2B are not in the same relative order!
Insertion Sort Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor.
Insertion Sort section_7_insertion_sort.mov
Insertion Sort Stability Question Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. Insertion sort is stable. Give an example.
Insertion Sort Stability Answer Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. 3A 2A 3B 2B Insertion sort is stable. Give an example.
Insertion Sort Stability Answer Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. sorted 3A 2A 3B 2B Insertion sort is stable. Give an example.
Insertion Sort Stability Answer Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. sorted 2A 3A 3B 2B Insertion sort is stable. Give an example.
Insertion Sort Stability Answer Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. sorted 2A 3A 3B 2B Insertion sort is stable. Give an example.
Insertion Sort Stability Answer Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. sorted 2A 2B 3A 3B Insertion sort is stable. Give an example. Relative orders never broken!
Merge Sort 1. If array is of size 1, return. 2. Merge sort the left half. 3. Merge sort the right half. 4. Merge the two sorted halves. Stable! uses the fact that left-half items come before right-half items.
In-place Heap Sort Modifies the input to be in descending (reverse sorted) order! Possible fixes: 1) Reverse the output (in O(n)) 2) Use a max heap 3) Reverse heap compare function to emulate a max heap
In-place Heap Sort Avoid extra copies of data to save memory by treating the input array as a heap. We ll use a max heap for this sort. 1. Floyd s buildHeap. Efficient heap construction by percolating down on nodes in reverse level order (starting from the back of our input array). 2. Once heap-ified, call removeMax() and place max item after remainder of heap in array. Repeat this step N times.
Heap Sort Stability Question 1. Floyd s buildHeap. 2. Repeat N times: a. Call removeMax(). b. Put max item after heap in the array. Heap sort is not stable. Give an example.
Heap Sort Stability Answer 1A 1. Floyd s buildHeap. 2. Repeat N times: a. Call removeMax(). b. Put max item after heap in the array. 1B 1C 1D Heap sort is not stable. Give an example. 1A 1B 1C 1D
Heap Sort Stability Answer 1D 1. Floyd s buildHeap. 2. Repeat N times: a. Call removeMax(). b. Put max item after heap in the array. 1B 1C sorted Heap sort is not stable. Give an example. 1D 1B 1C 1A Relative order messed up!
Heap Sort Stability Answer 1C 1. Floyd s buildHeap. 2. Repeat N times: a. Call removeMax(). b. Put max item after heap in the array. 1B sorted Heap sort is not stable. Give an example. 1C 1B 1D 1A Relative orders messed up! And so on...
Quick Sort 1. Partition around a pivot item, e.g. leftmost item. 2. Quicksort left side, all keys pivot. 3. Quicksort right side, all keys pivot (can put equal items on left as well). Stable? 32 15 2 17 19 26 41 17 17 Quick Sort is not stable because equal items are arbitrarily placed on the left or right of the pivot so their relative orders may change. 32 32 Partition(32) 15 2 17 19 26 17 17 32 41 Other partitioning algorithms can result in a stable Quick Sort. 32 s final position
Quick Sort Stability Not stable! Say we pick this as pivot... 1A 1B 1C 1D 1B 1A 1C 1D Relative order messed up!
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
Answer Problem 2a) Insertion Sort Answer Build a sorted subarray (like selection sort) by using left-neighbor swaps for stability. Scan from left to right 1. If an item is out of order with respect to its left-neighbor, swap left. 2. Keep on swapping left until the item is in order with respect to its left- neighbor. Input: 32 15 2 17 19 26 41 17 17
Answer Problem 2b) Selection Sort Answer Repeatedly select the smallest remaining item and swap it to its proper index. 1. Find the smallest item in the array, and swap it with the first item. 2. Find the next smallest item in the array, and swap it with the next item. 3. Continue until all items in the array are sorted. We look through entire remaining array every time to find the minimum. Input: 32 15 2 17 19 26 41 17 17
Answer Problem 2c) In-place Heapsort Answer Avoid extra copies of data to save memory by treating the input array as a heap. We ll use a max heap for this sort. Floyd s buildHeap. Efficient heap construction by percolating down on nodes in reverse level order (starting from the back of our input array). Once heap-ified, call removeMax() and place max in the array index after the last item in heap. Repeat N times. 32 15 2 17 19 26 41 17 17 Finish heapification and then sort by calling removeMax()! Heapification 41 19 32 ... ... ... ... ... ...
Answer Problem 2d) Merge Sort Answer 1. If array is of size 1, return. 2. Merge sort the left half. 3. Merge sort the right half. 4. Merge the two sorted halves. 32 15 2 17 19 26 41 17 17
Answer Problem 2e) Quick Sort Answer 1. Choose the leftmost item as your pivot. 2. Quicksort left side, all keys pivot. 3. Quicksort right side, all keys pivot. 32 15 2 17 19 26 41 17 17 32 32 Partition(32) 15 2 17 19 26 17 17 32 41 32 s final position
Problem 6: Corner-Case Inputs Selection Sort: Trick Question! Sort does the same thing each time. selection_all.mov
Problem 6: Corner-Case Inputs Insertion Sort: Best Case Notice: List is already sorted! insertion_best.mov
Problem 6: Corner-Case Inputs Insertion Sort: Worst Case Notice: List is reverse sorted! insertion_worst.mov
Problem 6: Corner-Case Inputs Heap Sort: Best Case A heap with all duplicates means no percolating down so every removeMin() becomes O(1)!
Problem 6: Corner-Case Inputs Heap Sort: Worst Case
Problem 6: Corner-Case Inputs Heap Sort: Worst Case Notice: Every item needs to percolate down worst_heapsort.mov
Problem 6: Corner-Case Inputs Merge Sort: Trick Question! Sort does the same thing each time.
Problem 6: Corner-Case Inputs Quick Sort: Worst Case
Problem 6: Corner-Case Inputs Quick Sort: Worst Case Screen Recording 2020-05-17 at 2.34.35 PM.mov
Problem 6: Corner-Case Inputs General Quick Sort worst-case runtime: N N - 1 Pivot always puts everything to one side. N - 2 datastructur.es datastructur.es
Problem 6: Corner-Case Inputs Quick Sort: Best Case
Problem 6: Corner-Case Inputs Quick Sort: Best Case Pivot is the median every time! best_quicksort.mov
Problem 6: Corner-Case Inputs N N/2 N/4 General Quick Sort best-case runtime: Pivot always divides input in half. datastructur.es datastructur.es
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)
