qsort

From

Ianos Gnatiuc (2:469/303.55)

To

Anatoly Svishev

Date

2002-10-09T19:33:15Z

Area

RU.ALGORITHMS

Hello Anatoly!

04 Oct 02 23:49, you wrote to All:



#define CUTOFF 8
#define SWAP(A, B) tmp = A; A = B; B = tmp;

int lostk[30], histk[30];
int stkptr;

void iqsort(int *base, unsigned num)
{
    int tmp;
    int lo = 0, hi = num-1, mid;
    int loguy, higuy;
    unsigned size;

    stkptr = 0;

recurse:

    size = hi - lo + 1;

    if (size <= CUTOFF)
    {
        int p, max;

        while (hi > lo)
        {
            max = base[lo];
            for (p = lo+1; p <= hi; p++)
            {
                if (base[p] > max) max = base[p];
            }

            SWAP(max, base[hi]); hi--;
        }
    }
    else
    {
        mid = lo + size/2;
        SWAP(base[mid], base[lo]); loguy = lo; higuy = hi+1;

        for (;;)
        {
            do loguy++; while ((loguy <= hi) && (base[loguy] <= base[lo]));
            do higuy--; while ((higuy >  lo) && (base[higuy] >= base[lo]));
            if (higuy < loguy) break;
            SWAP(base[loguy], base[higuy]);
        }

        SWAP(base[lo], base[higuy]);

        if ((higuy - lo - 1) >= (hi - loguy))
        {
            if ((lo+1) < higuy)
            {
                lostk[stkptr] = lo; histk[stkptr] = higuy-1; stkptr++;
            }

            if (loguy < hi) { lo = loguy; goto recurse; }
        }
        else
        {
            if (loguy < hi)
            {
                lostk[stkptr] = loguy; histk[stkptr] = hi; stkptr++;
            }

            if ((lo + 1) < higuy) { hi = higuy-1; goto recurse; }
        }
    }

    --stkptr;
    if (stkptr >= 0)
    {
        lo = lostk[stkptr]; hi = histk[stkptr]; goto recurse;
    }

    return;
}



Ianos

... [WinAmp is not installed]  EMAIL: ssianky[at][hotmail | yahoo].com
--- GoldED+/W32 1.1.4.7
 * Origin: SS Ianky - (373-2) 534966 (2:469/303.55)