COMP1927 13s1

COMP1927 13s1 Final Exam

Computing 2

Question 4 (6 marks)

Consider the following pair of functions:

int cmp(int a, int b)
{
    return (a-b);
}

void sort(int a[], int n)
{
    int i, j, min;

    for (i = 0; i < n-1; i++) {
        min = i;
        for (j = i+1; j < n; j++) {
            if (cmp(a[j],a[min]) < 0) min = j;
        }
        int t = a[min]; a[min] = a[i]; a[i] = t;
    }
}

Based on the above answer the following questions:

1. How many times will the cmp() function be invoked if the sort() function is called with an array of length 6?

2. How many times will the cmp() function be invoked if the sort() function is called with an array of length n?

3. What is the complexity of the sort() function? (e.g. O(n), O(log n), etc.)

4. Give a C expression that could implement the (cmp(a[j],a[min]) < 0) test more efficiently.

Type the answer to this question into the file called q4.txt and submit it using the command:

submit q4