Solution:
Question No. 01: The name of the algorithm being used for sorting the given array has given below.
Selection sort
Question No. 02: The Pseudo code for the algorithm used for sorting the given array has given below.
Pseudo code:
1 Selection sort (A)
{
2 For i 1 to A.lenght-1
{
3 imin i
4 for j i+1 to A.length
{
5 If (A[j] < A[imin])
Imin j
}
6 Temp A[i]
7 A[i] A[imin]
8 A[imin] Temp
}
}
Question No. 03: The step by stem analysis of the algorithm designed in question 2 is as follow,
The time taken by each statement (step) is given as follows,
Selection sort (A)
Cost
Times
{
For i 1 to A.length-1 |c1 | n
{
imin i--------------------> c2 n-1
for j i+1 to A.length
{ c3 n+n-1+…1=n(n+1)/2
If (A[j] < A[imin])
imin j
}
Temp A[i] c4 n-1
A[i] A[imin] c5 n-1
A[imin] Temp c6 n-1
}
}
Total time T(n) can be calculated as follows,
T(n)= c1n+c2(n-1)+c3(n(n+1)/2)+c4(n-1)+c5(n-1)+c6(n-1)
c1n+c2n-c2+c3 (n2+n/2) +c4n-c4+c5n-c5+c6n-c6 collect the like terms
c3n2/2+ (c1+c2+c3/2+c4+c5+c6) n + (-c2-c4-c5-c6)
This is equivalent to a polynomial an2+bn+c
Therefore T (n) = Big O (n2) by taking the highest order term of the equation.
Note: a, b, c in polynomial represents constants
// Ignoring constant terms
T(n) = O (n2)
