Given below is C++ code for an algorithm named sort (with accompanying algorithm

Question

Given below is C++ code for an algorithm named sort (with accompanying algorithms/code called reverseSegment and minInSegment) that sorts positive integers into descending order. Give the running time both in terms of T(n) and O(n) for these algorithms/code. Clearly explain how you arrived at your answer.

// Reverse order of elements in A from positions 0 to num (inclusive)

void reverseSegment(int A[], const int num)

{

int temp, j = num;

for (int i = 0; i < --j; i++)

{

temp = A[i];

A[i] = A[j]; A[j] = temp;

}

}

// Return position of minimum value element in A between

// positions i and j (inclusive)

int minInSegment(const int A[], const int i, const int j)

{

int positionOfMin = i;

for (int k = i+1; k <= j; k++)

if (A[k] < A[positionOfMin])

positionOfMin = k;
return(positionOfMin);
}
void sort(int A[])
{
int positionOfMin, count = 0;
if (N < 2) return; // nothing to sort
for (int i = N; i > 1; i--)
{
positionOfMin = minInSegment(A, 0, i-1);
if (positionOfMin == i-1)
continue;
if (positionOfMin > 0)
{
count++;
reverseSegment(A, positionOfMin + 1);
}
count++;
reverseSegment(A, i);
}
}
// Here’s main( ) to show how the sort could be called; don’t analyze the runtime of main!
int main()
{
int A[N]; // assume N has been defined as a const in the program
srand(time(NULL));
// Initialize data array A with values from 1..100
cout << "Input data: ";
for (int i = 0; i < N; i++)
{
A[i] = (rand() % 100) + 1;
cout << A[i] << " ";
}
cout << endl;
sort(A);
cout << " Data sorted: ";
for (int i = 0; i < N; i++)
cout << A[i] << " ";

cout << endl;
return 0;
}

Explanation / Answer

The for loop in sort function runs for n times and for each iteration of the loop function calls function minInSegment and function reverseSegement. So, the overall time complexity is

n*(time complexity of minInSegment + time complexity of reverseSegment)

In worst case, running time of minInSegment will be n and of reverseSegment is 3*n. So, overall time complexity is given as:

t(n) = n*(n+3n) = 4*n2 = O(n2).

Hope it helps, feels free to comment in case of any query.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.