Selection Sort

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a[100];
    int n,min;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-1;i++){
        min=i;
        for(int j=i+1;j<n;j++){
            if(a[j]<a[min])
                min=j;
        }
        if(min!=i){
            int temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }
    }
     for(int i=0;i<n;i++)
        cout<<a[i]<<" ";

    return 0;
}

Insertion Sort

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int a[100];
    int n,x;
    cin>>n;
    int j;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++){
        x=a[i];
        for(j=i;j>0;j--){
            if(a[j-1]>x)
                a[j]=a[j-1];
            else
                break;
        }
        a[j]=x;
    }
     for(int i=0;i<n;i++)
        cout<<a[i]<<" ";

    return 0;
}

Time Conversion

Problem Link (Click here)

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

int main(){
    string time;
    string temp;
    cin >> time;
    temp = time;
    if(time[8]=='A'){
        time.erase (8,2);
        if(time[0]=='1'&&time[1]=='2'){
            time[0]='0';
            time[1]='0';
        }
        cout<<time;
    }
    else{
        time.erase (2,8);
        stringstream ss(time);
        int x;
        ss >> x;
        if(x!=12){
            x=x+12;
        }
        cout<<x;
        temp.erase (0,2);
        temp.erase (6,2);
        cout<<temp;
    }

    return 0;

}

COUNTING SORT WITH NEGATIVE VALUE

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int temp_p[100];
    int temp_n[100];
    int m,n,i,x;
    int j=0;
    int p=0;
    cout<<"Total number : ";
    cin>>n;
    cout<<"Maximum number : ";
    cin>>m;
    int pos[m+1];
    int neg[m+1];
    memset(pos, 0, sizeof pos);
    memset(neg, 0, sizeof neg);
    for(i=0;i<n;i++){
        cin>>x;
        if(x>=0){
            temp_p[j]=x;
            pos[x]++;
            j++;
        }
        else{
            temp_n[p]=x*-1;
            neg[x*-1]++;
            p++;
        }
    }
    for(i=1;i<=m;i++){
        pos[i]=pos[i]+pos[i-1];
        neg[i]=neg[i]+neg[i-1];
    }
    int arry_p[j];
    int arry_n[p];

    for(i=0;i<j;i++){
        int b=temp_p[i];
        arry_p[pos[b]-1]=b;
        pos[b]--;
    }
    for(i=0;i<p;i++){
        int b=temp_n[i];
        arry_n[neg[b]-1]=b;
        neg[b]--;
    }
    for(i=p-1;i>=0;i--){
        cout<<(arry_n[i]*-1)<<" ";
    }
    for(i=0;i<j;i++){
        cout<<arry_p[i]<<" ";
    }
    cout<<endl;


    return 0;
}

COUNTING SORT

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
    int temp[100];
    int m,n,i;
    cout<<"Total number : ";
    cin>>n;
    cout<<"Maximum number : ";
    cin>>m;
    int c[m+1];
    memset(c, 0, sizeof c);
    for(i=0;i<n;i++){
        cin>>temp[i];
        int a=temp[i];
        c[a]++;
    }
    for(i=1;i<=m;i++)
        c[i]=c[i]+c[i-1];

    int arry[n];
    for(i=0;i<n;i++){
        int b=temp[i];
        arry[c[b]-1]=b;
        c[b]--;
    }
    for(i=0;i<n;i++){
        cout<<arry[i]<<" ";
    }
    cout<<endl;

    return 0;
}

Kruskal's algorithm

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

struct node{
    int s;
    int e;
    int weight;
};

int makeset(int a[],int e){
    for(int i=0;i<=e;i++)\
        a[i]=i;
    return a[e];
}
int found(int arry[], int x){
    if(x==arry[x])
        return x;
    return found(arry, arry[x]);
}
int Union(int arry[],int x,int y){
    if(x!=y)
        arry[y]=x;
}

bool compare(node a, node b){
    if(a.weight<b.weight)
        return true;
    else
        return false;
}

int main(){

    int i, totalEdge, totalNode, p1, p2, w;
    node edgeList[50];
    cout << "How many vertices?  " ;
    cin>>totalNode;
    cout << "How many edges?  " ;
    cin>>totalEdge;

    for(i=0;i<totalEdge;i++){
        cin>>p1;
        cin>>p2;
        cin>>w;

        edgeList[i].s = p1;
        edgeList[i].e = p2;
        edgeList[i].weight = w;
        edgeList[i].s = p2;
        edgeList[i].e = p1;
    }
    sort(edgeList,edgeList+totalEdge, compare);
    int arry[totalEdge];
    makeset(arry,totalEdge);

    int total=0;
    for(int i=0; i<totalEdge; i++){
        int x=found(arry, edgeList[i].s);
        int y=found(arry, edgeList[i].e);
        if(x!=y){
            Union(arry,x,y);
            total+=edgeList[i].weight;
            cout << edgeList[i].s << " " << edgeList[i].e << " " << edgeList[i].weight << endl;
        }
    }
    cout<< total<<endl;


    return 0;
}

Coin Change Problem Using Dynamic Programming

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <conio.h>
#include <climits>
#include <cstring>

using namespace std;

int main ()
{
    int amount;
    int b[10000];
    memset(b, INT_MAX, sizeof b);
    b[0]=0;
    int a[20];
    int coin;
    int i;
    cout << "amount : " ;
    cin >> amount;
    cout << "No of coin : " ;
    cin >> coin;
    for(i=0; i<coin; i++){
        cin >> a[i];
    }

     for(int i = 0; i <amount; i++)
    {
        for(int j = a[i] ; j <= amount; j++)
        {
            int pre = b[j];
            int cur = 1+b[j-a[i]];
            b[j] = min(pre,cur);
        }
    }
     cout << b[amount];

getch();
return 0;
}