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 assignment4 under assignments in your cs170 directory. All code for the assignment should be stored in this directory. 

cd ~/cs170/assignments
mkdir assignment4
cd assignment4

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 both insertion sort and selection sort. You will implement bubble sort from the algorithm description below.

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.

Bubble Sort

Bubble sort is actually one of the easiest to understand sorting algorithms. In bubble sort, you simply compare successive elements of the list. If they are out of order, swap them. Then, you compare the next two elements of the list and perform the same process. This process continues until you reach the end of the list.

When you reach the end of the list, you simply start the process over again from the beginning of the list. You continue to do this process (iterating through the entire list, performing the swaps) until you do a full iteration of the list without performing a single swap.

Submission

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

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

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

Last modified: Mon Feb 17 14:21:27 EST 2014