We will spend this week learning about sorting algorithms. We will cover two in depth, and possibly a third (time permitting). We will focus on understanding, implementing, and analyzing each of the algorithms presented.
In groups of 2 or 3, grab 8 playing cards. Given a random set of cards, think of possible algorithms for sorting the list of cards from smallest to lowest. Specifically, describe each comparison that needs to be done and when a swap of two cards takes place. Try to describe your process as an algorithm (using pseudocode). Keep in mind that the cards are standing in place of a list of numbers.
First, we will discuss the algorithm selection sort which, on the first step, searches the entire list for the minimum value. This value is swapped with position 0 in the list. On the next pass, the algorithm repeats the process for the remaining part of the list (position 1 to N-1).
In sortNumbers.py, we will implement selection sort to put a list of ints in order from smallest to largest
In pairs, sort the list of numbers:
10 5 6 11 9 21 17 3 7Show the result after each major step (approximately each iteration).
Next, we will cover bubble sort. We will repeat the steps from selection sort, including implementation and analysis of run time. The bubble sort algorithm works down the list, comparing neighboring items, and swapping them if they are out of order. The list is not completely sorted, but it is more sorted than before. We repeat the process until the list is completely sorted. After each pass, the largest item is pushed all the way to the end of the list. Therefore, we know the number of passes is at most N (the length of the list).
We will analyze the run time of both algorithms, described in big-O terms. To think carefully about the analysis, let us first break the problem into two subquestions. For each algorithm, answer these two questions:
findMin() for selection sort and then try to figure out how many times findMin() gets called.What is the big-O run time of selection sort? Bubble sort?
Finally, we will conclude with a third algorithm known as insertion sort and analyze its runtime.