Question

Consider the following correct implementation of the selection sort algorithm.

public static void selectionSort(int[] elements)


{


for (int j = 0; j < elements. Length - 1; j++)


{


int minIndex = j;


for (int k = j + 1; k < elements. Length; k++)


{


if (elements[k] < elements[minIndex])


{


minIndex = k; // Line 11


}


}


if (j != minIndex)


{


int temp = elements[j];


elements[j] = elements[minIndex];


elements[minIndex] = temp;


}


}


}


The following declaration and method call appear in the same class as selectionSort.


int[] vals = {5, 10, 2, 1, 12};


selectionSort(vals);


How many times is the statement minIndex = k; in line 11 of the method executed as a result of the call to selectionSort ?

Answer 1

The statement minIndex = k; in line 11 of the selectionSort method is executed n*(n-1)/2 times, where n is the length of the elements array.

Step-by-step explanation:

This is because the inner loop starts at j+1 and iterates through the remaining elements in the array. In the first iteration of the outer loop, the inner loop iterates n-1 times. In the second iteration of the outer loop, the inner loop iterates n-2 times, and so on. The total number of iterations of the inner loop is:

(n-1) + (n-2) + ... + 2 + 1

= n*(n-1)/2

Therefore, the statement minIndex = k; in line 11 is executed n*(n-1)/2 times in the selectionSort method.

In the specific case of the vals array given in the question, which has length 5, the statement minIndex = k; in line 11 is executed 5*(5-1)/2 = 10 times.