Radix Sort - prośba o wytłumaczenie.

0
 
void radixsort(unsigned long * const z1, unsigned int const N)
{
    unsigned long L[2], i, m = 1;
    unsigned long * const z2 = new unsigned long[N];
    
    for (int licz = 0; licz < sizeof(unsigned long) * 4; ++licz)
    {
        L[0] = L[1] = 0;
        for(i = 0; i < N; ++i) ++L[(z1[i] & m) > 0];
        L[1] += L[0];
        for(i = N; i > 0; --i) z2[(L[(z1[i - 1] & m) > 0]--) - 1] = z1[i - 1];

        
        m <<= 1;
        
        L[0] = L[1] = 0;
        for(i = 0; i < N; ++i) ++L[(z2[i] & m) > 0];
        L[1] += L[0];
        for(i = N; i > 0; --i) z1[(L[(z2[i - 1] & m) > 0]--) - 1] = z2[i - 1];
        
        m <<= 1;
    }

    
    delete [] z2;
}

Czy pomógłby mi ktoś i wytłumaczył co się w tym kodzie po kolei dzieje, bo ja siedzę nad tym i nic nie moge wymyślić. Z góry dzięki za pomoc.

0

Przyjmując, że ten kod prawidłowo sortuje metodą radix, wpisz po prostu radix sort w Google i poczytaj jak ta metoda działa, bo tłumaczenie kodu nie ma sensu.

0

A kod jest napisany:

  1. nie poprawnie
  2. bardzo nie optymalnie
0

Z tego co mi wiadomo ww. kod wykorzystuje counting sorta. Wiem jak ogólnie działa metoda radix sort, ale nie rozumie tego kodu. Dlatego proszę o wytłumaczenie go np. co dzieje się w pętli for w 2. i 4. linijce.

0
  1. Zlicza się ilości elementów dla kubełków 0 i 1
  2. Elementy odpowiednio kopiowane do z2
0

Powiedziałem przykładowo. Prosiłbym o wyłożenie ww. kodu krok po kroku

0

Przecież pozostałe wiersze są oczywiste.

0

Dokładniej chodzi mi o bardziej szczegółowe wytłumacznie tej 2. i 4. linijki w wewnętrznym for

0

to rozpisz sobie to przez zmienne dodatkowe:

++L[(z1[i] & m) > 0];

=> unsigned long tmp1=z1[i] & m;
bool tmp2=tmp1>0;
++L[tmp2];

i normalnie po ludzku powiedz której operacji nie rozumiesz.
0

Co znajduje się w tablicy z1 i czym jest L[tm2] (co to za wartość)

0
korczyn napisał(a):

Co znajduje się w tablicy z1 i czym jest L[tm2] (co to za wartość)

Skąd my mamy to wiedzieć? Spójrz na nagłówek funkcji, a zrozumiesz, że to pytanie jest bez sensu.
Edit: chyba, że w innym rozumieniu, no ale wtedy i tak z definicji funkcji widać, że jest to tablica z liczbami do posortowania...

0

czym jest z1- @Patryk27 ci odpowiedział, patrz na nagłówek funkcji.
L[tmp] - jeżeli nie wiesz czym jest Tablica[i] to zacznij może od czytania podstaw C, bo żadne tłumaczenie ci nie pomoże.

0

Ok wybaczcie. z1 to tabalica wejściowa, ale co się z nią wtedy dzieje.

@up
wiem czym jest tablica[i]. Chodzi mi o konkretnie w tym przypadku.

0

Jeżeli rozumiesz czym jest tablica[i] to czemu pytasz co to L[tmp2]?
Czyżby nie widzisz deklaracji tej tablicy L?
W tym fragmencie z z1 nic się nie dzieje.

1 użytkowników online, w tym zalogowanych: 0, gości: 1