quicksort.cpp

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

#include "quicksort.h"

int QuickSortCompares=0;
int QuickSortMemaccess=0;

void QuickSort(std::vector<int>* numbers) {
   QuickSortRecurse(numbers, 0, numbers->size() - 1);
}

void QuickSortRecurse(std::vector<int>* numbers, int i, int k) {
   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);
   
   /* Recursively sort low partition (i to j) and
    high partition (j + 1 to k) */
   QuickSortRecurse(numbers, i, j);
   QuickSortRecurse(numbers, j + 1, k);
   
   return;
}

int Partition(std::vector<int>* numbers, int i, int k) {
   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];
   QuickSortMemaccess+=1;
   l = i;
   h = k;
   
   while (!done) {
      
      /* Increment l while numbers[l] < pivot */
	  QuickSortCompares+=1;
	  QuickSortMemaccess+=1;
      while ((*numbers)[l] < pivot) {
         ++l;
      }
      
      /* Decrement h while pivot < numbers[h] */
	  QuickSortCompares+=1;
	  QuickSortMemaccess+=1;
      while (pivot < (*numbers)[h]) {
         --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];
		 QuickSortMemaccess+=1;
         (*numbers)[l] = (*numbers)[h];
		 QuickSortMemaccess+=2;
         (*numbers)[h] = temp;
         QuickSortMemaccess+=1;
         ++l;
         --h;
      }
   }
   
   return h;
}