The code for the selection sort algorithm, implemented to sort items in ascendin

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;
}

int i = 0;

indexOfMin = j;

int i = 0;

0 i < objArray.length - 1 N(N+1)2-1 Comparable min = objArray[i]; n^2 int indexOfMin = i; N-1 int j = i + 1; N+1 j <= objArray.length - 1; N(N+1)(n+2)/6 if (objArray[j].compareTo(min) < 0) N min = objArray[j]; 1

indexOfMin = j;

N(N+1)/2-N j++; Comparable temp = objArray[i]; ObjArray[i] = objArray[indexOfMin] objArray[indexOfMin] = temp; I++; return objArray;

Explanation / Answer

The answer is given below

int i = 0;

indexOfMin = j;

N-1

if (objArray[j].compareTo(min) < 0) this statement is checked everytime when it enters the inner loop hence The net runs are n-1+n(n+1)2 -n=n(n+1)/2-1 the answer.

Please do give a thumbs up and leave any comments in case of doubts.

int i = 0;

1 i < objArray.length - 1 N Comparable min = objArray[i]; N-1 int indexOfMin = i; N-1 int j = i + 1; N-1 j <= objArray.length - 1; N(N+1)/2-1 if (objArray[j].compareTo(min) < 0) N(N+1)/2-1 min = objArray[j]; N

indexOfMin = j;

N j++; N(N-1)/2 Comparable temp = objArray[i]; N-1 ObjArray[i] = objArray[indexOfMin] N-1 objArray[indexOfMin] = temp; N-1 I++;

N-1

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---