C++ Templated QuickSort Algorithm

Mar 19, 2009 in BLOG • CODE
algorithms c#
2 min read

It has been over a month since I posted. I’ve been really busy with all of my classes.

So, instead of going too in depth with anything, I’m just going to share some code we’ve written. This is a QuickSort Algorithm that we adapted from the MIT Intro to Algorithms book. We just finished it last night (less than 12 hours ago), so it’s not fully tested.

#ifndef _QUICKSORT_H
#define _QUICKSORT_H
#include <vector>
using namespace std;

namespace QuickSort
{
/* 
    QuickSort Algorithm using Templates

    Algorithm was adapted from:
        Introduction to Algorithms
        By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
        Contributor Thomas H. Cormen
        Edition: 2, illustrated
        Published by MIT Press, 2001
        ISBN 0262032937, 9780262032933
        1180 pages
    Accessed March 2009
    via http://books.google.com/books?id=NLngYyWFl_YC
    See pages 145-147

*/
    template<class T>
    class QuickSort
    {
    public:
        vector<T> *sortingArray;
        int left;
        int right;
 
        // Constructors
        QuickSort();
        QuickSort(vector<T> *sortArray);
        QuickSort(vector<T> *sortArray, int startIndex, int endIndex);
 
        /**********************************************************************
        * Partition and Swap Functions
        **********************************************************************/
        int Partition(vector<T> *sortArray, int startIndex, int endIndex);
        void Swap(int l, int k);
 
    };
 
    template<class T>
    QuickSort<T>::QuickSort()
    {
        sortingArray = new vector<T>();
        left = 0;
        right = 0;
    }
 
    template<class T>
    QuickSort<T>::QuickSort(vector<T> *sortArray)
    {
        int startIndex = 0;
        int endIndex = 0;
 
        endIndex = (int)(*sortArray).size() - 1;
 
        QuickSort(sortArray, startIndex, endIndex);
    }
 
    template<class T>
    QuickSort<T>::QuickSort(vector<T> *sortArray, int startIndex, int endIndex)
    {
        if(startIndex >= endIndex)
        {
            return;
        }
 
        // *initialize* the array
        sortingArray = sortArray;
 
        // For instance: 1..n
        left = startIndex;
        right = endIndex;
 
        if(left < right)
        {
            // get pivot
            int pivot = Partition(sortingArray, left, right);
 
            // sort left side
            QuickSort(sortingArray, left, (pivot-1));
 
            // sort right side
            QuickSort(sortingArray, (pivot+1), right);
        }
    }
 
    template<class T>
    int QuickSort<T>::Partition(vector<T> *sortArray, int startIndex, int endIndex)
    {        
        // initially this start - 1 when startIndex is 0.
        int l = startIndex - 1;
         int k = endIndex;
  
         for(int i = startIndex; i <= k - 1; i++)
         {
             // Go until you find a value smaller than the last value.
             if((*sortArray)[i] <= (*sortArray)[k])
             {
                 // increment l
                 l++;
  
                 // swap i and j
                 // NOTE: this is supposed to swap j with itself the first time.
                 Swap(l, i);        
             }
         }    
         
         // when loop is finished, swap 
         Swap(l + 1, k);
  
         return l + 1;
     }
  
     template<class T>
     void QuickSort<T>::Swap(int l, int k)
     {
         // create temp variable
         T tmp;
         
         // store first element in temp
         tmp =(*sortingArray)[l];
  
         // swap second element to first element
         (*sortingArray)[l] = (*sortingArray)[k];
  
         // put temp variable in second element
         (*sortingArray)[k] = tmp;
     }
  
 }
  
 #endif

Related Articles