Lab 21: Counting-Based Sorts | CS 61BL Summer 2024
Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for lab 21 is located here. As usual, pull the files from the skeleton and make a new IntelliJ project. For demos of the algorithms discussed in this lab, look here This lab is very reading-heavy, with fairly short coding sections. You should try to fully understand each section before moving on. If you have any confusion, clarify with your TA! Before we talk about the topics of today’s lab, let’s talk about insertion sort and quicksort’s runtime in the “average” case. Is it possible to do better than 𝑂 ( 𝑁 log 𝑁 ) in the worst case for these comparison-based sorts? Suppose we have a scrambled array of 𝑁 numbers, with each number from 1 to 𝑁 occurring once. How many possible orders can the numbers be in? The answer is 𝑁 ! , where 𝑁 ! = 1 ∗ 2 ∗ 3 ∗ ⋯ ∗ ( 𝑁 − 2 ) ∗ ( 𝑁 − 1 ) ∗ 𝑁 . Here’s why: the first number in the array can be anything from 1
Each assignment will have an FAQ linked at the top. You can also access it by adding “/faq” to the end of the URL. The FAQ for lab 21 is located here. As usual, pull the files from the skeleton and make a new IntelliJ project. For demos of the algorithms discussed in this lab, look here This lab is very reading-heavy, with fairly short coding sections. You should try to fully understand each section before moving on. If you have any confusion, clarify with your TA! Before we talk about the topics of today’s lab, let’s talk about insertion sort and quicksort’s runtime in the “average” case. Is
Explore this link on the map →