CS 3100 Programming Assignment 2 Comparing Sort Algorithms Finished Program DUE Wednesday October 17 you will not turn in a preliminary version of this program Write a program that REPEATEDLY 1 prompts the user to enter a filename 2 opens the file 3 reads a comment from the first line 4 reads an integer N from the second line e g N 1000 5 reads N integers from the rest of the file putting them into consecutive locations in an array 6 sorts an identical copy of the array using each of the following methods a selection sort b insertion sort c quick sort d heap sort 7 writes the name of the input file 8 writes the comment from the input file 9 writes a report of the number of comparisons done in each sort and the number of swaps done in each sort 10 asks the user if he she wishes to continue UNTIL the user wishes NOT to continue DETAILS You need to arrange to pass in a NEW COPY of your original array to each sorting function because otherwise the first function will be the only one that sorts the original list and the others will just be resorting a list that is already in order When you count swaps count the number of calls to the procedure Swap You will be using code I give to you and that code uses procedure Swap to do all the data moves When counting comparisons count ONLY comparisons of the array contents the things that are being sorted not the array indices The file sorts2 cpp contain all the sort code you need for this program If you wish you can do this assignment just by adding code to sorts2 cpp Data files are on the class web site http www cs csustan edu lamie cs3100 main htm MOTIVATION SAMPLE INPUT and OUTPUT files Working on this program and actually experiencing the differences in runtime is a nice way to get familiar with analysis of algorithms This is an important part of the science in computer science The examples below should be enough to allow you to figure out what you need to make your program do Don t believe the counts in the sample output files They are just made up numbers that I thought seemed plausible CS 3100 Programming Assignment 2 Page 1 of 2 sample inputs Here is a sample input file we will call ran1000 This is a random list of 1000 numbers 1000 233 871 954 23 1245 the file continues 1000 numbers in all starting with 233 compares selection sort insertion sort quick sort heap sort 1225 49 1250 290 swaps 50 0 680 153 TESTING Here is a sample file we will call ord50 This is an ordered list of 50 numbers 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 sample output File Name ran1000 File comment This is a random list of 1000 numbers Here are the results of the sorts selection sort insertion sort quick sort heap sort compares swaps 499500 251000 12000 12450 1000 250000 6500 7453 File Name ord50 File comment Be sure to test your program on large lists up to 1000 elements or more medium size lists small lists ordered lists both ascending and descending order and unordered lists Test all possible combinations of these list characteristics This is a very important aspect It will determine what you learn from this assignment and will also determine a large fraction of your grade In the header of your program include a paragraph or two describing what you learned from writing and testing this program Do your very best to make this well written This will be another aspect of the assignment that will count heavily WHAT TO TURN IN Turn in the source code plus a script that shows the full range of the testing you did For this program do not cat the input files when you make the script of the tests Most of the input files will be way too long for this to be practical If you write the program according to the specifications I gave you and if the comments you put in the input files are intelligible then the information printed by the program will tell me what I need to know about the input files Turn in the program source code and the script by email before midnight Wednesday October 17 This is an ordered list of 50 numbers CS 3100 Programming Assignment 2 Page 2 of 2