CODEWITHSUNDEEP
calgorithmsortingbubble-sort
HelloWor1d
HelloWor1d

Reputation: 63

How is this bubble sort so fast?

I came across a bubble sort algorithm that is ridiculously fast... Like sorts 100,000 full length ints in reversed sorted order in 0.03 seconds fast. I know that bubble sort is regarded as one of the most inefficient sorting algorithms, so what makes this one so much better?

I see that it stops sorting if no items are interchanged on the first pass (meaning it is already sorted), but that shouldn't affect the reversed order case.

p.s. Can anyone think of a way to sort this many ints faster? Maybe Radix sort?

void sort(int list[], int n)
{
    int i; 
    int j; 
    int gap;
    int swapped = 1;
    int temp;
    gap = n;

    while (gap > 1 || swapped == 1)
    {
        gap = gap * 10 / 13;
        if (gap == 9 || gap == 10)
        {
            gap = 11;
        }
        if (gap < 1)
        {
            gap = 1;
        }
        swapped = 0;
        for (i = 0, j = gap; j < n; i++, j++)
        {
            if (list[i] > list[j])
            {
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
                swapped = 1;
            }
        }
    }
}

Upvotes: 0

Views: 298

Answers (2)

rcgldr
rcgldr

Reputation: 28828

As commented it's a comb sort .

For in place sorting, quick sort or heap sort would be faster. If using a second temp array, then merge sort or counting / radix sort are faster. Counting / radix sort should be the fastest of these.

Example code for counting / radix sort. It takes about .001 seconds on my system (Intel 2600K, 3.4ghz). This example code could be optimized a bit (like using a pointer for mIndex[j]), but I'm not sure if the compiler is already doing most of the optimizations you might make with minor code changes. It's possible that the processor overhead is so small that memory bandwidth is the limiting factor.

typedef unsigned int UI32;

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

    for(i = 0; i < count; i++){         // generate histograms
        u = pData[i];
        for(j = 0; j < 4; j++){
            mIndex[j][(size_t)(u & 0xff)]++;
            u >>= 8;
        }       
    }
    for(j = 0; j < 4; 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 < 4; 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);
}

Upvotes: 3

user295691
user295691

Reputation: 7248

Though it bears resemblance to a bubble sort, I think this is a shell sort, which is a much faster variant on the bubble sort.

Upvotes: 1

Related Questions