Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sorting revisited again

  1. Dec 14, 2013 #1

    rcgldr

    User Avatar
    Homework Helper

    Added radix sort to sort examples in:

    http://rcgldr.net/misc/sortv.zip

    Results on my system:

    Code (Text):

    Time to sort 4,194,304 64 bit elements of psuedo random data:

    radix sort                 rsortv.cpp    203 ms
    hybrid (radix+merge) sort  hsortv.cpp    265 ms
    merge sort                 msortv.cpp    297 ms
    microsoft sort             sortv.cpp     344 ms
    microsoft stable_sort      sortv.cpp     375 ms

    64 bit mode, Windows XP64, Visual Studio 2005 compiler.
    Intel i7 2600K 3.4ghz, DP67BG motherboard, 4GB ram
     
    Previous threads:

    https://www.physicsforums.com/showthread.php?t=218369

    https://www.physicsforums.com/showthread.php?t=181589

    Code for radix sort function example - it makes one pre-pass over the data array, generating an array of histograms (256 entries for each histogram), then coverts the histograms into the starting indices for each "bucket". Each pass places data into "buckets" based on the 8 bit value of the data, and the passes go from least signficant byte to most significant byte. In this example, 1 pre pass and 8 sort passes are used to sort an array of 64 bit unsigned integers. Only one temporary array (the same size as the original array) is required for the radix sort, using variable size "buckets".

    Code (Text):

    typedef unsigned __int64    UI64;
    typedef unsigned __int64 *  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);
    }
     
     
    Last edited: Dec 15, 2013
  2. jcsd
  3. Dec 15, 2013 #2
    You might want to try comparing how the algorithms perform on partially sorted data. It's just a thought.
     
  4. Dec 15, 2013 #3

    rcgldr

    User Avatar
    Homework Helper

    This was previously done with one of the pointer based text file sorts, msortp.cpp, that optionally takes advantage of ascending or descending sequences (change "#define VARSZGRP 0" to "#define VARSZGRP 1" in msortp.cpp). If the data is already sorted, it determines this with one read pass of the data and completes.

    http://rcgldr.net/misc/sortp.zip

    This wasn't done with the vector / array test sort programs, since the goal at that time was to benchmark the sorts with pseudo random data.

    The previous thread didn't have a proper radix sort, so I added it to the zip file and created this thread.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sorting revisited again
  1. Sorting revisited. (Replies: 17)

  2. Selection sort? (Replies: 2)

  3. Sorting algorithm? (Replies: 2)

  4. Perfect sort (Replies: 2)

  5. Merge sort (Replies: 1)

Loading...