Visual Sorting

When implementing an algorithm, it is very important to fully understand the inner workings. However, it is sometimes difficult to wrap your head around those inner workings, especially when all you have is a textual description that describes the algorithm. It is often very helpful to visualize the process, to clarify any nuances of the actual algorithm. You are going to do exactly that with this assignment.

Setup

Create a directory assignment5 under assignments in your cs170 directory. All code for the assignment should be stored in this directory.

cd ~/cs170/assignments
mkdir assignment5
cd assignment5

Details

Create a program that displays a list of integers as a series of vertical bars on the tkinter window. You can specify (as global constants) the width and height of the window. However, you should scale the size of the bars such that the largest integer in the list fills the entire height of the window. You should also scale the locations of the bars, so that the item at index 0 of the list appears on the left edge of the window, and the item at the end of the list appears on the right edge of the window.

You are also going to write three different sorting algorithms: insertion sort, selection sort, and bubble sort. By the end of class on Monday, you should have code for insertion sort, selection sort, and bubble sort.

Once you have these two key pieces in place, you can get to the main portion of your program: the visualization. Your program will generate a shuffled list of integers, and store that to be drawn. Your program should then allow the user to select a sorting algorithm to execute. The simplest way to accomplish this is by assigning each algorithm to a keyboard key. For example, assign the "q" key to selection sort, the "w" key to insertion sort, and the "e" key to bubble sort. For each iteration of the sorting algorithm, the window displaying the list should be re-drawn. This allows the user to visually watch the sorting taking place. An iteration for selection sort is one selection, for insertion sort is one insertion, and for bubble sort is one swap.

The user should be able to pick a new algorithm at any point AFTER the previous choice of algorithms has fully finished. This should start the newly selected algorithm on the same, previously shuffled list. This way the user can view how different algorithms behave on the same list. You will get weird behavior if you do not wait until the first algorithm finishes.

Submission

You are required to submit a tar file to http://inquire.roanoke.edu/. On cseval, there is a link for Assignment 5. You can create a tar file by issuing the following commands:

cd ~/cs170/assignments
tar czvf assignment5.tgz assignment5/

"Hacker" Prompt

1. Buttons: This is more of an asthetic choice, but I don't like arbitrarily chosen keys to represent the sorting algorithms. Instead, it would be nice if there were some tk buttons on the tk window, which allowed the user to simply click on which algorithm they wanted to visualize. Look up the documentation for tk buttons, and add the three necessary buttons (with correct behaviors) to the tk window.

2. More Detailed Visuals: Once you get above a certain list size, it becomes a little hard to tell which elements are actually being moved during each iteration of the program. And this program isn't quite colorful enough, as it. At each iteration of the sorting algorithms, change the color of the bars that got moved.

3. Comb Sort: A sorting algorithm called comb sort was recently developed. The core concept is based on bubble sort, but changes the distance between elements being compared for each swap procedure. The Wikipedia page for comb sort provides all the information necessary to implement it. Add this sorting method to the potential sorting algorithms.