#include "QuickSort.h" #include using namespace std; //------------------------------------------------------------------------------------------------- // Function Name: QuickSort // Purpose: QuickSort constructor initializes the sort table // Parameters: int* theValues in the unsorted list // Returns: none // Pre-conditions: none // Post-conditions: theList contains a pointer to the unsorted list //------------------------------------------------------------------------------------------------- QuickSort::QuickSort(int theCount, int* theList) { this->theCount = theCount; this->theList = theList; } //------------------------------------------------------------------------------------------------- // Function Name: ~QuickSort // Purpose: ~QuickSort destructor performs house cleaning when the class is destroyed // Parameters: none // Returns: none // Pre-conditions: none // Post-conditions: none //------------------------------------------------------------------------------------------------- QuickSort::~QuickSort() { if (theList != nullptr) delete[] theList; theCount = 0; theList = nullptr; } //------------------------------------------------------------------------------------------------- // Function Name: sort // Purpose: sort the list using the Quick Sort algorithm // Parameters: none // Returns: none // Pre-conditions: theList contains a valid pointer to an array of ints // Post-conditions: theList is sorted //------------------------------------------------------------------------------------------------- void QuickSort::sort() { if (theCount <= 1 || theList == nullptr) return; // sort the whole list starting with the first element through the last element internalSort(0, theCount - 1); } //------------------------------------------------------------------------------------------------- // Function Name: internalSort // Purpose: internalSort is recursively called using a divide and conquer strategy to // sort the list // Parameters: int left is the left starting position in the list // int right is the right starting position in the list // Returns: none // Pre-conditions: theList contains a valid pointer to an array of ints // Post-conditions: theList is sorted //------------------------------------------------------------------------------------------------- void QuickSort::internalSort(int left, int right) { // chose the pivot point to be the middle element (left + (right - left) /2) int pivotIndex = left + (right - left) / 2; int pivotValue = theList[pivotIndex]; int tmpLeft = left; int tmpRight = right; // partition the values with: // those smaller than the pivot to the left // those larger than the pivot to the right while (left <= right) { // skip values that are less than the pivot while (theList[left] < pivotValue) { left++; } // skip values that are greater than the pivot while (theList[right] > pivotValue) { right--; } // swap the values if the left hasn't crossed the right if (left <= right) { swap(theList[left], theList[right]); left++; right--; } } // continue to recursively call internalSort while the left hasn't crossed the pivot point if (tmpLeft < right) { internalSort(tmpLeft, right); } // continue to recursively call internalSort while the right hasn't crossed the pivot point if (tmpRight > left) { internalSort(left, tmpRight); } } //------------------------------------------------------------------------------------------------- // Function Name: saveList // Purpose: saves the list (sorted or unsorted) to the specified filename // Parameters: const char* filename is the filename to write the list to // Returns: true if successful, false otherwise // Pre-conditions: filename is not null // Post-conditions: none //------------------------------------------------------------------------------------------------- bool QuickSort::saveList(const char* filename) { if (filename == nullptr) return false; ofstream outFile(filename); //outFile.open(filename); if (!outFile.good()) return false; if (theList == nullptr) { theCount = 0; outFile << "theList was null. nothing to save." << endl; } for (int x = 0; x < theCount; x++) outFile << theList[x] << endl; outFile.close(); return true; }