Programowanie w języku C/C++ » FAQ

Radix sort

  • 2007-03-19 18:20
  • 0 komentarzy
  • 867 odsłon
  • Oceń ten tekst jako pierwszy
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);
}