Thu Feb 7

The assignment for Tuesday is posted.

Questions about anything so far ?

today ... sorting

Discuss topics related to sorting including

• why sorting
• what is a "comparison" sort"
• properties of sorting algorithms :
• some of the common ones as listed in wikipedia: sorting
  • insertion sort
  • quick sort
  • heap sort
  • merge sort
  • bucket sorts

questions

Suppose you have a database with entry for every person in the US (i.e. 300 million items) and you're asked to sort them by birth date. What algorithm should you use and why?

Quicksort has a worst time efficiency of O(n**2). Why then is it so popular?

Radix sort is described as having O(n * k). What is k? Is this better or worse than a typical O(n log(n)) like quicksort? Explain what's going on.

aside

For testing these sorts of things in python3, notice the difference between

import random
a = random.sample(range(100), k=50)
b = random.choices(range(100), k=50)