I'm working on a program that performs insert sorts and selection sorts on an array of 5 unsorted numbers and a sorted array of 5 numbers and counts the comparisons made on each. I'm still learning about Big O notation, so I'm having a hard time figuring out where a comparison counter should be added (and how many comparisons are done on an array that's already sorted.) Any help would be AWESOMELY appreciated :)
This is my insertion sort, and when performed on a sorted array it makes 0 comparisons:
void insertSort(int &arraysize, int array[], int &comparisons)
{
int j = 0;
int loc = 0;
for (int i = 1; i < arraysize; i++)
{
loc = i;
j =array[i];
comparisons++;
for (; loc > 0 && array[loc-1] > j; loc--)
{
array[loc] = array[loc-1];
comparisons++;
}
array[loc] = j;
}
}
This is my selection sort, on a sorted array it makes 0 comparisons too:
void selectionSort(int &arraysize, int array[], int &comparisons)
{
int last;
int bigIndex;
for(last = arraysize-1; last >= 1; last--)
{
bigIndex = 0;
for (int j = 1; j <= last; j++)
{
comparisons++;
if (array[j] > array[bigIndex])
{
bigIndex = j;
}
}
if (bigIndex !=last)
{
swap(array[last], array[bigIndex]);
}
}
}