← Introduction to Computer Science

Unit 19: Sorting and Searching

Every classic sort racing on the same array with comparisons ticking, plus the two ways to search once the data is or isn't sorted.

10 topics · 35 questions

Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.

Bubble Sort

  1. How it worksHow does one pass of bubble sort walk through the array swapping every adjacent pair that's out of order?
  2. Worked exampleTrace bubble sort on [5, 1, 4, 2] through its first two full passes.
  3. Common mistakeWhy doesn't bubble sort finish sorting an array in just one single pass?
Your turn1 of 2
One pass of bubble sort walks through an array of 697 elements, comparing and possibly swapping each of the n minus 1 adjacent pairs. How many adjacent-pair comparisons does one full pass make?

Selection Sort

  1. How it worksHow does selection sort find the minimum of the unsorted remainder and swap it into place at each step?
  2. Worked exampleTrace selection sort on [5, 1, 4, 2, 3] through each step of finding and placing the minimum.
  3. Going furtherWhat happens to the number of comparisons selection sort makes once the array is already sorted?
Your turn1 of 2
Selection sort scans the entire unsorted remainder to find its minimum before each single swap. For an array of 697 elements, how many comparisons does the first scan make to find the minimum among all n elements?

Insertion Sort

  1. How it worksHow does insertion sort take one element at a time and slide it backward into place among the sorted ones?
  2. Worked exampleTrace insertion sort on [5, 1, 4, 2] through each element being inserted into the sorted portion.
  3. Common mistakeWhy isn't insertion sort always a bad choice just because its worst case is O(n2)?
Your turn1 of 2
Insertion sort takes one element at a time and slides it backward into place among the 697 already-sorted elements before it. In the worst case, how many comparisons does sliding this one new element require?

Merge Sort

  1. How it worksHow does merge sort recursively split the array in half and then merge two sorted halves back together?
  2. Worked exampleTrace merge sort splitting [5, 1, 4, 2] down to single elements and merging them back up in sorted order.
  3. Ties togetherHow does merge sort's split-then-combine structure make it a textbook example of divide and conquer?
Your turn1 of 2
Merge sort recursively splits an array in half 14 times before reaching single elements. If the array size n equals 2 to the power of k, what is n given k is 14?

Quicksort and Its Worst Case

  1. How it worksHow does quicksort pick a pivot, partition smaller values to one side and larger to the other, then recurse?
  2. Worked exampleTrace quicksort on [5, 1, 4, 2, 8] using the last element as the pivot for the first partition step.
  3. Common mistakeWhy isn't quicksort's runtime always O(n log n), the way its average case might suggest?
  4. Worked exampleTrace why quicksort using the first element as pivot degrades to O(n2) on the sorted array [1, 2, 3, 4, 5].
  5. Going furtherWhat changes about quicksort's worst case once the pivot is chosen randomly instead of always the first element?
Your turn1 of 2
Quicksort picks a pivot and partitions 697 elements into two sides around it, then recurses on each side. This first partition step compares every other element against the pivot once. How many comparisons does this first partition step make for an array of n elements?

Heap Sort

  1. How it worksHow does heap sort build a max-heap and then repeatedly extract the maximum into the back of the array?
  2. Worked exampleTrace heap sort on [4, 10, 3, 5, 1] through building the initial max-heap and the first two extractions.
  3. Ties togetherHow does heap sort's repeated extract-max connect back to the sift-down operation from a priority queue?
Your turn1 of 2
Heap sort builds a max-heap from 697 elements, then repeatedly extracts the maximum into the back of the array, one extraction at a time. How many total extractions does heap sort perform to fully sort all n elements?

Counting Sort and Radix Sort

  1. How it worksHow does counting sort tally how many times each value appears and then rebuild the array from those counts?
  2. Worked exampleTrace counting sort on [4, 2, 2, 4, 1, 3] by building its count array and rebuilding the sorted output.
  3. Going furtherWhat changes once radix sort applies counting sort digit by digit instead of on the whole value at once?
  4. Worked exampleTrace radix sort processing [170, 45, 75, 90] by its ones digit first, then its tens digit.
  5. Common mistakeWhy doesn't counting sort work well once values range from 1 to a billion instead of 1 to 100?
Your turn1 of 2
Counting sort tallies how many times each of 131 possible distinct values appears across 699 elements, then rebuilds the sorted array from those counts. How many total count-array entries does counting sort maintain, one per possible value?

Every Sort Racing on the Same Array

  1. How it worksHow does counting each sort's comparisons on the same random array reveal which curve each algorithm follows?
  2. Worked exampleFind how many comparisons bubble sort and merge sort each make sorting the same 8-element array.
  3. Common mistakeWhy doesn't a sort with fewer lines of code necessarily run faster than one with more?
  4. Ties togetherHow does the moment an O(n2) sort falls permanently behind an O(n log n) sort connect to their growth curves never crossing again?
Your turn1 of 2
Bubble sort makes roughly n squared comparisons while merge sort makes roughly n log n comparisons, on the same array of 6965 elements. Find the number of comparisons bubble sort makes, computed as n squared.

Binary Search and Its Precondition

  1. How it worksHow does binary search compare the middle element and throw away half of the remaining list on every step?
  2. Worked exampleTrace binary search for 23 in the sorted list [2, 5, 8, 12, 16, 23, 38, 45].
  3. Common mistakeWhy doesn't binary search work correctly the moment you run it on data that isn't actually sorted?
Your turn1 of 2
Binary search on a sorted list of 2 to the power of 14 elements halves the remaining search space with each comparison. About how many comparisons does it need in the worst case, expressed directly as k?