Worst Case of Number of Swaps in Selection Sort

The best case and worst case running time of selection sort are O(n^2). This is because regardless of how the elements are initially arranged, on the i iteration of the main for loop, the algorithm always inspects each of the remaining n-i elements to find the smallest one remaining.

Selection sort is the algorithm which takes minimum number of swaps, and in the best case it takes ZERO (0) swaps, when the input is in the sorted array like 1,2,3,4. But the more pertinent question is what is the worst case of number of swaps in selection sort? And for which input does it occur. 

Answer: Worst case of number of swaps is n-1. But it does not occur for the just the oppositely ordered input, rather the oppositely ordered input like 6,5,3,2,1 does not take the worst number of swaps rather it takes n/2 swaps. So what is really the input for which the number of swaps takes N-1 swaps, if you analyse a bit more you’ll see that the worst case occurs for “SINE WAVE KIND OF AN INPUT”.  That alternatively increasing and decreasing input.

7 6 8 5 9 4 10 3 - input of eight (8) elements will therefore require 7 swaps 

3 6 8 5 9 4 10 7               1)

3 4 8 5 9 6 10 7 2)

3 4 5 8 9 6 10 7 3)

3 4 5 6 9 8 10 7 4)

3 4 5 6 7 8 10 9 5)

3 4 5 6 7 8 9 10 6)

3 4 5 6 7 8 10 9               7)

Hence proved. Now the code of selection sort in C.

#include<stdio.h>

#include<stdlib.h>

int main(){

    int n,c;

    int smallest;

    scanf("%d",&n);

    int a[n];

    for(int i=0;i<n;i++){

        scanf("%d",&a[i]);

    }

    for(int i=0;i<n-1;){

        smallest = a[i];

        c=i;

        for(int j=i+1;j<n;j++){

            if(a[j]<=smallest){

                smallest = a[j];

                c=j;

            }

        }

        if(c!=i){

        a[c]=a[i];

        a[i]=smallest;

       //  printf("hello\n"); for counting the number of swaps

        }

        i++;

    }

    for(int i=0;i<n;i++)

        printf("%d ",a[i]);

    return 0;

    

}

ROD CUTTING PROBLEM - Dynamic Programming

Hey I have come up with a wonderful algorithm for solving the rod cutting problem using dynamic programming. The rod cutting algorithm as per CLRS takes O(n^2) but but but there is a suspense, in CLRS Prof. Cormen embodies the solution to only one subproblem. So I brainstormed a bit and found that if you try to find to modify the solution for both the subproblem and optimise the code a bit then you can achieve O(nlogn) .

You'll not find O(nlogn) implementation of Rod Cutting Problem anywhere on the net. Go through the code, at first it's hard to completely understand it, but if you try a bit harder you'll know what I have done. The link to problem description is given below:

https://en.wikipedia.org/wiki/Cutting_stock_problem

Here is the implementation in C:

#include<stdio.h>

#include<stdlib.h>

#define maxi(a,b) ((a) > (b) ? a : b)

int main(){

    int i,j,n,q=0;

    printf("Enter the length of the array");

    scanf("%d",&n);

    int a[n+1],r[n+1];

    a[0]=0;

    a[1]=1;

    for(i=2;i<=n;i++)

        scanf("%d",&a[i]);

    for(i=0;i<=n;i++)

        r[i]=0;

    r[1]=1;

    

    for(i=2;i<=n;i++){

        q = a[i];

        for(j=1;j<=i/2;j++)

            q = maxi(q,(r[j]+r[i-j]));

        r[i]=q;

    }

    for(i=1;i<=n;i++)

        printf("%d ",r[i]);

    return 0;

                       

}

INPUT : Enter the length of the array

10

5 8 9 10 17 17 20 24 30

OUTPUT: 1 5 8 9 10 17 18 22 25 30

If you have any doubts feel free to ask in the comments section below.

                       

Maximum Perimeter Triangle

This is a simple but tricky greedy problem. I find the solution without complicating the things in O(n logn), I hope you'll like this! . Check out the link below for the problem Description.
https://www.hackerrank.com/challenges/maximum-perimeter-triangle/problem

Solution:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
int cmpfunc (const void * a, const void * b)
{
   return (*(int*)b - *(int*)a);
}

int main() {

    int n,i,c=0;
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    qsort(a, n, sizeof(int), cmpfunc);

    for(i=0;i<n-2;i++){
        if(a[i]<(a[i+1]+a[i+2])){
            c=1;
            printf("%d %d %d",a[i+2],a[i+1],a[i]);
            break;
        }
    }
    if(c==0)
        printf("-1");    
    return 0;
}

Luck Balance

Just a trivial greedy problem. Check out the link for the problem description :
https://www.hackerrank.com/challenges/luck-balance


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int main() {
    int a[100]={0};
    int N,K,c=0,i=0,l,t,c1,c2,sum=0;
    scanf("%d %d",&N,&K);

    while(i!=N){
        scanf("%d %d",&l,&t);
        if(t==0)
            sum+=l;
        else if(t==1){
            a[i]=l;
            c+=1;
        }
      i++;
    }

    qsort(a, 100, sizeof(int), cmpfunc);

    c1=100-c;
    c2=c-K;
    for(i=c1;i<100;i++){
        if(i<c1+c2)
        sum=sum-a[i];
       
    else if(i>=c1+c2)
        sum=sum+a[i];
    }
    printf("%d",sum);
    return 0;
}

The Coin Change Problem

https://www.hackerrank.com/challenges/coin-change

Checkout my solution to this hard Dynamic Programming from Hackerrank:

#include <math.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <assert.h>

#include <limits.h>

#include <stdbool.h>

int comp (const void * elem1, const void * elem2)

{

    int f = *((int*)elem1);

    int s = *((int*)elem2);

    if (f > s) return  1;

    if (f < s) return -1;

    return 0;

}

int main(){

    int n,m,i,j;

    scanf("%ld %ld", &n,&m);

    long int a[m],b[n+1];

     b[0]=1;

     for(i=1;i<(n+1);i++){

        b[i]=0;

     }

    for(i=0;i<m;i++)

        scanf("%ld",&a[i]);

    qsort(a, sizeof(a)/sizeof(*a), sizeof(*a), comp);

    for(i=0;i<m;i++){

        for(j=a[i];j<n+1;j++)

            b[j]+=b[j-a[i]];

    }

    printf("%ld",b[n]);

    return 0;

}

Count number of ways to reach a given score in a game

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of ways to reach the given score.

The idea is to create a table of size n+1 to store counts of all scores from 0 to n. For every possible move (3, 5 and 10), increment values in table and it can be solved in O(n) time and O(n) auxiliary space.

Following is the implementation in C++

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

    int n;

    cout<<"Enter the score"<<endl;

    cin>>n;

    vector<int> v(n+1,0);

    v[0] = 1;

    for(auto i = 3;i!=v.size();++i){

        v.at(i)+=v.at(i-3);

    }

    for(auto i = 5;i!=v.size();++i){

        v.at(i)+=v.at(i-5);

    }

    for(auto i = 10;i!=v.size();++i){

        v.at(i)+=v.at(i-10);

    }

    cout<<*(v.end()-1);

    return 0;

}

You can change the value of the points in the game by changing the value of variable i in the three for loops...Enjoy the game!

Partition Problem - Karmarkar Karp Algorithm

This is an implementation of the Karmarkar-Karp algorithm in O(nlogn) steps.

The Karmarkar-Karp heuristic begins by sorting the numbers in decreasing order. At each step, the algorithm commits to placing the two largest numbers in different subsets, while differencing the decision about which subset each will go in. The algorithm continues removing the two largest numbers, replacing by their difference in the sorted list, until there is only one number left, which is the value of the final subset difference. If the final subset difference is equal to 0, then partition is possible else not possible.

Following is the implementation of the algorithm in C++ and note that this algorithm better than the Dynamic Programming Approach because Dynamic approach takes longer time for large value of sum.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
   vector<int>v={3, 1, 1, 2, 2, 1};
   sort(v.begin(),v.end());
   int a;
   while(v.size()!=1){
        auto i = v.end()-1;
        a = (*(i))-(*(i-1));
        v.pop_back();
        v.pop_back();
        v.push_back(a);
        sort(v.begin(),v.end());
   }
   if (a==0)
        cout<<"Partition is Possible";
    else
        cout<<"Partition is not Possible";


}
I will soon update the code of the algorithm, so that you can also find the two subsets partition elements. Till then enjoy the game of partitions.