# Analysis of Algorithms

## 3. Analysis of Algorithms

Consider the following code for doing insertion sort

#include <iostream> #include <iomanip> #include <string> using namespace std; int count = 0; void insertionSort (int a[], int n) { int i, j, copy; count++; // for the initialization of i in the for loop for (i = 0; count++, i < n-1; count++, i++) { j = i+1; count++; copy = a[j]; count++; while (j > 0 && copy < a[j-1] ) { count++; // for the test to get into the body of the loop a[j] = a[j-1]; count++; j–; count++; } a[j] = copy; count++; } } void print(int a[], int n) { int i; cout << “sorted in ” << count << “steps: “; for (i = 0; i < n; i++) cout << a[i] << ‘ ‘; cout << endl; } int main () { int a[] = {34, 3343, 334, 644, 33, 31, 112, 119}; int n = sizeof(a) / sizeof(int); insertionSort (a,n); print (a,n); return 0; }

For the `insertionSort` subroutine only, do a full summation analysis similar to the one that is done for selection sort, given in the notes to determine the number of steps the sorting algorithm takes. You should end up with a formula in terms of n.