Shell Sort

#include <iostream>
using namespace std;
#define siz 100000000

int a[siz];
void swap(int i, int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

void shell_sort(int a[], int n)
{
    int d=n,flag=1;
    while(flag!=0||d>1)
    {
        flag=0;
        d=(d+1)/2;
        for(int i=0;i<n-d;i++)
        {
            if(a[i+d]<a[i])
            {
                swap(i+d,i);
                flag=1;
            }
        }
    }
}

int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++) cin>>a[i];
        shell_sort(a,n);
        for(int i=0;i<n;i++) cout<<a[i]<<endl;
    }
    return 0;
}

Selection Sort

#include <iostream>
using namespace std;
#define siz 100000000
int a[siz];

void selection_sort(int a[], int n)
{
    for(int i=0;i<n-1;i++)
    {
        int min=i;
        for(int j=i+1;j<n;j++)
        {
            if(a[j]<a[min])
            min=j;
        }
        int temp=a[i];
        a[i]=a[min];
        a[min]=temp;
    }
    for(int i=0;i<n;i++) cout<<a[i]<<endl;
}

int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++) cin>>a[i];
        selection_sort(a,n);
    }
    return 0;
}

Insertion Sort

#include <iostream>
using namespace std;
int a[100],n;
void insertion_sort(int a[], int n)
{
    for(int j=2;j<=n;j++)
    {
        int key=a[j];
        int i=j-1;
        while(i>0&&a[i]>key)
        {
            a[i+1]=a[i];
            i-=1;
            a[i+1]=key;
        }
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    cout<<endl;
}
int main()
{
    while(cin>>n)
    {
        for(int i=1;i<=n;i++) cin>>a[i];
        insertion_sort(a,n);
    }
    return 0;
}

Counting Sort

#include <iostream>
using namespace std;
#define siz 100000000

int a[siz],b[siz],c[siz];

void counting_sort(int a[], int n, int k)
{
    for(int i=0;i<=k;i++) c[i]=0;
    for(int j=1;j<=n;j++) c[a[j]]=c[a[j]]+1;
    for(int i=2;i<=k;i++) c[i]=c[i]+c[i-1];
    for(int j=n;j>=1;j--)
    {
        b[c[a[j]]]=a[j];
        c[a[j]]-=1;
    }
    for(int i=1;i<=n;i++) cout<<b[i]<<endl;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int k=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            k=max(k,a[i]);
        }
        counting_sort(a,n,k);
    }
    return 0;
}#include <iostream>
using namespace std;
#define siz 100000000

int a[siz],b[siz],c[siz];

void counting_sort(int a[], int n, int k)
{
    for(int i=0;i<=k;i++) c[i]=0;
    for(int j=1;j<=n;j++) c[a[j]]=c[a[j]]+1;
    for(int i=2;i<=k;i++) c[i]=c[i]+c[i-1];
    for(int j=n;j>=1;j--)
    {
        b[c[a[j]]]=a[j];
        c[a[j]]-=1;
    }
    for(int i=1;i<=n;i++) cout<<b[i]<<endl;
}
int main()
{
    int n;
    while(cin>>n)
    {
        int k=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            k=max(k,a[i]);
        }
        counting_sort(a,n,k);
    }
    return 0;
}

Brick Sort

#include <iostream>
using namespace std;
#define siz 1000000
int a[siz];
void swap(int a[], int i, int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void Brick_sort(int a[], int n)
{
    bool sorted=false;
    while(sorted!=true)
    {
        sorted=true;
        for(int i=1;i<n-1;i+=2)
        {
            if(a[i]>a[i+1])
            {
                swap(a,i,i+1);
                sorted=false;
            }
        }
        for(int i=0;i<n-1;i+=2)
        {
            if(a[i]>a[i+1])
            {
                swap(a,i,i+1);
                sorted=false;
            }
        }
    }
    for(int i=0;i<n;i++) cout<<a[i]<<endl;
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=0;i<n;i++) cin>>a[i];
        Brick_sort(a,n);
    }
    return 0;
}

Knapsack

#include <iostream>
using namespace std;
#define siz 100

int n,c[siz],v[siz],used[siz],W;

void Knapsack()
{
    int cw,i,mx;
 double tv;

 for (i=0;i<n;i++) used[i]=0;

 cw=W;
 while (cw>0)
 {
  mx=-1;
        for (i=0;i<n;i++)
        if ((used[i]==0)&&((mx == -1)||((double)v[i]/c[i] > (double)v[mx]/c[mx]))) mx = i;

  used[mx]=1;
  cw-=c[mx];
  tv+=v[mx];
  if(cw<0)
  {
   tv-=v[mx];
   tv+=(1+(double)cw/c[mx])*v[mx];
  }
 }
 cout<<tv<<endl;
}

int main()
{
    cin>>W>>n;
    for(int i=0;i<n;i++) cin>>v[i]>>c[i];
    Knapsack();
    return 0;
}

Prims Algorithm

#include <iostream>
#include <queue>
#include <vector>
#define INF 100000
using namespace std;

struct edge{
    vector <int> Adj;
    vector <int> Cost;
};

struct node{
    int x,y;
};

edge Ed[100];
int N,E;
int key[100];
char F[100];
int P[100], Cost;
int SS[100][100];

class comp{
    public:
    bool operator()(const node &a, const node &b){
        return a.y>b.y;
    }
};

void CT(int u){
    if(F[u]==1||u==1) return;
    F[u]=1;
    if(P[u]==-1) return;
    Cost+=SS[u][P[u]];
    CT(P[u]);
}

int Prim(){
    int i,j,u,v,c,cost;
    Cost=0;
    priority_queue<node, vector<node>, comp>Q;
    node temp, dum;
    for(i=1;i<=N;i++) key[i]=INF;
    key[1]=0;
    temp.x=1;
    temp.y=0;
    Q.push(temp);
    P[1]=-1;
    while(!Q.empty()){
        temp=Q.top();
        Q.pop();
        u=temp.x;
        F[u]=1;
        for(i=0;i<Ed[u].Adj.size();i++){
            v=Ed[u].Adj[i];
            c=Ed[u].Cost[i]+temp.y;
            if(F[v]==0){
                if(key[v]>c){
                    dum.x=v;
                    dum.y=c;
                    key[v]=c;
                    P[v]=u;
                    Q.push(dum);
                }
            }
        }
    }
    for(i=1;i<=N;i++) F[i]=0;
    for(i=1;i<=N;i++){
        if(F[i]==0)
            CT(i);
    }
    return Cost;
}

int main()
{
    int c,u,v,n;
    cin>>N>>E;
    n=E;
    while(n--)
    {
        cin>>u>>v>>c;
        Ed[u].Adj.push_back(v);
        Ed[u].Cost.push_back(c);
        Ed[v].Adj.push_back(u);
        Ed[v].Cost.push_back(c);
        SS[u][v]=SS[v][u]=c;
    }
    cout<<Prim()<<endl;
}