Bubble Sort

sorts.py and main.py: 10 points

For our final trick, we’ll add another sorting algorithm to our repertoire. This addition lets us test that we’ve really designed our program in such a way that it can be readily extended without having to be totally rewritten.

How to Add a New Sorting Algorithm

Adding a new sort involves updating our code in at least three places:

  • Add a function definition to sorts.py.
  • Add a test of the new sort to the body of sorts.py.
  • Update the menu and code in main.py.

If everything has gone according to plan, the above steps should be enough to get your new sort working. (If not, this exercise will become an opportunity to find and fix mistakes.)

1. Define the new algorithm

Open sorts.py and write code to complete the stub for bubble_sort_demo. Your approach should be similar to what you did for Selection Sort and Insertion Sort. As a reminder refer to the code you used to create your hand-drawn visualization in the Warmup, but modify it to:

  • take a DataSet (or VisualDataSet) object instead of a list;
  • call the display() method of your DataSet or VisualDataSet object every time two values swap places;
  • include an appropriate docstring.

2. Test our new sort

In the main body of sorts.py, add code to set the values of your test_data object back to [8, 6, 4, 2, 0, 1, 3, 5, 7, 9] and call the demo_test on your new sort. Inspect the resulting text-based visualization to make sure it’s behaving the way you expect. Use the provided list of values, the relevant terminal output should be:

*******************************************************************************
Testing bubble_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	

6	4	8	2	0	1	3	5	7	9	

6	4	2	8	0	1	3	5	7	9	

6	4	2	0	8	1	3	5	7	9	

6	4	2	0	1	8	3	5	7	9	

6	4	2	0	1	3	8	5	7	9	

6	4	2	0	1	3	5	8	7	9	

6	4	2	0	1	3	5	7	8	9	

4	6	2	0	1	3	5	7	8	9	

4	2	6	0	1	3	5	7	8	9	

4	2	0	6	1	3	5	7	8	9	

4	2	0	1	6	3	5	7	8	9	

4	2	0	1	3	6	5	7	8	9	

4	2	0	1	3	5	6	7	8	9	

2	4	0	1	3	5	6	7	8	9	

2	0	4	1	3	5	6	7	8	9	

2	0	1	4	3	5	6	7	8	9	

2	0	1	3	4	5	6	7	8	9	

0	2	1	3	4	5	6	7	8	9	

0	1	2	3	4	5	6	7	8	9	

Demo complete.
Sorted: True

3. Update the main menu

If the demo seems to be working correctly, it’s time to make it available to our users. To do this, edit main.py and add Bubble Sort to your list of sort options:

Welcome to the sorting algorithm visualization tool!
The following algorithms are available:
    1: Selection Sort
    2: Insertion Sort
    3: Bubble Sort
Please enter your selection:

Again, make sure your code continues to handle user errors appropriately and prompts the user repeatedly until they select a valid option.

Go ahead and make any additional edits you need to your logic so your program will run bubble_sort_demo when requested by the user, in either text-based or graphical modes.

Finally, run the program yourself to verify that it works for both the text-based and graphical visualizations. By holding down the Enter key in the terminal window, you should be able to run a graphical demonstration of Bubble Sort that resembles the example below:

Bubble Sort Demo

(Don’t worry if your display flickers a little as it runs. This is a normal result of the way we redraw our background with each update.)

Hooray!

If you’ve made it this far you have completed the required portion of the Final Lab. Give yourself a pat on the back, and feel free to head straight to the Wrap-Up.

Of course, if you ever need more computery adventures, the Extra Credit Section awaits…