# 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.

• We can count comparisons by counting how many times the ==, <, and <= operators are called. Since we cannot do this with simple numbers, we are providing you with the class Number to keep track of comparisons. Your sorts should sort `Number` objects instead of simple integers.

• We can count swaps in a similar way by counting how many times the Sorts `_swap` method is called. Note that we also track swaps in the `_shift` method, but this method uses only 1/3 as many lines as swapping, so we only increment the swaps counter by 1/3.

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`: