QuickSort: Templated using function pointers

Freaky_Chris 0 224 Views

This is a sample code snippet of a quicksort that uses templating and function pointers to allow the user to sort an array of anything from numbers to strings to structures.

The idea is, that the coder writes a small function thats return type is bool, It should return true if the first parameter is "less than" the second, or if you which to sort it in descending order then "greater than" the second parameter.

Below is an example of the quicksort being used on an array of ints, strings & a structure.

Hope this is helpful to people and provides a small insight into templating and function pointers with callback procedures.

(Note: perhaps not the best code ever, but nice)

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>

struct example{
    int id;
    std::string name;
};

template <class T>
void quickSort(T uA[], int l, int r, bool (*less)(T, T));

template <class T>
int partition(T uA[], int l, int r, bool (*less)(T, T));

bool intCheck(int a, int b){
    return (a < b);
}

bool stringCheck(std::string a, std::string b){
    for(int i = 0; i < a.length(); i++)
        a[i] = tolower(a[i]);
    for(int i = 0; i < b.length(); i++)
        b[i] = tolower(b[i]);
    if(strcmp(a.c_str(), b.c_str()) >= 0)
        return false;
    else return true;
}

bool exampleCheck(example a, example b){
    if(strcmp(a.name.c_str(), b.name.c_str()) >= 0) return false;
    else return true;
}

int main(int argc, char *argv[]){

    int iArray[] = { 2, 1, 56, 213, 2, 32, 32216, 14 };
    std::string sArray[] = { "Hello", "how are you?", "elephant", "aaah!", "zzzzz", "queen" };
    example structArray[] = { {1, "Joe"},
                              {4, "Billy"},
                              {2, "Zander"},
                              {3, "Tom"} };

    quickSort(iArray, 0, 7, intCheck);
    quickSort(sArray, 0, 5, stringCheck);
    quickSort(structArray, 0, 3, exampleCheck);

    std::cout << "Integers:" << std::endl;
    for(int i = 0; i < 8;i++)
        std::cout << '\t' << iArray[i] << std::endl;

    std::cout << std::endl << "String:" << std::endl;
    for(int i = 0; i < 6;i++)
        std::cout << '\t' << sArray[i] << std::endl;

    std::cout << std::endl << "Structure (By name):" << std::endl;
    for(int i = 0; i < 4;i++)
        std::cout << "\t{ " << structArray[i].id << ", " << structArray[i].name << " }" << std::endl;

    std::cin.get();
    return 0;
}

template <class T>
int partition(T uA[], int l, int r, bool (*less)(T, T)){
     int pos = l;
     std::swap(uA[r], uA[pos]);
     if (l < r){
        for(int i = l; i < r; i++) if((*less)(uA[i], uA[r])) std::swap(uA[i], uA[pos++]);
        std::swap(uA[r], uA[pos]);
        }
     return pos;
}

template <class T>
void quickSort(T uA[], int l, int r, bool (*less)(T, T)){
     if(r > l){
        int pos = partition( uA, l, r, less );
        quickSort( uA, l, pos-1, less);
        quickSort( uA, pos+1, r, less);
     }
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Edit Preview