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]);
}
}
}``````

What do you mean that it makes 0 comparisons? Because compiling as-is with a simpler driver, I get reasonable comparison results.

What do you mean that it makes 0 comparisons? Because compiling as-is with a simpler driver, I get reasonable comparison results.

Sorry! I was moving the comparison counter around and posted the wrong version of each. Thanks for pointing that out. Do you think the version I left up there is correct (assuming sorted arrays get compared regardless)? The one I've been using is below and does leave 0 comparison results for a sorted array:

Insertion Sort:

``````void insertSort(int &arraysize, int array[], int &comparisons)
{
int j = 0;
int loc = 0;
comparisons = 0;

for (int i = 1; i < arraysize; i++)
{
loc = i;
j =array[i];

for (; loc > 0 && array[loc-1] > j; loc--)
{
array[loc] = array[loc-1];
comparisons++;
}
array[loc] = j;
}

}``````

Selection Sort:

``````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++)
{

if (array[j] > array[bigIndex])
{
bigIndex = j;
}
}
if (bigIndex !=last)
{
swap(array[last], array[bigIndex]);
comparisons++;
}
}
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.