quicksort.cpp

#include <cstdio>
#include <algorithm>
using namespace std;

static const int QSORT_BUFLEN = 3;
static int qsort_buf[QSORT_BUFLEN];
static int qsort_bufn; // quantidade de itens no buffer

static void partition(
        int* file,
        int lo, int hi,    // limites do subarquivo a ser ordenado [lo, hi]
        int* pi, int* pj)  // limites do particionamento que será feito
{
    int rlow, rupp; // ponteiros de leitura
    int wlow, wupp; // ponteiros de escrita
    rlow = wlow = lo;
    rupp = wupp = hi;
    int linf = -0x3f3f3f3f, lsup = 0x3f3f3f3f;

    *pi = lo - 1;
    *pj = hi + 1;
    qsort_bufn = 0;
    while(rupp >= rlow) {
        int item;

        if (rlow - wlow < wupp - rupp)
            item = file[rlow++];
        else
            item = file[rupp--];

        if (qsort_bufn < QSORT_BUFLEN) {
            qsort_buf[qsort_bufn++] = item;
            sort(qsort_buf, qsort_buf + qsort_bufn);
        } else {
            if (item > qsort_buf[qsort_bufn - 1]) {
                if (item > lsup)
                    *pj = wupp;
                else
                    lsup = item;
                file[wupp--] = item;
            } else if (item < qsort_buf[0]) {
                if (item < linf)
                    *pi = wlow;
                else
                    linf = item;
                file[wlow++] = item;
            } else if (wlow - lo < hi - wupp) {
                file[wlow++] = qsort_buf[0];
                linf = qsort_buf[0];
                qsort_buf[0] = item;
                sort(qsort_buf, qsort_buf + qsort_bufn);
            } else {
                file[wupp--] = qsort_buf[qsort_bufn - 1];
                qsort_buf[qsort_bufn - 1] = item;
                sort(qsort_buf, qsort_buf + qsort_bufn);
            }
        }
    }

    // grava o conteúdo do buffer no arquivo
    while(qsort_bufn > 0)
        file[wupp--] = qsort_buf[--qsort_bufn];
}

void ext_qsort(int* file, int lo, int hi)
{
    if (hi - lo < 1) return;

    int i, j;
    partition(file, lo, hi, &i, &j);

    if (i - lo < j - hi) { // ordena o menor subarquivo
        ext_qsort(file, lo, i);
        ext_qsort(file, j, hi);
    } else {
        ext_qsort(file, j, hi);
        ext_qsort(file, lo, i);
    }
}

int main()
{
    const int L = 7;
    int A[] = {5, 3, 10, 6, 1, 7, 4};
    for(int i = 0; i < L; i++)
        printf("%d ", A[i]);
    putchar('\n');
    ext_qsort(A, 0, L - 1);
    for(int i = 0; i < L; i++)
        printf("%d ", A[i]);
    putchar('\n');

    return 0;
}

/* Testando
$ g++ quicksort.cpp && ./a.out 
5 3 10 6 1 7 4
1 3 4 5 6 7 10
*/