Resultaten Bucketsort sorteren op hoevaak iets voorkomt

[Verwijderd]

Beste mede programmeurs,
ben op dit moment aan het programmeren in PHP en probeer al dagen resultaten van een bucketsort te sorteren op hoe vaak een getal voor komt. Met het meest voorkomende getal achteraan.

Weet iemand hoe ik dit voor elkaar krijg? Zowel het getal, als hoe vaak het getal voorkomt moet ik kunnen opvragen.

Hoop dat jullie me hierbij kunnen helpen.

[P.O. Box]

misschien is dit wat:
http://nl3.php.net/manual/en/function.usort.php

i.c.m.
http://nl3.php.net/manual/en/function.array-count-values.php

[ Voor 33% gewijzigd door P.O. Box op 14-03-2007 09:57 ]

[Creepy]

En wat heb je zelf al geprobeerd en wat lukt daar niet niet mee? Als je je getallen hebt en per uniek getal telt hoevaak het voorkomt lijkt het me dat je zonder problemen moet kunnen sorteren?

[wackmaniac]

Misschien ook even vertellen hoe de sortering inelkaar steekt mbt datatypes.

Als je gebruik maakt van een array, dan zou erover kunnen denken om een tweede dimensie aan de array toe te voegen.

[Daos]

Het maakt niet uit welk sorteeralgoritme je gebruikt. Je kan het met elke doen.

Een getallenvoorbeeldje is weliswaar geen bewijs, maar helpt in zo'n geval vaak het inzicht te vergroten:
Getallen:
2 5 3 2 1 2 3 2 5 2 1 5 3 4 3
1) sorteren op getal:
1 1 2 2 2 2 2 3 3 3 3 4 5 5 5
2) aantallen bepalen:
1,2 2,5 3,4 4,1 5,3
3) sorteren op aantal:
4,1 1,2 5,3 3,4 2,5
Het resultaat:
4 1 5 3 2

wackmaniac schreef op woensdag 14 maart 2007 @ 10:02:
Als je gebruik maakt van een array, dan zou erover kunnen denken om een tweede dimensie aan de array toe te voegen.

Dat kan voor stap 2 en 3. Je kan ook een nieuw type maken met getal en aantal als velden.
In PHP is dit allemaal volgens mij niet nodig. Een index van een array kan in php van alles zijn. Zelfs strings.

Edwardvb schreef op woensdag 14 maart 2007 @ 09:55:
misschien is dit wat:
http://nl3.php.net/manual/en/function.usort.php

i.c.m.
http://nl3.php.net/manual/en/function.array-count-values.php

Stap 1 en 2 zijn in 1 keer te doen met die array_count_values. Stap 3 kan al met asort.

[wackmaniac]

Stap 1 maakt geen gebruik van BucketSort. Ik weet niet hoe noodzakelijk dit is voor de ts.

Ik snap eigenlijk niet helemaal waarom je bucketsort hiervoor uberhaupt zou willen gebruiken. Zoals Daos al zegt kan je in PHP heerlijk aan het klussen met indexen van een array. Bucketsort heeft een lineaire tijdscomplexiteit, maar als je gewoon elk element doorloopt en de waarde in een array op de index van die waarde met 1 ophoogt ben jer ook na een standaard sorteerfunctie van php.

Snapt iemand het nog

[Daos]

wackmaniac schreef op woensdag 14 maart 2007 @ 11:27:
Stap 1 maakt geen gebruik van BucketSort. Ik weet niet hoe noodzakelijk dit is voor de ts.

Stap1 kan met elk sorteer algoritme. Dus ook met BucketSort.

Bucketsort heeft een lineaire tijdscomplexiteit, maar als je gewoon elk element doorloopt en de waarde in een array op de index van die waarde met 1 ophoogt ben jer ook na een standaard sorteerfunctie van php.

Wat jij voorstelt is ongeveer hetzelfde als BucketSort. Ipv van de elementen zelf in een bucket te stoppen hou je daar het aantal bij.

Of het altijd goed werkt hangt af van de getallen en het aantal buckets. Bij BucketSort kan het namelijk voorkomen dat niet identieke elementen in dezelfde bucket komen.

Snapt iemand het nog

Het valt reuze mee. In c ziet het er bijvoorbeeld zo uit (met quicksort uit stdlib. Ik had niet veel tijd, code is dus beetje slecht):

C:

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int v;
    int c;
} t;


int fcmp1(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

void s1(int a[], int la) {
    qsort(a, la, sizeof(int), fcmp1);
}

void pr1(int a[], int la) {
    int i;

    for (i = 0; i < la; i++)
        printf("%d ", a[i]);

    puts("");
}


void c(int a[], int la, t b[], int lb) {
    int i;
    int bi = 0;

    b[0].v = a[0];
    b[0].c = 1;

    for (i = 1; i < la; i++) {
        if (a[i] == b[bi].v)
            b[bi].c++;
        else {
            b[++bi].v = a[i];
            b[bi].c = 1;
        }
    }
}


int fcmp2(const void *a, const void *b) {
    return ((t *)a)->c - ((t *)b)->c;
}

void s2(t b[], int lb) {
    qsort(b, lb, sizeof(t), fcmp2);
}

void pr2(t b[], int lb) {
    int i;

    for (i = 0; i < lb; i++)
        printf("%d,%d ", b[i].v, b[i].c);

    puts("");
}


void e(t b[], int lb, int r[], int lr) {
    int i;

    for (i = 0; i < lb; i++)
        r[i] = b[i].v;
}


int main() {
    int a[] = {2, 5, 3, 2, 1, 2, 3, 2, 5, 2, 1, 5, 3, 4, 3};
    int la = 15;

    t b[5];
    int lb = 5;

    int r[5];
    int lr = lb;


    puts("Getallen:");
    pr1(a, la);

    puts("1) sorteren op getal:");
    s1(a, la);
    pr1(a, la);

    puts("2) aantallen bepalen:");
    c(a, la, b, lb);
    pr2(b, lb);

    puts("3) sorteren op aantal:");
    s2(b, lb);
    pr2(b, lb);

    puts("Het resultaat:");
    e(b, lb, r, lr);
    pr1(r, lr);
}

Zoals ik al zei: In Php is dat allemaal veel makkelijker te doen met array_count_values en asort.

[Janoz]

Met bucketsort voer je stap 1 en 2 tegelijk uit. Je loop de hele rij door en je telt gewoon voorkomens. Het gesorteerde resultaat heeft geen enkele koppeling meer met het orgineel, maar dat is het offer wat je moet brengen om er een O(N) algoritme van te maken ipv een O(N log N).

[Daos]

Janoz schreef op woensdag 14 maart 2007 @ 14:08:
Met bucketsort voer je stap 1 en 2 tegelijk uit. Je loop de hele rij door en je telt gewoon voorkomens. Het gesorteerde resultaat heeft geen enkele koppeling meer met het orgineel, maar dat is het offer wat je moet brengen om er een O(N) algoritme van te maken ipv een O(N log N).

Voor de complexiteit maakt het niet uit of stap 1 en 2 samengevoegd worden. Stap1 gaat net zo snel als een samengevoegd algoritme. Stap 2 is heel simpel en gaat altijd in O(N).

Bij het samenvoegen hoef je geen informatie te verliezen.


De keuze of je wel of niet samen moet voegen hangt dus alleen af van de hoeveel werk de je zelf er aan hebt.
In Php is er een functie die stap 1 en 2 in 1 keer kan doen -> Samenvoegen en die functie het werk laten doen.
In andere talen waar dat niet kan -> Standaard sorteerfunctie voor stap 1 en eigen functietje voor stap 2. Als er in de taal zelf geen sorteerfunctie zit, dan kan je altijd wel een implementatie ergens vandaan plukken.

Een eigen samenvoeging maken is erg veel werk.

[Janoz]

Ik heb mijn algoritmen niet meer helemaal scherp, maar volgens mij werkte bucketsort door een array te nemen van counters. Vervolgens loop je door je set heen en verhoog je de counter van het element wat je dan tegen komt. Het resultaat is dan een frequentie tabel. Dit terugrekenen naar de lijst doe je door die array te doorlopen en vervolgens de index net zo vaak af te drukken als de waarde die die teller heeft. Je hoeft je lijst niet op volgorde te zetten om de frequentie tabel te maken.

Het bucketsort algoritme levert dus eerst een frequentie tabel op en dan een lijst. Het lijkt me dan ook vreemd om in de volgende stap er weer een frequentie tabel van te maken.

maar goed, het kan zijn dat mijn algoritmekennis wat roestig is

[ Voor 11% gewijzigd door Janoz op 14-03-2007 16:54 ]

[Daos]

BucketSort is het algoritme dat je gebruikt als je dossiers oid met de hand sorteert op achternamen:
- Je hebt bakjes met labels a-e, f-k, l-p, q-t, u-z
- Je kijkt naar de eerste letter en gooit dossier in het juiste bakje.
- Je sorteert per bakje de dossiers met InsertionSort of zo iets.
- Je maakt weer een grote stapel

Het is (vrijwel altijd) mogelijk dat er in een bakje verschillende namen voorkomen en daarom moest je de inhoud van de bakjes ook nog sorteren.


In software zijn de bakjes samen 1 array en meerdere items worden in zo'n bakje bewaard in een gesorteerde linkedlist. Je krijgt dus een array van linkedlists. De InsertionSort zit verstopt in het toevoegen van een item aan de gesorteerde linkedlist.


Toch maar even de PHP versie van het oorsponkelijke probleem:

PHP:

$getallen  = array(2, 5, 3, 2, 1, 2, 3, 2, 5, 2, 1, 5 ,3, 4, 3);
$aantallen = array_count_values($getallen);
asort($aantallen);
print_r($aantallen);

En dat geeft:

Array (
    [4] => 1
    [1] => 2
    [5] => 3
    [3] => 4
    [2] => 5
)

Het blijft onvoorstelbaar dat iemand dagen met zoiets bezig is.

[Janoz]

Ik ken bucketsort. De variant waar ik het over had was degene waarbij je weet welke items er in je lijst voorkomen, maar alleen niet weet hoeveel en waar ze staan. In dit geval zijn het cijfers van 1 t/m 5 en heb je voor de mapjes enkel een array met 5 posities nodig en hoeft er per bucket niet meer gesorteerd te worden. Maar goed, we praten een beetje langs elkaar heen . Ik ben het verder helemaal met je eens dat het inderdaad vreemd is dat iemand heir zo lang mee bezig moet zijn. Ik vermoed echter dat TS de opdracht heeft om het algoritme daadwerkelijk uit te schrijven, maar dan nog. In principe zou je dat ook in een middag tijdens een practicum moeten kunnen doen.