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 assignment5
cd assignment5

Details

Create a program that displays a list of integers as a series of vertical bars on the QT 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 Friday, you should have code for insertion sort and bubble sort. The algorithm for selection sort is in the textbook.

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. There should be 3 buttons at the bottom of the screen, which allows the user to select an algorithm. 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.

Class Structure

A lot of the code you will be using for this assignment will have been written already. Namely, the sorting algorithms. So that means the difficult part of this assignment is the visualization, not the sorts. To force you to plan, I'm going to ask you to pseudocode the main "process" of your program.

For Monday, February 27^th, I want you to turn in (on paper!) a design for the MainWindow class of the program. What attribues do you need for the window? What methods will you need to facilitate the sorting?

This is worth 30 points of your assignment grade. It does not sound like a lot, but they should be 30 easy points to get each week. Do not neglect them.

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. 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 is. At each iteration of the sorting algorithms, change the color of the bars that got moved.

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