[C++][Qt] Parallel Quick Sort with QtConcurrent (Shared memory generic quick sort)

PS : I developed several quick sort (available on this blog), a sequential version, an openmp tasks version, a openmp not inplace version, an mpi version and a Qt concurent version.

Here I developed a quick sort based on the great qt feature QtConcurrent.
It is mostly similar to the openmp tasks versions.

Advices

Change the fallowing lines in the code to perform different tests

QThreadPool::globalInstance()->setMaxThreadCount(1);
const long Size = 10000000;

The code

#include <QtCore/QCoreApplication>
#include <QTime>
#include <QtConcurrentRun>

#include <iostream>

////////////////////////////////////////////////////////////
// Miscialenous functions
////////////////////////////////////////////////////////////

/** Swap to value */
template <class NumType>
inline void Swap(NumType& value, NumType& other){
    NumType temp = value;
    value = other;
    other = temp;
}

////////////////////////////////////////////////////////////
// Quick sort
////////////////////////////////////////////////////////////

/* use in the sequential qs */
template <class SortType>
long QsPartition(SortType outputArray[], long left, long right){
    const long part = right;
    Swap(outputArray[part],outputArray[left + (right - left ) / 2]);
    const SortType partValue = outputArray[part];
    --right;

    while(true){
        while(outputArray[left] < partValue){
            ++left;
        }
        while(right >= left && partValue <= outputArray[right]){
            --right;
        }
        if(right < left) break;

        Swap(outputArray[left],outputArray[right]);
        ++left;
        --right;
    }

    Swap(outputArray[part],outputArray[left]);

    return left;
}

/* a sequential qs */
template <class SortType>
void QsSequential(SortType array[], const long left, const long right){
    if(left < right){
        const long part = QsPartition(array, left, right);
        QsSequential(array,part + 1,right);
        QsSequential(array,left,part - 1);
    }
}

/** A task dispatcher */
template <class SortType>
void QuickSortTask(SortType array[], const long left, const long right, const int deep){
    if(left < right){
        if( deep ){
            const long part = QsPartition(array, left, right);

            QtConcurrent::run(QuickSortTask<SortType>, array, part + 1, right, deep - 1);
            QtConcurrent::run(QuickSortTask<SortType>, array, left, part - 1, deep - 1);
        }
        else {
            const long part = QsPartition(array, left, right);
            QsSequential(array,part + 1,right);
            QsSequential(array,left,part - 1);
        }
    }
}

////////////////////////////////////////////////////////////
// Main
////////////////////////////////////////////////////////////

template <class SortedType>
bool isSorted(SortedType array[], const long size){
    for(int idx = 1; idx < size ; ++idx){
        if(array[idx-1] > array[idx]){
            return false;
        }
    }
    return true;
}

template <class SortedType>
void print(SortedType array[], const int size){
    for(int idx = 0 ;idx < size; ++idx){
        std::cout << array[idx] << "\t";
    }
    std::cout << "\n";
}

int main(int argc, char** argv){
    QCoreApplication app(argc, argv);
    // Change to test efficiency
    // QThreadPool::globalInstance()->setMaxThreadCount(1);

    const long Size = 10000000;//600000000;
    long* const array = new long[Size];

    // Create array
    srand(0);
    for(long idx = 0 ; idx < Size ; ++idx){
        array[idx] = int(Size*(float(rand())/RAND_MAX));
    }

    printf("Sorting %ld elements\n", Size);
    // Start sorting
    QTime timer;
    timer.start();
    QtConcurrent::run(QuickSortTask<long>, array, 0, Size - 1, 6);
    QThreadPool::globalInstance()->waitForDone();
    printf("Elapsed time %f s\n", timer.elapsed()/1000.0);

    // Test result
    if(isSorted(array,Size)){
        printf("Is sorted\n");
    }
    else{
        printf("Error array is not sorted!\n");
        if( Size <= 20) print(array,Size);
        return -1;
    }

    // remove array and quit
    delete [] array;
    return 0;
}

Licence : lgpl.