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); } } // Heres main( ) to show how the sort could be called; dont 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; }