Wprowadzenie

Sortowanie pozycyjne (ang. radix sort) jest jednym z efektywniejszych algorytmów sortowania. Jego złożoność obliczeniowa wynosi O(n), jego podstawową wadą są dość duże wymagania pamięciowe.

Sortowanie binarne

Poniżej przedstawiona została funkcja implementująca sortowanie pozycyjne o podstawie 2 (binarne).

// table - tablica
// count - ilość elementów w tablicy
// unsigned int ma 32 bity
void radix_sort(unsigned int* table, int count)
{
 unsigned int* temp0 = (unsigned int)malloc(count*sizeof(unsigned int));
 unsigned int* temp1 = (unsigned int)malloc(count*sizeof(unsigned int));

 unsigned int bit = 1;

 for (int i=1; i<32; i++)
    {
     unsigned int* t0 = temp0;
     unsigned int* t1 = temp1;

     for (int j=0; j<count; j++, table++)
        if (table[j] && bit) // rozdzielanie elementów
           *t1++ = table[j];
        else
           *t0++ = table[j];

     // tutaj następuje połączenie tablic temp0 i temp1 w jedną:
     int num0 = (int)t0-(int)temp0;
     int num1 = (int)t1-(int)temp1;

     memcpy(table,      temp0, num0*sizeof(int));
     memcpy(table+num0, temp1, num1*sizeof(int));

     bit <<= 1;
    }

 free(temp0);
 free(temp1);
}

Pamiętając, że sortowanych może być naprawdę dużo danych, należałoby jakoś wyeliminować wspomniane łączenie tablic. Poniższa funkcja pokazuje ideę proponowanej optymalizacji.

void sort(unsigned int* table, int count)
{
 typedef unsigned int* ptr;

 ptr input0 = table;
 ptr input1 = (unsigned int)malloc(count*sizeof(unsignd int));

 int count0 = count;
 int count1 = 0;

 ptr output1 = (unsigned int)malloc(count*sizeof(unsignd int));
 ptr output1 = (unsigned int)malloc(count*sizeof(unsignd int));

 unsigned int bit = 1;
 for (int i=0; i<32; i++)
    {
     ptr temp0 = output0;
     ptr temp1 = output1;

     for (int j=0; j<count0; j++) // sortujemy pierwszą
         if (input0[j] && bit)
            *temp1++ = input0[j];
         else
            *temp0++ = input0[j];

     for (int j=0; j<count1; j++) // i drugą cześć tablicy
         if (input1[j] && bit)
            *temp1++ = input1[j];
         else
            *temp0++ = input1[j];

     bit <<= 1;

     // teraz już nie kopiujemy danych, tylko zamieniamy wskaźniki
     // jednocześnie należy obliczyć nowe rozmiary tablic wejściowych

     count0 = (int)temp0 - (int)output0;
     count1 = (int)temp1 - (int)output1;

     ptr t;

     t       = input0;
     input0  = output0;
     output0 = t;

     t       = input1;
     input1  = output1;
     output1 = t;
    }

 // Dopiero na samym końcu trzeba połączyć tablice wyjściowe.
 // Jako że input0==table, tak więc pierwsza część tablicy
 // jest już "na miejscu".
 memcpy(table+count0, input1, count1);

 free(input1);
 free(output0);
 free(output1);
}

Bez wątpienia wadą powyższego rozwiązania jest zwiększenie wymagań pamięciowych — o 33% większe niż w pierwszej wersji. O wiele istotniejszą zaletą jest jednak znaczne zmniejszenie ilości przenoszonych danych.

Koszt stały, wynikający z metody, to przesłanie count elementów w jednej iteracji. W przypadku pierwszej metody w każdej iteracji jest przesyłane dodatkowe count elementów.

Sumaryczna ilość danych przenoszona w trakcie sortowania to:

• pierwsza metoda: 64*count,
• druga metoda: od 32*count do 33*count.

Uwagi

1. W przypadku gdy sortowane są duże struktury względem jakiegoś rekordu efektywniej jest sortować wskaźniki do struktur.
2. Sortowanie binarne umożliwia również sortowanie liczb zmiennoprzecinkowych: najpierw brany jest pod uwagę zanegowany bit znaku, następnie bity wykładnika, a na końcu bity mantysy.