Thread: best way to sort large amount of data.

Sorting algorithm - Wikipedia, the free encyclopedia

sort - C++ Reference
Most of the STL comes with a "complexity guarantee".
Which in the case of std::sort means N*log2(N).

There are several algorithms which meet this requirement.

Also, given that you want to use some complex sorting criteria, you can also do

Code:

std::sort(myvector.begin(), myvector.end(), [](T left, T right) -> bool { /* your sorting critera here */ });

Where T is the type of the elements in your vector. This requires C++11 support in your compiler.
If using a C++14 compliant compiler (e.g. clang), you can simplify it to

Code:

std::sort(myvector.begin(), myvector.end(), [](auto left, auto right) { /* your sorting critera here */ });

Originally Posted by manasij7479

Not specifying the return type seems to work fine with C++11.
Why? (GCC extension..perhaps??)

It does, but only if you have a simple return statement in the lambda body. That's why I added the return type.
If you have a more complex body, you must specify return type. This restriction was lifted from C++14, as long as all return statements have the same return type.

Originally Posted by jocdrew21

@Elysia, I am assuming that is lambda right? I am very interested in how you just coded that. It looks very nice!!!!

Yes, it's called a lambda.

Originally Posted by Elysia

If using a C++14 compliant compiler (e.g. clang)

Technically, there is no such thing as a C++14 compliant compiler at this time

Originally Posted by laserlight

Technically, there is no such thing as a C++14 compliant compiler at this time

Well, you have a point, I guess. Draft C++14 compliant may be a better term, then

Originally Posted by Elysia

Well, you have a point, I guess. Draft C++14 compliant may be a better term, then

That's an oxymoron - compliance is relative to an accepted standard or set of criteria, the word draft means not yet accepted and subject to change.

I'd suggest a "compiler that provides features from the C++14 draft" would be an appropriate description.

Yes, there was a number of compiler vendors who described their products as ANSI compliant before the first C++ standard was ratified by ANSI (and later ISO). The truth is the first casualty when marketeers get involved in claims of compliance.

Originally Posted by jocdrew21

What do you guys think is the best way to sort lets say 10 million ints in random order?

The fastest way would be Radix sort. Example code below. pData is a pointer to the array, pTemp is a pointer to a temp array of the same size. UI64 is a 64 bit unsigned integer, PUI64 is a pointer to a 64 bit unsigned integer. In this case RadixSort() always takes 8 passes so the sorted data always ends up in pData and RadixSort() will always return a pointer to pData. For 32 bit ints, the index matrix size would be [4][256], and only 4 passes made.

Code:

typedef unsigned long long UI64;
typedef unsigned long long *PUI64;

PUI64 RadixSort(PUI64 pData, PUI64 pTemp, size_t count)
{
size_t mIndex[8][256] = {0};            /* index matrix */
PUI64 pDst, pSrc, pTmp;
size_t i,j,m,n;
UI64 u;

    for(i = 0; i < count; i++){         /* generate histograms */
        u = pData[i];
        for(j = 0; j < 8; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 8; j++){             /* convert to indices */
        n = 0;
        for(i = 0; i < 256; i++){
            m = mIndex[j][i];
            mIndex[j][i] = n;
            n += m;
        }       
    }

    pDst = pTemp;                       /* radix sort */
    pSrc = pData;
    for(j = 0; j < 8; j++){
        for(i = 0; i < count; i++){
            u = pSrc[i];
            m = (size_t)(u >> (j<<3)) & 0xff;
            pDst[mIndex[j][m]++] = u;
        }
        pTmp = pSrc;
        pSrc = pDst;
        pDst = pTmp;
    }

    return(pSrc);
}

Originally Posted by jocdrew21

What do you guys think is the best way to sort lets say 10 million ints in random order?

std::sort is fine. No need to invest anything unless you can prove the performance isn't sufficient.
Also works on any type as long as you can compare them using operator < (as opposed to, say, radix sort).