natalie_code/quicksort.cpp

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

#include "quicksort.h"

int* QuickSort(std::vector<int>* numbers) {
  int comparisonCounter = 0;
  int memAccessCounter = 0;
  static int returnCounters[2];

  QuickSortRecurse(numbers, 0, numbers->size() - 1, &comparisonCounter, &memAccessCounter);

  returnCounters[0] = comparisonCounter;
  returnCounters[1] = memAccessCounter;
  return returnCounters;
}

void QuickSortRecurse(std::vector<int>* numbers, int i, int k, int *comparisonCounter, int *memAccessCounter) {
   int j = 0;

   /* Base case: If there are 1 or zero elements to sort,
    partition is already sorted */
   if (i >= k) {
      return;
   }

   /* Partition the data within the array. Value j returned
    from partitioning is location of last element in low partition. */
   j = Partition(numbers, i, k, comparisonCounter, memAccessCounter);

   /* Recursively sort low partition (i to j) and
    high partition (j + 1 to k) */
   QuickSortRecurse(numbers, i, j, comparisonCounter, memAccessCounter);
   QuickSortRecurse(numbers, j + 1, k, comparisonCounter, memAccessCounter);

   return;
}

int Partition(std::vector<int>* numbers, int i, int k, int *comparisonCounter, int *memAccessCounter) {
   int l = 0;
   int h = 0;
   int midpoint = 0;
   int pivot = 0;
   int temp = 0;
   bool done = false;

   /* Pick middle element as pivot */
   midpoint = i + (k - i) / 2;
   pivot = (*numbers)[midpoint];
   *memAccessCounter = *memAccessCounter + 1;

   l = i;
   h = k;

   while (!done) {

      /* Increment l while numbers[l] < pivot */
      while ((*numbers)[l] < pivot) {
        *comparisonCounter = *comparisonCounter + 1;
        *memAccessCounter = *memAccessCounter + 1;
         ++l;
      }

      /* Decrement h while pivot < numbers[h] */
      while (pivot < (*numbers)[h]) {
        *comparisonCounter = *comparisonCounter + 1;
        *memAccessCounter = *memAccessCounter + 1;
         --h;
      }

      /* If there are zero or one elements remaining,
       all numbers are partitioned. Return h */
      if (l >= h) {
         done = true;
      }
      else {
         /* Swap numbers[l] and numbers[h],
          update l and h */
         temp = (*numbers)[l];
         *memAccessCounter = *memAccessCounter + 1;
         (*numbers)[l] = (*numbers)[h];
         *memAccessCounter = *memAccessCounter + 2;
         (*numbers)[h] = temp;
         *memAccessCounter = *memAccessCounter + 1;

         ++l;
         --h;
      }
   }

   return h;
}