GLProgramming.com

home :: about :: development guides :: irc :: forums :: search :: paste :: links :: contribute :: code dump

-> Click here to learn how to get live help <-


New Paste :: Recent Pastes:: Add Line Numbers


quicksort by godecho
///// sort.h
template <class _Type>
void quickSort(_Type *array, unsigned int n)
{
    if(n < 2)
    {
        return;
    }

    int pivotIndex = 0;
    int midIndex = n/2;
    _Type temp;

    // partition the list
    if(array[n-1] < array[0])
    {            
        temp = array[n-1];
        array[n-1] = array[0];
        array[0] = temp;
    }
    if(array[n-1] < array[midIndex])
    {
        temp = array[n-1];
        array[n-1] = array[midIndex];
        array[midIndex] = temp;
    }
    if(array[0] < array[midIndex])
    {
        temp = array[0];
        array[0] = array[midIndex];
        array[midIndex] = temp;
    }
    for(unsigned int i = 1; i < n; i++)
    {
        if(array[i] < array[0])
        {
            temp = array[i];
            array[i] = array[++pivotIndex];
            array[pivotIndex] = temp;
        }
    }
    
    temp = array[pivotIndex];
    array[pivotIndex] = array[0];
    array[0] = temp;

   // recursively sort the sublists
    quickSort(array, pivotIndex);
    quickSort(array+pivotIndex+1, n-pivotIndex-1);
}

/////// simple driver program
#include <cstdio>

#include "sort.h"

int main(void)
{
    int array[] = {4, 8, 1, -1, 111, 75};

    quickSort<int>(array, 6);

    for(int x = 0; x < 6; ++x)
    {
        printf("%i ", array[x]);
    }
    printf("\n\n");

    return 0;
}