Basic Sorting Visualizations

sorts.py: 25 points

Objective

Now that we have created our DataSet class, we’ll use it to set up and test simple, text-based visualizations of selection sort and insertion sort. Once we’re confident that our program works on text-based simulations, we can move on to adding graphics.

Overview

Open the file sorts.py. It contains stubs for the following functions:

  • selection_sort_demo
  • insertion_sort_demo
  • demo_test

We’ll begin by completing the demo_test function so we have a nice way to check whether our other functions are working. Then we’ll implement selection_sort_demo and test it. Finally, we’ll implement insertion_sort_demo and make some modifications to our tests to make it easier to verify that we’re getting the behavior we expect.

demo_test

Part of this function has already been completed for you. As its docstring explains, it accepts a DataSet object and a sorting demo function and tests the function on the DataSet object. In the main body of body of the program you can see that we are currently calling our demo_test function on the DataSet object test_data and the function insert_sort_demo. (Note that, as you saw in Section C of the Warmup, we are again using the trick of passing the name of a function into another function as an argument here.) Since the function is not yet fully implemented, the current output should look something like this:

*******************************************************************************
Testing insertion_sort_demo
-------------------------------------------------------------------------------
Initial data values:
Sorted: ???
Running demo...
Demo complete.
Sorted: ???

Follow the instructions given in the comment lines marked TODO to complete this test function. There are four in total. When you are finished, running python3 sorts.py should produce output very similar to the following:

*******************************************************************************
Testing selection_sort_demo
-------------------------------------------------------------------------------
Initial data values:
[3, 2, 2, 1, 10, 0, 0, 4, 1, 0]
Sorted: False
Running demo...
Demo complete.
Sorted: False

Note that running the demo function has no effect right now, since you haven’t yet implemented selection_sort_demo. We’re about to fix this!

selection_sort_demo(data)

This function accepts a DataSet object, data, and sorts it using the Selection Sort Algorithm. To implement it, refer to the code for Selection Sort you used to create your hand-drawn visualization in the Warmup. Complete the selection_sort_demo function by modifying this code as follows:

  • Instead of a list, it should be altered to work with a DataSet object.
  • The comment that asks you to draw the current state of the list of values should be replaced by a call to the display() method of the DataSet object you are sorting.
  • Don’t forget to write an appropriate docstring with a summary, parameters and return values. Docstrings are required and will be graded as part of your submission.

When you’ve finished, running python3 sorts.py should walk through a text-based visualization of the steps to sort your data using selection sort. For example:

*******************************************************************************
Testing selection_sort_demo
-------------------------------------------------------------------------------
Initial data values:
[2, 8, 7, 2, 3, 5, 1, 1, 9, 6]
Sorted: False
Running demo...
1	8	7	2	3	5	2	1	9	6	

1	1	7	2	3	5	2	8	9	6	

1	1	2	7	3	5	2	8	9	6	

1	1	2	2	3	5	7	8	9	6	

1	1	2	2	3	5	7	8	9	6	

1	1	2	2	3	5	7	8	9	6	

1	1	2	2	3	5	6	8	9	7	

1	1	2	2	3	5	6	7	9	8	

1	1	2	2	3	5	6	7	8	9	

Demo complete.
Sorted: True

insertion_sort_demo(data)

Once Selection Sort is looking good, repeat the same process to implement insertion_sort_demo. Similar to our selection_sort_demo, it should take a DataSet object and sort it, this time using the Insertion Sort Algorithm.

Before you get started, edit the last line in the main body of the program so demo_test runs on insertion_sort_demo instead of selection_sort_demo. This change will allow you to continue to test your work as you go. Try running python3 sorts.py again to make sure you’re testing the right function.

Again, you should start with the code you were given in the Warmup, and modify it so your insertion_sort_demo:

  • takes a DataSet object instead of a list;
  • calls the display() method of the DataSet object you are sorting each time it assigns the current key to a place in the list;
  • has an appropriate docstring.

Regression tests with set_data

At this point, you should have two working sorting demos and a test that runs them on a small set of randomly generated values. The last thing we need to do is verify that each of the visualizations is actually following the appropriate algorithm to sort the data. One approach would be to read through the output and verify each steps by hand. This isn’t a bad idea, but it’s a bit tedious and error prone. An automated check would be better, but writing comprehensive automated tests is also very hard.

Nonetheless, it would be nice to have a quick way of spot checking our answers that at least works for a simple case. A test like this is called a “regression test.” It isn’t intended to be foolproof, but it does help increase our confidence that our code is working the way we want. These kinds of tests are very commonly used by software developers. Whenever we make modifications to existing code and want to make sure we didn’t break anything or introduce unintended changes to basic functionality, we can use this testing approach.

We can create basic regression tests for our selection_sort_demo and insertion_sort_demo functions by picking a fixed example dataset to check them against and verifying that the output matches our expectations. To achieve this, replace the code in the main body of the program (under if __name__ == "__main__":) so it does the following:

  • Creates a DataSet object and the replaces the random values with the following list: [8, 6, 4, 2, 0, 1, 3, 5, 7, 9]. (You should be able to use the set_data method for this.
  • Run demo_test on this DataSet object and selection_sort_demo.
  • Reset the values of the DataSet object back to [8, 6, 4, 2, 0, 1, 3, 5, 7, 9].
  • Run demo_test again, this time using insertion_sort_demo.

If all goes well, python3 sorts.py should give you the following output:

*******************************************************************************
Testing selection_sort_demo
-------------------------------------------------------------------------------
Initial data values:
[8, 6, 4, 2, 0, 1, 3, 5, 7, 9]
Sorted: False
Running demo...
0	6	4	2	8	1	3	5	7	9	

0	1	4	2	8	6	3	5	7	9	

0	1	2	4	8	6	3	5	7	9	

0	1	2	3	8	6	4	5	7	9	

0	1	2	3	4	6	8	5	7	9	

0	1	2	3	4	5	8	6	7	9	

0	1	2	3	4	5	6	8	7	9	

0	1	2	3	4	5	6	7	8	9	

0	1	2	3	4	5	6	7	8	9	

Demo complete.
Sorted: True
*******************************************************************************
Testing insertion_sort_demo
-------------------------------------------------------------------------------
Initial data values:
[8, 6, 4, 2, 0, 1, 3, 5, 7, 9]
Sorted: False
Running demo...
6	8	4	2	0	1	3	5	7	9	

4	6	8	2	0	1	3	5	7	9	

2	4	6	8	0	1	3	5	7	9	

0	2	4	6	8	1	3	5	7	9	

0	1	2	4	6	8	3	5	7	9	

0	1	2	3	4	6	8	5	7	9	

0	1	2	3	4	5	6	8	7	9	

0	1	2	3	4	5	6	7	8	9	

0	1	2	3	4	5	6	7	8	9	

Demo complete.
Sorted: True