Exercise 5.1. Consider the array S consisting of 8 elements in the following ord
ID: 3752987 • Letter: E
Question
Exercise 5.1. Consider the array S consisting of 8 elements in the following order: 8, 2, 6, 7, 5, 1, 4, 3. Find the total number of comparisons of the following algorithms take the input.
• SimpleSort (Algorithm 11)
Algorithm 11 Algorithm SimpleSort(X[1 . . . n]). Input: An array X[1 . . . n] of n elements. Output: An ordering of elements of X such that X[1] 6 X[2] 6 . . . 6 X[n].
1: for I = 1 to n do
2: for J = I + 1 to n do
3: if X[J] < X[I] then // Exchange X[I] and X[J]
4: T EMP = X[I]
5: X[I] = X[J]
6: X[J] = TEMP
Explanation / Answer
In The above algoritham we have 2 loops
1st loop is travelling from 1 to n so it wil iterate n times
2nd loop is iterating (n-1)(n-2)(n-3).....(N-n) times so total it will execute n times
so the if conidtion is executed n * n times so no of comparisions are n^2