#include<bits/stdc++.h>
using namespace std;

// bubble sort
void bubble(vector<int> &a)
{
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        int c=0;
        for(int j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1]){
                c=1;
                swap(a[j],a[j+1]);
            }
        }
        if(c==0)
            break;
    }
}
//selection sort
void selection(vector<int> &a)
{
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        int pos=i;
        for(int j=i+1;j<n;j++)
            if(a[j]<a[pos])
                pos=j;
        swap(a[i],a[pos]);
    }
}
//insertion sort
void insertion(vector<int> &a)
{
    int n=a.size();
    for(int i=0;i<n;i++)
    {
        int temp=a[i];
        int j=i-1;
        while(j>=0&&a[j]>temp)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;
    }
}
//merge sort
void mergefunc(int l,int m,int h,vector<int> &arr)
{
    int a[m-l+1];
    int b[h-m];
    int i=l,j=0;
    while(i<=m)
    {
        a[j++]=arr[i++];
    }
    j=0;
    while(i<=h)
    {
        b[j++]=arr[i++];
    }
    int si1=m-l+1,si2=h-m;
    i=j=0;
    int k=l;
    while(i<si1&&j<si2)
    {
        if(a[i]<=b[j])
        {
            arr[k++]=a[i++];
        }
        else
        {
            arr[k++]=b[j++];
        }
    }
    while(i<si1)
    {
        arr[k++]=a[i++];
    }
    while(j<si2)
    {
        arr[k++]=b[j++];
    }
    return;
}
void mergesort(int l,int h,vector<int> &a)
{
    if(l<h)
    {
        int m=(l+h)/2;
        mergesort(l,m,a);
        mergesort(m+1,h,a);
        mergefunc(l,m,h,a);
    }
    return;
}
//heap sort
void maxheapify(int i,int n,vector<int> &a)
{
    int left=(2*i)+1;
    int right=(2*i)+2;
    int m=i;
    if(left<n&&a[left]>a[m])
        m=left;
    if(right<n&&a[right]>a[m])
        m=right;
    swap(a[i],a[m]);
    if(m!=i)
        maxheapify(m,n,a);
    return;
}
void buildmaxheap(vector<int> &a)
{
    int n=a.size()-1;
    for(int i=n/2;i>=0;i--)
        maxheapify(i,n,a);
    return;
}
void heapsort(vector<int> &a)
{
    int n=a.size();
    buildmaxheap(a);
    for(int i=0;i<n;i++)
    {
        swap(a[0],a[n-i-1]);
        maxheapify(0,n-i-1,a);
    }
}
//quick sort using last element to partition
int partition_elements(int l,int h,vector<int> &a)
{
    int curr=l-1;
    int pivot=a[h];
    for(int i=l;i<h;i++)
    {
        if(a[i]<=pivot)
        {
            curr++;
            swap(a[curr],a[i]);
        }
    }
    curr++;
    swap(a[curr],a[h]);
    return curr;
}
void quicksort(int l,int h,vector<int> &a)
{
    if(l<h)
    {
        int p=partition_elements(l,h,a);
        quicksort(l,p-1,a);
        quicksort(p+1,h,a);
    }
    return;
}
//stable counting sort
vector<int> countingsort(vector<int> a)
{
    int n=a.size();
    int k=*max_element(a.begin(),a.end());
    int *c=(int *)calloc(k+1,sizeof(int));
    for(int i=0;i<n;i++)
        c[a[i]]++;
    for(int i=1;i<=k;i++)
        c[i]=c[i-1]+c[i];
    vector<int> b(n);
    for(int i=n-1;i>=0;i--)
    {
        b[c[a[i]]-1]=a[i];
        c[a[i]]--;
    }
    free(c);
    return b;
}
//bucket sort
void bucketsort(vector<int> &a)
{
    int n=a.size();
    int BUCKETS=*max_element(a.begin(),a.end());
    int *buckets=(int *)calloc(BUCKETS+1,sizeof(int));
    for(int i=0;i<n;i++)
        buckets[a[i]]++;
    for(int i=0,j=0;j<=BUCKETS;j++)
        for(int k=0;k<buckets[j];k++)
            a[i++]=j;
}
int main()
{
    vector<int> a={5,7,8,10,1,4,9,11,2};
    //bubble(a);
    //selection(a);
    //insertion(a);
    //mergesort(0,a.size()-1,a);
    //heapsort(a);
    //quicksort(0,a.size()-1,a);
    //a=countingsort(a);
    bucketsort(a);
    for(auto it=a.begin();it!=a.end();it++)
        cout<<*it<<"\t";
    cout<<endl;
}