CP164 Lab 10 : Sorting

Week of

Sorting Algorithms

We are giving you a series of sorting algorithms and asking you to show which algorithms are superior in terms of the number of comparisons and swaps each has to make in order to sort an array into ascending order. The fewer comparisons and swaps an algorithm has to make, the more efficient it is.

The file Sorts_array.py contains a number of sorting algorithms defined as methods in the class Sorts. Copy this file to your data structures project. Unlike the other classes we have seen so far in this course, we do not have to create a Sorts object by calling s = Sorts() . In fact, Sorts has no __init__ method. Instead, each method is defined with the Python decorator @staticmethod . (Discussing Python decorators in detail is beyond the scope of this course.) This tells Python that you can call this method as a class method using the syntax Sorts.sort(...) rather than having to create a Sorts object.

We need some way to count the comparisons and swaps.

  1. Define functions that create a sorted list of Number objects, a reversed list of Number objects, and a list of randomly arranged list of Number objects. The function outlines and constant values to use are defined in test_Sorts_array.py.

    Hint: when you need to sort these arrays, make copies of them and sort the copies so that you don't have to recreate them every time you want to test a sort.

    Test test_Sorts_array.py:


  2. Complete the function test_sort . Track the comparisons for each set of data, calculate the average number of comparisons for the list of random lists.

    The sort function reference just means that you can put a function definition into a variable just like any other value, and then execute that function variable. You can also pass a function definition as an argument to a another function and then execute the resulting parameter as a function. For example, we can do the following:

    a = [45, 67, 23, 12, ... 89]
    sort = ('Selection Sort', Sorts.selection_sort)
    ...
    # Sort a with an function variable.
    description = sort[0]
    func = sort[1]
    print("Sort with {}".format(description))
    func(a)
    print(a)
    

    (See Interlude - Passing Functions for further details.)


  3. Using the test_sort function from above, compare all of the array-based sorts in the Sorts_array.py file. Display the results in the following table:

    n:   100       |      Comparisons       | |         Swaps          |
    Algorithm      In Order Reversed   Random In Order Reversed   Random
    -------------- -------- -------- -------- -------- -------- --------
    Bubble Sort          99     4950     4758        0     4950     2482
    ...
    

    Which of the algorithms given are best and worst in which situation? Is there a best or worst overall algorithm?


  4. Generate a similar table for various linked sorts using the files test_Sorts_List_linked.py and Sorts_List_linked.py. Copy this last file to your data structures project.

    How do the linked sorts compare to the array-based sorts?

    swap.txt contains the linked implementation of the List ADT _swap method. If you don't already have this, add this to your List_linked.py module.

    Test test_Sorts_List_linked.py: