CMI-2019-DataScience-B: 15

Question

Consider the following pseudocode for a function that operates on an $N$ element array $A[1],A[2],\dots,A[N]$ of integers.

function mystery (A[1...N])
{
    int i,j,position,tmp;
    for i=1 to N
    {
        position=i;
        for j=i+1 to N
        {
            if(A[j]<A[position])
            {
                position=j;
            }
        }
        tmp=A[i];
        A[i]=A[position];
        A[position]=tmp;
    }
}

1. Explain what effect the function has on the input array $A$.
2. If $N=100$, how many times is the comparison $A[i]<A[position]$ checked?

Answer 1