Week 10, Wednesday: Sorting/Analysis of Algorithms

selection sort

This is the selection sort algorithm:

• given a list L
• find the smallest number in the list, swap it to position 0
• find the next smallest number in the list, swap it to position 1
• find the next smallest number in the list, swap it to position 2
• and so on....

It is called selection sort because each time you are selecting the smallest number from the remaining unsorted elements.

I assume you understand the "find the smallest number in a list" part, but here it is:

ismall = 0               # index of first element in list
for i in range(len(L)):
  if L[i] < L[ismall]:
    ismall = i           # found a smaller item, so save position

# after the for loop, ismall should be the index of the 
# smallest item in the list
print "smallest is ", L[ismall]

The selection sort uses the above code, but not just for position 0. A second outer for loop is needed to run the above code for all values from 0 to the last index of the list.

Here is a video of the selection sort algorithm (click to play):

See if you can add selectionSort() to our sorts.py file of sorts. Include some test code at the bottom of sorts.py to make sure your selectionSort() function is working properly.

bubble sort

This is the bubble sort algorithm:

• given a list L
• for every item in the list, compare to the item just to the right, swap if needed
• keep doing the above until you go from one end of the list to the other and don't make any swaps!

Here's a video of the bubble sort algorithm (click to play):

See if you can add bubbleSort() to our sorts.py file. Include some test code at the bottom of sorts.py to make sure your bubbleSort() function is working properly.

insertion sort

This is the insertion sort algorithm:

• assume item at index 0 is already "sorted"
• starting with item at index 1, check all items to the left and swap positions if needed
• do the same for item at index 2, where now items at index 0 and 1 should be in order
• do the same for item at index 3, where now items at index 0, 1, and 2 are in order ...and so on

Notice that, for each index, all items to the left are in order, and you are inserting the next item into the correct spot.

Here is a video of the insertion sort algorithm (click to play):

See if you can add insertionSort() to our sorts.py file. Include some test code at the bottom of sorts.py!