- Quiz 4 this Friday

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.

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.

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`

!