In class notes week 9

Change into your inclass directory and copy some starting code from my directory.


    $ cd 
    $ cd cs21/inclass
    $ pwd
        /home/your_user_name/cs21/inclass
    $ mkdir w09-sort        
    $ cd w09-sort
    $ pwd
      /home/your_user_name/cs21/inclass/w09-sort
    $ cp ~adanner/public/cs21/w09-sort/* .
    $ ls
    sorting.py

Sorting

Today we are going to write a function selectSort that sorts a list of n numbers in place using an algorithm called selection sort. The basic idea of selection sort is to repeatedly find the next smallest element and place it in the correct position in the list by swapping. For example, we first find the smallest element in the list and place it in the first position of the list. Next we find the second smallest (this will be the smallest in the rest of the list, ignoring the first position). After repeating this process n-1 times, the list will be sorted.

Review the function swap(ls, i, j) that swaps the items in positions i and j in the list ls. We will use this function to implement selectSort(ls).

Next, we will implement the key selectSort steps outline in the code. Try testing the code and making sure the list is sorting.

How many steps does this take? How much longer would selection sort take if we doubled the size of the list? Try varying the value of n in main. n=500,1000,2000,4000,8000 make good test values. Do the runtimes follow your intuition?

Sorting and recursion