Radix sort dokaze vyriesit triedenie tohoto intervalu v linearnom case no mam v mojom programe problem s nasobkami N napr. mam pole cisiel o velkosti 2 a je tam 2 a 4 pole to nevytriedi pretoze cisla %n vyjdu narovnako ... dokazal by mi dakto poradit ako tento bug vyriesit (samozrejme pri zachovani linearne zlozitosti algoritmu)

#include<stdio.h>
#include <malloc.h>

int radixSort(int *x, int n, int exp)
{
    int output[40000];
    int i, bucket[40000];

    //makes bucket full of zero
    for (i=0; i < n; i++)bucket[i] = 0;

    for (i = 0; i < n; i++)bucket[ (x[i]/exp)%n ]++;

    for (i = 1; i < n; i++)bucket[i] += bucket[i - 1];

    for (i = n - 1; i >= 0; i--) {
        output[bucket[ (x[i]/exp)%n] - 1] = x[i];
        bucket[(x[i]/exp)%n]--;
    }
    for (i = 0; i < n; i++)x[i] = output[i];
    return 0;
}

void sorting(int *x, int n)
{
    radixSort(x,n,1);
    radixSort(x,n,n);
}

int main(void)
{
    int i, *x, n;

    scanf("%d", &n);
    x = (int*)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
        scanf("%d", &x[i]);

    sorting(x, (const size_t) n);

    printf("%d", x[0]);
    for (i = 1; i < n; i++)
    {
        printf(" %d", x[i]);
        if (x[i-1] > x[i])
        {
            printf(" -- CHYBA\n");
            return 0;
        }
    }
    printf("\n");

    printf("OK\n");
    return 0;
}