Week of
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.
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.
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.)
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?
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.