Consider the following sorting algorithm: examSort (A[1. .n]) for i1 to n for j-
ID: 3757228 • Letter: C
Question
Consider the following sorting algorithm: examSort (A[1. .n]) for i1 to n for j-1 to n1 if (Aj AIj+1]) then swap (Al,A+1]) end if end for end for end examSort Express the worst-case running time of this algorithm using big-O notation. Make your bounds as tight as possible. Justify your answer by marking up the code above. True/False Questions True False The examSort algorithm is an in-place sorting algorithm True False The examSort algorithm is a stable sorting algorithm. True False The examSort algorithm is a comparison-based sorting algorithm True False A loop invariant for the outer loop in the examSort algorithm is that Al(n-i+2).n] contains the largest values of the array in sorted order.Explanation / Answer
Given sorting algorithm is the BUBBLE sort algorithm.
Worst case running time of algorithm:
As there is nested for loop used and let suppose an array in which all elements
are unsorted then it will take O(n^2).
in given algorithm n-1 comparision will took to sort first element and n-2 comparision for sort next, so
(n-1) + (n-2) + (n-3) + (n-4) ..... + 3 + 2 + 1
summation = n(n-1)/2
O(n^2)
Even if the array is sorted still it will take O(n) of time that is best time of given sorting algorithm.
TRUE/FALSE
The examSort algorithm is an in-place sorting algorithm : TRUE
in the given algorithm swap the one with another index (swap(A[J],A[J+1])) so modifiaction applying in same array
The examSort algorithm is a stable sorting algorithm : TRUE
yes it stable sorting algorithm because it also comapre the same value at different index and it sorted in correct manner
The examSort algorithm is a comparision-based sorting algorithm : TRUE
yes in examSort (A[J] >= A[J+1]) comapring then only swapping
A loop variant ..... : TRUE
yes for outer loop as they increase element will be in sorted order as every iteration of
algorithm sort ith element.