Lab Assignment 5
Due Thursday December
3 10:00 pm
Purpose:
Write a C++ program to implement the InsertionSort algorithm, and adapt
it to count the number of comparisions performed.
Project Description:
The InsertionSort algorithm was given in class as follows:
- L <-- 2
- while L <= n
- j <-- L
- while j>=2 and a[j]<a[j-1]
- swap a[j] <-->
a[j-1]
- j
<--
j-1
- L <-- L+1
- stop
In the above pseudocode, I have ignored the input and output
tasks. Assume, as usual, that the computing agent wakes up with
the integer n, and the
input list a[1]...a[n]
already stored. Take a few moments to re-familiarize yourself
with this algorithm by tracing it on some simple examples.
Your task in this project is to implement this algorithm as a C++
program. Use the SelectionSort.cpp
or BubbleSort.cpp programs from the
examples section of the webpage as a starting point for your
project. Begin by replacing the section of the program which
performs the sort with your translation of the above pseudocode into
C++. Also change the declarations section of the program as
appropriate for the variables you are using. Compile and test
your program at this stage to make sure there are no syntax errors, and
to make sure the sort is being performed correctly. It is very
important that you not wait until the project is complete to start
testing. By compiling and testing as you go, you narrow the
location of any errors that may (and probably will) occur, making them
easier to find and fix.
Next add an int variable
called count which is
initialized to be zero. Use this variable to count the number of
array comparisons that take place in any run of the program, i.e. count
the number of times the expression a[j]<a[j-1] is
evaluated in the while-loop test on line 4 of the
algorithm. To do this you must increment count every time
that the test is performed (not just every time it is true). Add
a
cout statement which
prints out the final value of count,
then test the program on some small lists to check that the count is
accurate.
A sample run of your program at this stage would look like this:
%
InsertionSort
Enter list length (must be less than or equal to 100): 5
Enter 5 numbers:
1 5 2 4 3
Number of comparisons: 8
1 2 3 4 5
Finally, adapt your program to handle large lists. Increase
the constant macro MAX_LIST_LEN to 2000, then delete the
code that prints the prompts to the user, and then delete the code that
prints out the sorted list. Leave in the code which prints out
the number of comparisons performed. You will run your program on
large sets of data by placing that data in a file, then redirecting the
input to come from that file, rather than the keyboard. (To learn
how to re-direct input to come from a file rather than the keyboard,
read Chapter 3 of the Unix Tutorial for
Beginners.) Note that
what is stored in the file must be exactly what you would
have typed at the keyboard, so in particular, the first number in the
file will be a positive integer giving the number n of numbers to be sorted.
The next n numbers in the
file constitute the input list. A sample input file and
corresponding
program output is given below:
File infile:
100
637 734 383 916 614 296 635 533
995 273
942 685 285 547 801 285 483 180
746 231
594 324 996 451 229 755 603 157
582 166
875 226 669 364 586 714 184 790
294 161
544 221 792 553 934 174 924 478
712 236
550 364 207 453 222 572 141 755
442 818
128 108 761 163 154 460 821 477
244 899
820 327 479 311 118 234 113 197
752 594
690 895 568 977 668 368 963 768
255 966
200 811 724 979 587 287 220 297
303 683
Sample run:
% InsertionSort < infile
Number of comparisons: 2619
Test your program in this manner on several large data sets, containing
at least 1000 but no more than 2000 numbers. Use the website
mentioned in lab3 to generate large lists of random numbers.
Follow this link to see some other
examples of sample input and output.
What to Turn In:
Submit your source code for InsertionSort.cpp to the
assignment name 'lab5'.
If you find any errors, please report them to: ptantalo@soe.ucsc.edu
webmaster@soe.ucsc.edu
Back to the SOE Class
Home Pages
Back to the SOE Home Page