#include <stdio.h>
#include <stdlib.h>
//dupa
// sortowanie przez wstawianie
void sort(int tab[])
{
    int i=0,x=0,j=0;
    for(i=18;i>=0;i--)
    {
        x=tab[i];
        j=i+1;
        while((j<20)&&(x>tab[j]))
        {
            tab[j-1]=tab[j];
            j++;
        }
        tab[j-1]=x;
    }
}

//sortowanie przez wybor
void sort2( int tab[], int size )
{
    int k,tmp,i,j;
    for(i = 0; i < size; i++ )
    {
        k = i;
        for(j = i + 1; j < size; j++ )
        if( tab[ j ] < tab[ k ] )
             k = j;

        tmp=tab[i];
        tab[i]=tab[k];
        tab[k]=tmp;
    }
}
//sortowanie kubelkowe
void sortowanieKubelkowe( int tab[],int n)
{
    int maxx,minn,pom,i,j;
    maxx=minn=tab[0];
    for(i=0;i<n;i++)
    {
        if(tab[i]>maxx) maxx=tab[i];
        if(tab[i]<minn) minn=tab[i];
    }
    pom=(maxx-minn)+1;
    int licz[pom];
    int zlicz=0;
    for(i=minn;i<=maxx;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i==tab[j]) zlicz++;
        }
        licz[i]=zlicz;
        zlicz=0;
    }
    printf("\n Zliczone kubelki: \n");
    for(i=0;i<pom;i++)
    {
        printf("%d ",licz[i]);
    }
    printf("\n");
    printf("\n");
    j=0;
    for(i=0;i<n;i++)
    {
        if(licz[j]==0)
        {
            j++;
            i--;
        }
        else
        {
           tab[i]=j;
           licz[j]--;
        }

    }
}


void quicksort(int tab[],int p,int k)
{
    int i=p,j=k,tmp;
    int sr=(p+k)/2;
    int x=tab[sr];

    do{
        while(tab[i]<x)i++;
        while(tab[j]>x)j--;

        if(i<=j)
        {
            tmp=tab[i];
            tab[i]=tab[j];
            tab[j]=tmp;

            i++;
            j--;
        }
    }while(i<=j);

    if(p<j)quicksort(tab,p,j);
    if(k>i)quicksort(tab,i,k);

}

int main()
{
    int tab[20];
    int i,j;
    printf("Nieposortowana tablica: \n");
    //losowanie i wyswietlanie tablicy nie posortowanej
    for(i=0;i<20;i++)
    {
       tab[i]=rand()%10;
       printf("%d ",tab[i]);
    }

    printf("\n");
    /*
    sort2(tab,20);
    printf("Posortowana tablica: \n");
    for(j=0;j<20;j++)
    {
        printf("%d ",tab[j]);
    }
    */
    printf("\n");
    sortowanieKubelkowe(tab,20);
    printf("Posortowana tablica: \n");
    for(j=0;j<20;j++)
    {
        printf("%d ",tab[j]);
    }
    return 0;
}