Design Problem Design and implement two methods. Each method will sort a list of
ID: 3595446 • Letter: D
Question
Design Problem
Design and implement two methods. Each method will sort a list of integers, keeping track of the number of times a specific operation occurs during the sorting process. This information will then be used to compare the performance of the two sorting methods. You will also need a test driver for purposes of input, calling the methods, and possibly output, depending on your method implementations.
Input
Input consists of a text data file, sortlist.txt, which contains unique integers in the range 1 to 300, written one value per line. The maximum number of values in the file is 300, but in practice will be many fewer.
Output
The output will be the list of integers sorted into ascending order. Also output will be the number of assignment statements that were made which assigned (not input) a value into an array. Details below will make this clearer.
Structures
A simple 1-dimensional array is suitable for this assignment.
Method 1 – Sort by address calculation, or perfect hashing
This sort runs in linear time, and is thus very fast. It is restricted to lists of unique (unduplicated) items (integers in our case) that extend over a manageable range. The range of the numbers must be manageable in the sense that we must have enough memory to be able to allocate one unit of memory for each number that might be in the list, whether or not it actually turns to be there. For example, if we are sorting 200 numbers that range from 1 to 9999, we must allocate 9999 units of memory, even though 9799 of the locations are never used.
So, if we are working with integers, we first set each element of an appropriately sized array to 0. As a data value is read from the file, it is placed into its unique spot (e.g., if 57 is read, it is stored in location 57 of the array). To write out the (now) sorted list, scan the array, picking out only nonzero items.
Count each assignment that is made into the array. Giving this a little thought, you know that if the file contains N values, there will be N assignments into the array.
Method 2 – Insertion sort
You will find many implementations of Insertion sort on the Internet. Advice 1: Develop your own algorithm as described below. Advice 2: Do not claim something taken (stolen!) from the Internet as your own work. Advice 3: Make certain you understand how Insertion works.
The insertion sort algorithm can be used to sort numbers in place; that is, not storage (other than one temporary location) is needed other than the space used to hold the unsorted numbers. Sorted values are placed above unsorted ones in a systematic way that never overwrites a value before it is processed. Suppose that a sort of 10 integers has been partially completed to the point that the first thee are in order.
5
12
sorted numbers
23
7
first number not yet sorted
29
19
16
33
4
19
To place the next unsorted number, 7, in its proper place, we must make room to insert it between the 5 and the 12, and we must carefully create the “hole” needed so as not to disturb the ordering of 12 and 23. This can be done by copying the 7 to a temporary location, moving 23 and then 12 down one position, and then inserting the 7 into the position vacated by 12.
But how did we know that the 7 goes between the 5 and the 12 rather than somewhere else? Clearly, a test of some kind must be made in order to find the proper place. What must be done is to scan upward from the number at the end of the partially sorted list, 23 in the diagram, until either we find a number smaller than or equal to the number we are trying to insert or else we come to the top of the list.
The loop that contains this test can and should be the same loop that moves sorted numbers downward. (You might also think of this as moving a hole upward until it reaches the proper place for inserting a new value.) Sometimes the loop will have to move all currently sorted values down one, as it will have to do when it comes to the 4, and sometimes it is lucky enough that the next number can be tacked onto the end of the partially sorted list, as will happen when it is time to insert 29 and, later, 33. Even though we showed a partially sorted list as a starting point, you should be able to determine how to start the process with an unsorted list.
Again, keep a count of assignments made into the array as items are moved and inserted (not input).
Submission details:
A word processed document describing the results of your experiment – namely how many assignment operations were done for each of the sorting methods. What conclusions can you draw from the results? Is it “fair” to compare methods on the number of assignment operations? After all, it appears Insertion sort has to work a lot harder.
5
12
sorted numbers
23
7
first number not yet sorted
29
19
16
33
4
19
Explanation / Answer
I will be using python for this experiment.I have written code for reading the file getting data out of it.Applying both techniques and Printing time take and number of assignments and comparisons.
If you want to add something else please comment I am available to help.
Thank you.