Description
Question 1 [30 points]
Write a function that gets an array of 2d-points (see definition in assignment3.h) of length n,
and sorts the array using qsort().
Given two points a=(ax
,ay) and b=(bx
,by) we compare them as follows:
1) if |ax
|+|ay
| < |bx
|+|by
|, then a should come before b in the sorted array.
2) if |ax
|+|ay
| = |bx
|+|by
|, then the point with the lower x coordinate should come first.
3) if |ax
|+|ay
| = |bx
|+|by
|, and ax=bx
, then the point with the lower y coordinate comes first.
Remark: For a point a=(ax
,ay) the quantity |ax
|+|ay
| is sometimes called the “L1
-norm of a” or the
“Manhattan distance” of the point (ax
,ay) from (0,0).
That is, we sort the points according to their Manhattan distance from (0,0) in the increasing
order, and for points at the same distance, then we sort them according to the x-coordinate,
and if also the x-coordinates are equal, we sort according to the y-coordinates.
You need to implement the comparison function, and apply qsort() on the array with this
comparison function.
For example:
- Input: [(3,2), (7,1), (1,1), (-3,4), (-5,0), (-6,2), (-3,4)]
- Expected output: [(1,1), (-5,0), (3,2), (-3,4), (-3,4), (-6,2), (7,1)]
Explanation:
(1,1) has the smallest norm, because 1+1=2
Then we have (3,2) and (-5,0). Both have the same L1
-norm, so we compare them by their
x-coordinate: (-5,0) needs to come before (3,2).
Next comes (-3,4) because its L1
-norm is 7.
(-6,2) and (7,1) have both L1
-norm equal to 8, and -6<7.
**Note that we do allow some points in the array to be equal.
void sort_points(point2d* A, int n);
Question 2 [30 points]
Write a generic implementation of insertion sort.
// the function gets an array of length n of objects of given size
// and a compare function
// The function applies Insertion Sort on the array
// using the compare function
// The function returns the number of swaps made by the algorithm
// if compare (a,b)<0, then a must come before b in the sorted array
// if compare (a,b)>0, then a must come after b in the sorted array
int gen_insertion_sort(void* array, int n, size_t size,
int (*compare)(const void*, const void*));
**Note that the order of the elements in the sorted array depends on the compare function.
Question 3 [40 points: 10 points each]
Write the following three functions:
a) The function gets an array A, two indices of the array, and a boolean predicate pred.
It returns the smallest index i between start and end (including start and end themselves), such
that pred(A[i])==true.
If there is no index i∈[start,end] with pred(A[i])==true, the function returns -1.
You may assume start<= end
int find(int* A, int start, int end, bool (*pred)(int));
b) The function gets an array A, two indices of the array, and a boolean predicate pred.
It returns the number of indices i between start and end (including start and end themselves),
such that pred(A[i])==true.
You may assume start<= end
int count(int* A, int start, int end, bool (*pred)(int));
c) The function gets an array A, two indices of the array, and a function f.
It applies f to each element of A with indices between start and end (including start and end).
You may assume start<= end
void map(int* A, int start, int end, int (*f)(int));
d) The function gets an array A, two indices of the array, and a function f. The function f gets 2
ints and works as follows:
1. Start with accumulator = A[start]
2. For i=start+1...end
accumulator=f(accumulator, A[i])
3. Return accumulator
For example, if f computes the sum of the two inputs, then reduce() will compute the sum
A[start] + A[start+1] +...+A[end].
You may assume start<= end
int reduce(int* A, int start, int end, int (*f)(int,int));
**If start==end, the loop is not executed, and the function just returns accumulator=A[start].