CPS 6: Lab #8

What you should learn:

• To use Samba to see how different sorting algorithms work differently.

Change into your cps6 directory. Create a lab8 directory and change into that directory. You will need to copy some files in order to do this lab, they are located in ~dr/cps6/lab8 . Copy all the files from that directory into your lab8 directory.

You should now have the following files:

      Makefile       bubblesort.cc  insertsort.cc  scenes.h       sorted
      QUESTIONS      first          scenes.cc      selectsort.cc  

Really SEE the Sorting Process:

In this lab, you'll use the Samba animator to graphically view how three different sorting algorithms work --- bubble sort, insertion sort, and selection sort. We will sort a bunch of integers. Each integer is represented by a tall rectangle. Bigger integers will be represented by taller bars.

First compile all the programs and learn how to run it using the animator. DO NOT MODIFY the scenes.h or the scenes.c file.

Compiling all the programs and using the animator

We've divided the animated Rectangles class into files, scenes.h and scenes.cc. At the same time, the Rectangles class is used by three sorting programs bubblesort.cc, insertsort.cc, and selectsort.cc. You need a special Makefile to compile everything. You should have already copied this Makefile at the beginning of this lab. To compile one program, such as bubblesort, type:

make bubblesort

Notice that make executes the g++ command three times. It compiles scenes.cc first, creating an object file scenes.o, then it compiles bubblesort.cc, creating an object file bubblesort.o, then in the third compile it links bubblesort.o and scenes.o together with the code for other files stored in a library into one executable file called bubblesort.

We'll be using the Samba animator to display the sorting process. The animator will only work under X windows; any of the Sparc 5's should work fine.

To use the animator, you should have first compiled the sorting program(s). Then when the program is running, it outputs animator commands that are understood by the Samba animator.

The sorting programs take 3 inputs, the first one is speed (how fast you want to the animation to be), the second one is how many elements to sort, the third one is the integers that will be sorted.

A Samba windows should appear. You might need to move the Polka Control window so you can see it and the other windows at the same time. To start the animation, click on the button start. To quit at any time, click on the quit button.

After started, it will prompt you to enter the three inputs. For this first run, enter:

 Input the speed you want the animation to be (0-1000, 1000 is slowest)
0
 Input number of elts in array
10
 Enter the elements
10 9 8 7 6 5 4 3 2 1

After all the inputs are entered, the animation will start. When two bars blink simultaneously, they are being compared. Have Fun!

There are two pre-made input files, first and sorted , which will save you some typing. You can use first by typing

Show the UTA:

Show UTA the animation of selectsort on the input file first. Also, explain what the following UNIX command means:

       bubblesort < first  | samba

QUESTIONS file:

One of the files that you have copied is called: QUESTIONS. This file contains several questions which must be answered in that file and then submitted. Load the file in xemacs and answer the questions as you run the simulations.

Submission of programs:

For this lab, you need to submit the QUESTIONS and worst file:

      submit6 lab8 QUESTIONS worst

You should receive a message indicating that the programs were submitted successfully.