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++; 
  }
 } 
}
This article has been dead for over six months. Start a new discussion instead.