|| || || || || || || ||

---

QuickSort.h

Go to the documentation of this file.

#ifndef Impala_Util_QuickSort_h
#define Impala_Util_QuickSort_h


/*****************************
 * quicksort algorithm copied from http://www.uow.edu.au/~nabg/ABC/quicks.html
 * code is edited to conform to coding standards
 *****************************/

namespace Impala
{
namespace Util
{
    const int cQuicksortTreshold = 15; 

//    normal quicksort and selection sort        //

template<class Type>
void SelectionSort(Type data[], int left, int right)
{
        for(int i=left ; i<right ; i++)
    {
                int min = i;
                for(int j=i+1 ; j<=right ; j++)
                        if(data[j] < data[min])
                min = j;
                Type temp = data[min];
                data[min] = data[i];
                data[i] = temp;
        }
}

template<class Type>
int Partition(Type* data, int left, int right)
{
        Type val = data[left];
        int lm = left-1;
        int rm = right+1;
        for(;;)
    {
                do
                        rm--;
                while (data[rm] > val);
        
                do 
                        lm++;
                while(data[lm] < val);

                if(lm < rm)
        {
                        Type tempr = data[rm];
                        data[rm] = data[lm];
                        data[lm] = tempr;
                }
                else 
                        return rm;
        }
}

template<class Type>
void QuickSort(Type* data, int left, int right)
{
        if(left < (right-cQuicksortTreshold))
    {
                int split_pt = Partition(data,left, right);
                QuickSort(data, left, split_pt);
                QuickSort(data, split_pt+1, right);
        }
        else 
        SelectionSort(data, left, right);
}


//    normal quicksort and selection sort        //
//            in descending order                //

template<class Type>
void SelectionSortDesc(Type data[], int left, int right)
{
        for(int i=left ; i<right ; i++)
    {
                int max = i;
                for(int j=i+1 ; j<=right ; j++)
                        if(data[j] > data[max])
                max = j;
                Type temp = data[max];
                data[max] = data[i];
                data[i] = temp;
        }
}

template<class Type>
int PartitionDesc(Type* data, int left, int right)
{
        Type val = data[left];
        int lm = left-1;
        int rm = right+1;
        for(;;)
    {
                do
                        rm--;
                while (data[rm] < val);
        
                do 
                        lm++;
                while(data[lm] > val);

                if(lm < rm)
        {
                        Type tempr = data[rm];
                        data[rm] = data[lm];
                        data[lm] = tempr;
                }
                else 
                        return rm;
        }
}

template<class Type>
void QuickSortDesc(Type* data, int left, int right)
{
        if(left < (right-cQuicksortTreshold))
    {
                int split_pt = PartitionDesc(data,left, right);
                QuickSortDesc(data, left, split_pt);
                QuickSortDesc(data, split_pt+1, right);
        }
        else 
        SelectionSortDesc(data, left, right);
}

// quicksort and selection sort with 'companion' //
//      used in sorting tables and stuff         //

template<class Type, class CoType>
void SelectionSortCo(Type* data, CoType* coData, int left, int right)
{
        for(int i=left ; i<right ; i++)
    {
                int min = i;
                for(int j=i+1 ; j<=right ; j++)
                        if(data[j] < data[min])
                min = j;
                Type temp = data[min];
                data[min] = data[i];
                data[i] = temp;
                CoType coTemp = coData[min];
                coData[min] = coData[i];
                coData[i] = coTemp;
        }
}

template<class Type, class CoType>
int PartitionCo(Type* data, CoType* coData, int left, int right)
{
        Type val = data[left];
        int lm = left-1;
        int rm = right+1;
        for(;;)
    {
                do
                        rm--;
                while (data[rm] > val);
        
                do 
                        lm++;
                while(data[lm] < val);

                if(lm < rm)
        {
                        Type temp = data[rm];
                        data[rm] = data[lm];
                        data[lm] = temp;
                        CoType coTemp = coData[rm];
                        coData[rm] = coData[lm];
                        coData[lm] = coTemp;
                }
                else 
                        return rm;
        }
}

template<class Type, class CoType>
void QuickSortCo(Type* data, CoType* coData, int left, int right)
{
        if(left < (right-cQuicksortTreshold))
    {
                int split_pt = PartitionCo(data, coData, left, right);
                QuickSortCo(data, coData, left, split_pt);
                QuickSortCo(data, coData, split_pt+1, right);
        }
        else 
        SelectionSortCo(data, coData, left, right);
}

// quicksort and selection sort with 'companion' //
//           in descending order                 //
//      used in sorting tables and stuff         //

template<class Type, class CoType>
void SelectionSortDescCo(Type* data, CoType* coData, int left, int right)
{
        for(int i=left ; i<right ; i++)
    {
                int max = i;
                for(int j=i+1 ; j<=right ; j++)
                        if(data[j] > data[max])
                max = j;
                Type temp = data[max];
                data[max] = data[i];
                data[i] = temp;
                CoType coTemp = coData[max];
                coData[max] = coData[i];
                coData[i] = coTemp;
        }
}

template<class Type, class CoType>
int PartitionDescCo(Type* data, CoType* coData, int left, int right)
{
        Type val = data[left];
        int lm = left-1;
        int rm = right+1;
        for(;;)
    {
                do
                        rm--;
                while (data[rm] < val);
        
                do 
                        lm++;
                while(data[lm] > val);

                if(lm < rm)
        {
                        Type temp = data[rm];
                        data[rm] = data[lm];
                        data[lm] = temp;
                        CoType coTemp = coData[rm];
                        coData[rm] = coData[lm];
                        coData[lm] = coTemp;
                }
                else 
                        return rm;
        }
}

template<class Type, class CoType>
void QuickSortDescCo(Type* data, CoType* coData, int left, int right)
{
        if(left < (right-cQuicksortTreshold))
    {
                int split_pt = PartitionDescCo(data, coData, left, right);
                QuickSortDescCo(data, coData, left, split_pt);
                QuickSortDescCo(data, coData, split_pt+1, right);
        }
        else 
        SelectionSortDescCo(data, coData, left, right);
}

} // namespace Util
} // namespace Impala

#endif // Impala_Util_QuickSort_h

---