C/C++ FAQ

Radix sort

fr3

Kod do sortowania unsigned intów w czasie liniowym. ( O(n) )
O wiele lepszy od jakiegokolwiek algorytmu dzialajacego w czasie liniowo-logarytmicznym ( O(n lg n)), jak np. quicksort.

Algorytm jest stabilny, nie działa w miejscu (uzywa bufora tymczasowego o rozmiarze n).

#include <stdio.h>
 
//Radix Sort by Fr3m3n, 2007
#define uint unsigned int
 
typedef union _sort_uint{
    uint liczba;
    struct{
        #ifdef LITTLE_ENDIAN
            unsigned short int Low;
            unsigned short int High;
        #else
            unsigned short int High;
            unsigned short int Low;
        #endif
    };
}sort_uint;
 
int main(void){
    uint n;
    scanf("%u",&n);
    sort_uint *liczby0=(uint*)malloc(n*sizeof(uint)*2);
    //liczby1 to tablica pomocnicza
    sort_uint *liczby1=liczby0+n;
    for(uint i=0;i<n;i++)
        scanf("%u",&liczby0[i].liczba);
    /*
    Najpierw sortuje wedlug lsw (least significant word), uzywajac lsw jako indexu w tablicy.
    Pozniej w ten sam sposob z msw. (most significant word)
    Zlozonosc obliczeniowa: O(n)
    Zlozonosc pamieciowa: O(n)
    Sortuje wg unsigned int, ale latwo zmienic dla signed
    */
    uint gdzie[0xFFFF+1];
    bzero(gdzie,sizeof(gdzie));
    for(register uint i=0;i<n;i++)
        gdzie[liczby0[i].Low]++;
    register uint t=0,t1;
    //zapisz w gdzie adresy dla kolejnych liczb
    for(uint i=0;i<(0xFFFF+1);i++){
        if(gdzie[i]){
            t1=gdzie[i];
            gdzie[i]=t;
            t+=t1;
        }
    }
    //posortuj wg lsw
    for(register uint i=0;i<n;i++){
        register uint __asdf=(liczby0[i].Low);
        liczby1[gdzie[__asdf]].liczba=liczby0[i].liczba;
        gdzie[__asdf]++;
    }
 
    //posortuj wg msw
    bzero(gdzie,sizeof(gdzie));
    for(register uint i=0;i<n;i++)
        gdzie[liczby1[i].High]++;
    t=0;
    //zapisz w gdzie adresy dla kolejnych liczb
    for(uint i=0;i<(0xFFFF+1);i++){
        if(gdzie[i]){
            t1=gdzie[i];
            gdzie[i]=t;
            t+=t1;
        }
    }
    //posortuj wg msw
        for(register uint i=0;i<n;i++){
            register uint __asdf=(liczby1[i].High);
            liczby0[gdzie[__asdf]].liczba=liczby1[i].liczba;
            gdzie[__asdf]++;
    }
 
    //wypisz
    puts("Posortowane:");
    for(uint i=0;i<n;++i)
        printf("%u\n",liczby0[i].liczba);
    free(liczby0);
}
FAQ

0 komentarzy