CMPT 125 Assignment 2 Sort and Search
This
assignment relates to sorting and searching; it is worth 5% of your final
grade.
Write an insertion sort function and a selection sort
function. Write main and other functions that allows you to time how long each
algorithm takes to sort the following arrays:
§ sorted arrays of size 20,000, 40,000 and 80,000
§ reverse sorted arrays of size 20,000, 40,000 and
80,000
§ arrays of random data of size 20,000, 40,000 and
80,000
Use the shell time
command (look it up using man time)
to time each of the running times. Use the srand and rand functions to produce random data (you will need to include
<stdlib.h>).
Present your result in a table that looks like this:
(3 marks)
|
Selection Sort |
sorted |
reversed |
random |
|
20,000 |
|
|
|
|
40,000 |
|
|
|
|
80,000 |
|
|
|
|
Insertion Sort |
sorted |
reversed |
random |
|
20,000 |
|
|
|
|
40,000 |
|
|
|
|
80,000 |
|
|
|
Plot your results on a graph. The x axis should show the array size and the y axis should show time. You should draw six curves, one for each
combination of sorting algorithm and array organization. (6 marks)
Discuss the running times of each algorithm for each
type of array (sorted, reversed and random), noting the O notation running time
for each. (6 marks)
a) Using C code complete the function shown below that
swaps the values in array elements with indices i and j of an array, arr where arr, i and j are parameters to the function. (2
marks)
void swap(int arr[], int i,
int j) {
//
}
b) Using C code complete the function shown below that
sorts its arr
parameter (the length of which is given by the n parameter). You should use the selection sort algorithm discussed
in class but modified so that it sorts the array from the last legal element down, by repeatedly finding the maximum value and swapping it with the right-most element of the unsorted part
of the array. You should implement the algorithm iteratively, using nested for
loops. (2 marks)
void ssort_down(int arr[], int
n) {
//
}
c) Using C code complete the function shown below that
returns the index of the maximum value in the sub-array of arr from indices start to end where arr,
start and end are parameters to the function. The function must be written recursively and must not contain any
loops. (4 marks)
int max(int arr[], int
start, int end)
{
//
}
d) Using C code complete the function shown below that sorts
its arr
parameter (the length of which is given by the n parameter) using the backwards selection sort algorithm that
behaves in the same way as the function you implemented iteratively in part
(b). Your function should call the two functions that you wrote in parts (a)
and (c). The function must be written recursively
and must not contain any loops. (4 marks)
void rec_ssort(int arr[], int
n) {
//
}
Below is an iterative linear search function that
returns the index of the target if the target is found and -1 otherwise:
// Post:
. . .
int linearsearch(int arr[], int
n, int target) {
for (int i
= 0; i < n; i++) {
// assert:
if (arr[i] == target) return i;
}
return -1;
}
a) Complete the post-condition (1 mark)
b) Complete the assertion; your assertion is correct if
you answer yes to the following two questions: (2 marks)
§ Does the
assertion describe what you know is true after you've run the ith loop?
§ Does the
assertion relate to your post-condition?
c) Prove the algorithm is correct using the
initialization-maintenance-termination technique shown in class. (3 marks)
Bob is still working at the law firm as a junior
associate and is still having to look up client information in the files. Kate
was promoted so Bob took the opportunity to re-re-organize the files and has
again sorted them by last name.
Bob has to find client files by last name. He does
this by looking at the file in the middle of the filing cabinet. If its client name
comes before the name of the client he is looking for in the alphabet he looks
at the file in middle of the back half of the filing cabinet, if its client
name comes after the name he is looking for he looks at the file in the middle
of the front half of the filing cabinet and if the file is the one he is
looking for (the names are the same) he takes it out. He repeats this process
each time he looks at a file, making a mental note of the last two files he
looks at so that he knows which section of the filing cabinet he is going to
find the middle file in. If he gets to a point where he has looked at two files
next to each other then he stops because the file is not in the cabinet (or the
client doesn't exist).
a) What algorithm is this? (1 mark)
b) Bob sometimes has to put new files in the filing
cabinet, or move old files to storage. When he puts new files in the cabinet he
looks for where they go by following the same process described in (a) above. If he finds a file with the
same client name he puts the new file next to it. Otherwise, if he ends up not
finding a file with the same name, and has just looked at two files next to
each other then he puts the new file in between them. When Bob puts a new file
in the cabinet he makes room by simply pushing all the files behind it further
into the file cabinet (with one push), when he removes a file he pulls the
files behind it forward a bit (to keep things tidy). What is the O Notation running
time of this process? (1 mark)
c) Assume that we adapt Bob's insertion and removal
algorithms briefly described in (b)
to insert and remove elements of an array. What is the O notation running time
of the insertion and removal algorithms? Briefly explain your answer. (3 marks)
d) Partners at the law firm occasionally take out files
themselves. When they do this the rarely put them back in the right place.
Because of this Bob has to re-sort the filing cabinet every week. He can't
decide whether to use selection sort or insertion sort to do this. Which of
these two algorithms would you recommend and why? (1 mark)
Question 5 Linear Time Sort:
6 marks
You are to write a pseudo-code algorithm to sort arrays
of integer whose values range between 0 and n-1
where n is the size of the array.
This constraint is an important pre-condition for the algorithm. Here are a
couple of sample arrays:
n = 8: {7, 4, 0, 2, 7, 6, 5, 1}
n = 12: {9, 2, 4, 10, 7, 9, 11, 6, 4, 8, 11, 3}
Your pseudo-code algorithm should be documented with
assertions and comments. Your algorithm
must run in O(n) time.
Assessment
The assignment is out of 45.
Submission
You should submit your assignment online to the CoursSys submission server. Your solution should consist of one .pdf file
that contains the answers to questions 1 to 5 and a .zip (archive) file that
contains the C files that you used to generate the data for question 1. Please
read the documentation on site for further information about submission.
The assignment is due by 11:59pm on Monday the 19th of June.
John Edgar (johnwill@sfu.ca)