CMPT 125 Assignment 2 – Sort and Search Solution
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
(3 marks) and plot a graph (6)
Not shown
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)
The running times (in O Notation) are shown below. The
data in the table and the graph should be in accordance with these.
§ Selection sort sorted – O(n2)
§ Selection sort reversed – O(n2)
§ Selection sort random – O(n2)
§ Insertion sort sorted – O(n)
§ Insertion sort reversed – O(n2)
§ Insertion sort random – O(n2)
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)
// PRE: 0 <= i,j
< length of arr
// PARAM: arr is array whose elements are
to be swapped
// i and j are indexes in the array
// POST: arr[i]
<---> arr[j]
void swap(int arr[], int i,
int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
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)
// PRE: 0 < n < length of arr
// PARAM: arr is array to be sorted
// n is length of arr
// POST: arr is sorted in ascending
order
void ssort_down(int arr[],
int n)
{
for(int
i=n-1; i > 0; i--){
int max = i;
// Find
largest value in unsorted
for(int j = i-1; j >= 0; j--){
if(arr[j] > arr[max]){
max
= j;
}
}
swap(arr, i, max);
}
}
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)
// PRE: 0 <= start <= end < length of arr
// PARAM: arr is array to be searched
for max value
// start, end are
indexes that form a subarray
// POST: returns the max value in arr[start .. end]
int max(int arr[],
int start, int end)
{
// Base case -
last element of subarray
if(start == end){
return end;
}else{
// Find
largest so far
int largest = max(arr, start+1, end);
// Test
current item to see if larger
if(arr[largest] >
arr[start]){
return largest;
}else{
return start;
}
}
}
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)
// PRE: 0 <= n < length of arr
// PARAM: arr is array to be sorted
// n is length of arr
// POST: arr is sorted in ascending
order
void rec_ssort(int arr[],
int n)
{
// Implicit
base case: reached first element
if(len-1 > 0){
//
Replace current element with largest unsorted
int largest = max(arr, 0, len-1);
swap(arr, largest, n-1);
// Move
to next element
rec_ssort(arr,
n-1);
}
}
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)
Examples of
acceptable solutions include:
§ Returns index of target if
found or -1 otherwise
§ Returns i
where arr[i]
= target, if target is not in arr returns
-1
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?
arr[j] != target
for all values of j >= 0 and <= i-1
c) Prove the algorithm is correct using
the initialization-maintenance-termination technique shown in class. (3 marks)
§
Initialization
- the assertion holds since initially i = 0 and there
are no values >= 0 and <= -1, so arr[j] cannot be equal to target
§
Maintenance
– we assume that the assertion holds for some value i,
that is there are no array elements whose indexes are between 0 and i-1 that are equal to the target; we now
demonstrate that the assertion is true for i+1
by noting that if arr[i+1] was equal to the target then the if statement would have been
true and the loop would have ended
§
Termination
- there are two possible results, either some arr[j] == target in which case the function
returns j, or the loop terminates
when i is
equal to n in which case we have
tested each arr[j] for j = 0 to n-1.
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) – Binary search
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)
O(log n). Bob
has to find the files using binary search which is a O(log
n) algorithm; the rest of the process
(actually placing the file in the cabinet and pushing pulling the rest of the
files) is a constant amount of work that is not affected by the number of files
in the cabinet.
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)
O(n). There is no analogous process to pushing or pulling
the files up or down in an array. To insert a value in an occupied position in
an array you would have to first move up by one position every element from the
insertion position to the last element of the array. Similarly to remove a
value and not leave an unoccupied space you would have to first move down by
one position every element above the removal position (where "above"
means with an index greater than the index of the removal point).
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)
Insertion sort, because its running time is O(n) when sorting
(mostly) sorted data.
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.
There is no general
purpose O(n)
sorting algorithm. However, this question does not ask you to write a general purpose algorithm. The key is
that the values range between 0 and n-1,
where n is the size of the array.
These values map to the legal index values for the array. Therefore create a
second array, scan the first array recording the number of appearances of each
value in the temporary array. Then scan the temporary array writing back the
appropriate values to the first.
Taking the second array above as an example the temporary
array would contain {0,0,1,1,2,0,1,1,1,2,1,2} at the end of the process (no 0s,
no 1s, one 2, one 3, two 4s etc.). Then overwrite the original array with those
values (2,3,4,4,6,7,8,9,9,10,11,11}.
PRE: arr contains integer values where
0 <= value < n
POST: sorts arr
from 0 to n in ascending order
constrained_sort(arr[], n)
declare integer
array result[n]
// initialize each element of result
for i = 0 to n-1
result[i] = 0
// for each value k in arr increment results[k]
for i = 0 to n-1
// assert: each result[0..n-1] = number of appearances of each value in arr[0..i-1]
k = arr[i]
result[k] = result[k] + 1
// result[i]
contains the number of incidences of i in arr
// write these values back into arr
next = 0
for i = 0 to n-1
// assert: next
= sum(result[0] … result[i-1])
// assert: arr[next]
= the greatest value for x such that x <= i-1 and arr[x]
> 0
for j = 1 to
result[i]
arr[next]
= i
next++
John Edgar (johnwill@sfu.ca)