Basket sort (jazyk C)

Řadící algoritmus basket sorting je velmi jednoduchý – máme řadu „košíků“ s čísly (indexy). Do košíku číslo jedna dáváme vechny jedničky, do košíku číslo dva dvojky atd. Až všechna čísla nasypeme do košíků, vyndáváme je postupně od košíku jedna, pak dva atd. V kódu je systém košíků reprezentován dvojrozměrným polem. Jeden rozměr jsou košíky, druhý pak jejich obsah.
Pokud se jedná o jednoduché objekty, nemusíme je do košíků dávat všechny. Není tedy potřeba vytvářet obrovská pole intů, stačí jen aby „košíky“ obsahovaly jen jejich počet, tj. kolik je jedniček, kolik je dvojek atd.

 basket

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

#define SIZE 20
#define BASKET_SIZE 100

void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void printdata(int data[SIZE])
{
    int i;
    for (i = 0; i < SIZE; i++)
        printf("%02d", data[i]);

    printf("\n");
}

void basket_sort(int data[SIZE])
{
    int basket[100];
    int i, j, index = 0;

    for (i = 0; i < BASKET_SIZE; i++)
        basket[i] = 0; /* pro jistotu, nerad se spoleham na implicitni hodnoty */

    for (i = 0; i < SIZE; i++)
    {
        if (data[i] > BASKET_SIZE - 1 || data[i] < 0)
            printf("\nSerazena budou pouze cisla od 0 do 99\n");
        else
            basket[data[i]]++;
    }

    for (i = 0; i < BASKET_SIZE; i++)
    {
        for (j = 0; j < basket[i]; j++)
        {
            data[index++] = i;
        }
    }
}

int main(int argc, char *argv[])
{
    int data[SIZE] = {5, 3, 8, 48, 3, 7, 6, 11, 5, 29,
        4, 1, 33, 8, 13, 21, 39, 42, 20, 12 };

    printdata(data);
    basket_sort(data);
    printdata(data);

    return 0;
}
Příspěvek byl publikován v rubrice Programování se štítky , , . Můžete si uložit jeho odkaz mezi své oblíbené záložky.