» »

Implementacija Binary Radix Sorta

Implementacija Binary Radix Sorta

IcyFox ::

Pozdravljeni, imam težave pri implementaciji binarnega Radix Sorta v jeziku C++. Poleg naloge smo dobili navodila in imam kodo napisano po teh navodilih, ampak sortiranje ne deluje pravilno. Kot vmesni sortirni algoritem sem uporabil Counting sort. Pri nalogi je bilo zahtevano tudi, da se uporabi podatkovni tip unsigned char. Tu je koda:
vector<unsigned char> A;
    vector<unsigned char> C(2);
    vector<unsigned char> B(A.size());
    A.push_back(14);
    A.push_back(5);
    A.push_back(2);
    A.push_back(12);

    for(int i = 0; i < A.size(); i++) {
        B.push_back(0);
    }

    int k = 0;

while(k < 8) {
    C[0] = 0;
    C[1] = 0;

    for (int i = 0; i < 4; i++) {
        C[(A[i] >> k) & 1]++;
    }

    C[1] += C[0];

    for (int j = 0; j < 4; ++j) {
        B[--C[(A[j] >> k) & 1]] = A[j];
    }

    swap(A, B);
    k++;
}

Bi mogoče kdo vedel, v čem je težava da se sortiranje ne izvede pravilno? Hvala!

rozman ::

        // namesto j=3 daj potem A.size()-1
        for (int j = 3; j >= 0; j--) {
            B[--C[(A[j] >> k) & 1]] = A[j];
        }

IcyFox ::

rozman je izjavil:


// namesto j=3 daj potem A.size()-1
for (int j = 3; j >= 0; j--) {
B[--C[(A[j] >> k) & 1]] = A[j];
}

Holy... sploh ne veš kok ur sem porabil pa je bila samo to težava. Ful ti hvala :D

IcyFox ::

Imam pa še eno težavo pri omenjenem algoritmu, in sicer pri večji količini števil (300+) algoritem več ne sortira pravilno. V čem bi lahko bila težava?

Randomness ::

Sklepam, da si kodo od nekje copypastal. Znaš razložiti, kaj dela v kodi pogoj while(k < 8)?

TechGuy ::

Glede na to, da je za tisti del pokuril "kar nekaj ur" ...
Pomoje gre za kodo od asistenta (očitno je ni v celoti dobro prepisal :P)

w/e

Imaš namreč : vector<unsigned char> C(2)

rešitev :

int C[2];
ali
unsigned int C[2];


ko boš nalogo oddal pa je tvoja naslednja domača naloga, da pogooglaš kaj je unsigned char.


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[C++] OpenMP težave

Oddelek: Programiranje
6825 (697) Rokm
»

[Algoritem] Kako do najkrajše poti na med točkami

Oddelek: Programiranje
213230 (2818) Spura
»

Java vector konstruktor = failure?

Oddelek: Programiranje
111032 (897) arjan_t
»

[C++] velikost matrike

Oddelek: Programiranje
191693 (1505) Jean-Paul
»

c++ in linux/windows

Oddelek: Programiranje
121721 (1597) rapvirus

Več podobnih tem