natalie_code/program1/insertionsort.cpp

// Insertion Sort
//
// Author: Rob Gysel
// ECS60, UC Davis
// Adapted from: Lysecky & Vahid "Data Structures Essentials", zyBooks

#include "insertionsort.h"
#include <iostream>
#include <cstdio>

int* InsertionSort(std::vector<int>* numbers){
   int i = 0;
   int j = 0;
   int temp = 0; // Temporary variable for swap
   int comparisonCounter = 0;
   int memAccessCounter = 0;

   static int returnCounters[2];

   for (i = 1; i < numbers->size(); ++i) {
     memAccessCounter = memAccessCounter + 2;
     comparisonCounter++;

      j = i;
      // Insert numbers[i] into sorted part
      // stopping once numbers[i] in correct position
      while (j > 0 && (*numbers)[j] < (*numbers)[j - 1]) {
        comparisonCounter++;
        memAccessCounter = memAccessCounter + 2;

         // Swap numbers[j] and numbers[j - 1]
         temp = (*numbers)[j];
         memAccessCounter++;
         (*numbers)[j] = (*numbers)[j - 1];
         memAccessCounter = memAccessCounter + 2;
         (*numbers)[j - 1] = temp;
         memAccessCounter++;
         --j;
      }
   }
   // return both counters to timealgorithms
   returnCounters[0] = comparisonCounter;
   returnCounters[1] = memAccessCounter;
   return returnCounters;
}