As an exercise, determine the complexity of the following algorithm, called sele
ID: 3760654 • Letter: A
Question
As an exercise, determine the complexity of the following algorithm, called selection sort. Array a contains n elements and contains the elements to be sorted. The algorithm works starts at the first position in the array and looks through the array for the smallest element. Once it reaches the end of the array, it puts that element in the first cell of the array. It then restarts the whole process from the second position in the array, and continues until the entire array has been sorted. The function swap obviously swaps the elements in the positions i and j, and has a time complexity of O(1).
int i,j;
int iMin;
for (j = 0; j < n-1; j++) {
iMin = j;
for ( i = j+1; i < n; i++) {
if (a[i] < a[iMin]) {
iMin = i;
}
}
if ( iMin != j ) {
swap(a[j], a[iMin]);
}
}
Explanation / Answer
Worst case time complexity will be
O(n^2), because in the case where array is given in decending order, selection sort will traver n times for n inputs.
So time complexity is O(n^2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.