The code for the selection sort algorithm, implemented to sort items in ascendin
ID: 3834958 • Letter: T
Question
The code for the selection sort algorithm, implemented to sort items in ascending order, is shown below. Assume the algorithm is given the following input array: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} Match each statement on the left with the formula on the right that best describes the statement's performance in terms of the number of times the statement is executed. You may use the same formula for more than one statement. Pay close attention to where the loop indexes begin and end, and be sure to carefully trace how the code would be executed for the given input. Don't make unwarranted assumptions! You may want to instrument the code to help you with this question. public Comparable[] selectionSort(Comparable[] objArray) { for (int i = 0; i < objArray.length - 1; i++) { Comparable min = objArray[i]; int indexOfMin = i; for (int j = i + 1; j <= objArray.length - 1; j++) { if (objArray[j].compareTo(min) < 0) { min = objArray[j]; indexOfMin = j; } } Comparable temp = objArray[i]; objArray[i] = objArray[indexOfMin]; objArray[indexOfMin] = temp; } return objArray; }
Explanation / Answer
public Comparable[] selectionSort(Comparable[] objArray) {
for (int i = 0; i < objArray.length - 1; i++) { // this FOR loop runs (n-1) times: i=0 to i=length-2
Comparable min = objArray[i];
int indexOfMin = i;
for (int j = i + 1; j <= objArray.length - 1; j++) { // this
if (objArray[j].compareTo(min) < 0) {
min = objArray[j];
indexOfMin = j;
}
}
Comparable temp = objArray[i];
objArray[i] = objArray[indexOfMin];
objArray[indexOfMin] = temp;
}
return objArray;
}
We have two FOR loops. They are nested.
Outer FOR loop runs (n-1) times: i=0 to i=length-2
for each value of i from outer FOR loop: inner FOR loop runs (n-i) times
for i = 0, inner for loop runs: (n-1) times
for i = 1, inner for loop runs: (n-2) times
for i = 2, inner for loop runs: (n-3) times
........
for i = n-2, inner for loop runs: 1 times
So, T(n) = (n-1) + (n-2) + (n-3) + .... + 2 + 1
T(n) = n*(n-1)/2
Big-O = O(n^2)