Program for Shell Sort in C

Shell short is an improved and efficient version of the insertion sort.

In this algorithm, we sort the pair of elements that are far apart by gap h.
 The process is repeated by reducing h until it becomes 1.

Shell Sort

Algorithm

Following is the algorithm for shell sort.

Step 1 − Initialize the value of h

Step 2 − Divide the list into smaller 
               sub-list of equal interval h

Step 3 − Sort these sub-lists using insertion sort


Step 4 − Repeat until the complete list is sorted


Program for Shell Sort in C

#include<stdio.h>

void sort(int a[],int n)
{
int gap,i,j,temp;

for(gap=n/2;gap>0;gap/=2)
{
for(i=gap;i<n;i+=1)
{
temp=a[i];

for(j=i;j>=gap&&a[j-gap]>temp;j-=gap)

     a[j]=a[j-gap];

  a[j]=temp;

}

}

}

int main()
{
int a[20],i,n;

printf("Enter number of elements:");

scanf("%d",&n);

printf("Enter array elements:\n");

for(i=0;i<n;++i)
{
scanf("%d",&a[i]);
} sort(a,n);

printf("\nArray after shell sort:\n");

for(i=0;i<n;++i)
printf("%d ",a[i]);

    return 0;
}


Output

Enter number of elements:5
Enter array elements:
56 7 2 9 12

Array after shell sort:
2 7 9 12 56

Read More

Activity Selection Problem

1) Sort the activities according to their finishing time

2) Select the first activity from the sorted array and print it.


3) Do following for remaining activities in the sorted array.

a) If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.

Example:

Consider the following 3 activities sorted by finish time.

 Input:

   start[]  =  {10, 12, 20};

   finish[] =  {20, 25, 30};

Output:

A person can perform at most two activities. The 

maximum set of activities that can be executed 

is {0, 2}

C program:

#include<stdio.h>

/* Prints a maximum set of activities that can be done by a single person, one at a time.*/

//  n   -->  Total number of activities

//  s[] -->  An array that contains
//start time of all activities

//  f[] -->  An array that contains
//finish time of all activities

void printMaxActivities(int s[], int f[], int n)

{

    int i, j;

    printf ("Following activities are selected n ");

    i = 0;

    printf("%d ", i);

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

    {

      // If this activity has start time greater than or

      // equal to the finish time of previously selected

      // activity, then select it

      if (s[j] >= f[i])

      {

          printf ("%d ", j);

          i = j;

      }

    }

}

int main()

{

    int s[] =  {1, 3, 0, 5, 8, 5};

    int f[] =  {2, 4, 6, 7, 9, 9};

    int n = sizeof(s)/sizeof(s[0]);

    printMaxActivities(s, f, n);

    return 0;

}

Output:

Following activities are selected n 0 1 3 4

Read More

Minimum number of Coins

 Find the Minimum number of Coins

1) Initialize result as empty.

2) find the largest denomination that is 

     smaller than V.

3)  Add found denomination to result.

    Subtract the value of found denomination from V.

4) If V becomes 0, then print result.  

   Else repeat steps 2 and 3 

   for the new value of V

Example:

Input: V = 70

Output: 2

We need a 50 Rs note and a 20 Rs note.

C program:

#include <stdio.h>

#define COINS 9

#define MAX 20

// All denominations of Indian Currency

int coins[COINS] = { 1, 2, 5, 10, 20, 50, 100, 200, 2000 };

void findMin(int cost)

{

    int coinList[MAX] = { 0 };

    int i, k = 0;

    for (i = COINS - 1; i >= 0; i--) {

        while (cost >= coins[i]) {

            cost -= coins[i];

            coinList[k++] = coins[i];

        }

    }

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

        printf("%d ", coinList[i]);     }

    return;

}

int main(void)

{

    int n;

    printf("Enter the Rupees u want Change\n");

    scanf("%d",&n);

    printf("Following is minimal number of change for %d: ", n);

    findMin(n);

    return 0;

}

Output:

Enter the Rupees u want Change

1276

Following is minimal number of change for 1276: 200 200 200 200 200 200 50 20 5 1

Read More

Breath First Search

ALGORITHM BFS(G)//Implements a breadth-first search traversal of a given graph
//Input: Graph G = V, E//Output: Graph G with its vertices marked with consecutive //integers in the order they are visited by the BFS traversal
mark each vertex in V with 0 as a mark of being “unvisited”count ← 0for each vertex v in V do
if v is marked with 0Bfs(v)


Algorithm Bfs(v)//visits all the unvisited vertices connected to vertex v//by a path and numbers them in the order they are visited
//via global variable count
count← count + 1; 
mark v with count and initialize a queue with vwhile the queue is not empty do
for each vertex w in V adjacent to the front vertex do
if w is marked with 0count ← count + 1; 
mark w with the countadd w to the queue
remove the front vertex from the queue


C program:

#include<stdio.h>
int count=0;
int n;
void bfs(int a[][n],int b[],int v);
main()
{
    int i,j;
    printf("\nEnter number of vertices:");
    scanf("%d",&n);
    int a[n][n];
    int b[n];
    for(i=0;i<n;i++)
    {

        for(j=0;j<n;j++)
        {
            printf("\nEnter connection bt vertex %c & vertex %c",i+65,j+65);
            scanf("%d",&a[i][j]);
        }
    }
    for(i=0;i<n;i++)
   {

       for(j=0;j<n;j++)
       {
           printf("%d\t",a[i][j]);
       }
       printf("\n");
   }
   for(i=0;i<n;i++)
        b[i]=0;
                bfs(a,b,0);

}
void bfs(int a[][n],int b[],int v)
{

    int i,r=0,f=-1;
    int q[n];
    count++;
    b[v]=count;
    q[++f]=v;
     do
    {
        v=q[r];
        for(i=0;i<n;i++)
        {
            if(a[v][i]==1)
            {
                if(b[i]==0)
                {
                    count++;
                    b[i]=count;
                    q[++f]=i;
                }
            }
        }
       printf("%c\n",q[r++]+65);
    }while(f>=r);
}


Output:

Enter number of vertices:4

Enter connection bt vertex A & vertex A0

Enter connection bt vertex A & vertex B1

Enter connection bt vertex A & vertex C0

Enter connection bt vertex A & vertex D0

Enter connection bt vertex B & vertex A1

Enter connection bt vertex B & vertex B0

Enter connection bt vertex B & vertex C1

Enter connection bt vertex B & vertex D0

Enter connection bt vertex C & vertex A0

Enter connection bt vertex C & vertex B1

Enter connection bt vertex C & vertex C0

Enter connection bt vertex C & vertex D1

Enter connection bt vertex D & vertex A1

Enter connection bt vertex D & vertex B0

Enter connection bt vertex D & vertex C1

Enter connection bt vertex D & vertex D0
0       1       0       0
1       0       1       0
0       1       0       1
1       0       1       0
A
B
C
D

  

Read More

Sieve of Eratosthenes Algorithm

ALGORITHM Sieve(n)

//Implements the sieve of Eratosthenes

//Input: A positive integer > 1

//Output: Array L of all prime numbers less than or equal to n

for p ← 2 to n do A[p] ← p

for p ← 2 to √n do 

if A[p] = 0 //p hasn’t been eliminated on previous passes

j ← p ∗ p

while j ≤ n do

A[j] ← 0 //mark element as eliminated

j ← j + p

//copy the remaining elements of A to array L of the primes

i ← 0

for p ← 2 to n doifA[p] = 0

L[i] ← A[p]

i ← i + 1

return L

Method:

Algorithm to find all the prime numbers less than or equal to a given integer n by Eratosthenes’ method:

1.     Create a list of consecutive integers from 2 to n: (2, 3, 4, …, n).

2.     Initially, let p equal 2, the first prime number.

3.     Starting from p², count up in increments of p and mark each of these numbers greater than or equal to p² itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), etc..

4.     Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

C  program:

//  C program to print all primes smaller than or equal 

//to n using Sieve of Eratosthenes

#include <stdio.h>

#include <stdlib.h>

void SieveOfEratosthenes(int n)

{

    // Create a integer array "prime[0..n]" and initialize

    // all entries it as 1(true). A value in prime[i] will

    // finally be 0(false) if i is Not a prime, else true.

    int prime[n+1];

    int p,i;

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

{

    prime[i]=1;

}

    for (p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is a prime

        if (prime[p] ==1)

        {

            // Update all multiples of p greater than or

            // equal to the square of it

            // numbers which are multiple of p and are

            // less than p^2 are already been marked.

            for ( i=p*p; i<=n; i+= p)

                prime[i] = 0;

        }

    }

    // Print all prime numbers

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

       if (prime[p]==1){

          printf("%d ",p);

}

}

int main()

{

    int n;

    printf("Enter the N value\n");

    scanf("%d",&n);

    printf("Following are the prime numbers smaller than or 

equal to %d\n",n);

    SieveOfEratosthenes(n);

    return 0;

}  

Output:

Enter the N value

30

Following are the prime numbers smaller than or equal to 30

2 3 5 7 11 13 17 19 23 29

Read More

SortAnalysis Aglorithm

ALGORITHM SortAnalysis(A[0..n - 1])

//Input: An array A[0..n - 1] of n orderable elements
//Output: The total number of key comparisons made
count ← 0
for i ← 1 to n - 1 do
v ← A[i]
j ← i - 1
while j ≥ 0 and A[j] > v do
count ← count + 1
A[j + 1] ← A[j]
j ← j - 1
A[j + 1] ← v
return count

C program:

#include<stdio.h>
int main(){
int n,v,i,j,count=0,arr[100];
printf("Enter the No element u want to enter\n");
scanf("%d",&n);
printf("Enter the Elements\n");
for(i=0;i<n;i++){
    scanf("%d",&arr[i]);
}
for(i=1;i<n;i++)
{
    v=arr[i];
    j=i-1;
    while(j>=0 && arr[j]>v){
        count++;
        arr[j+1]=arr[j];
        j--;
        arr[j+1]=v;
    }

}
for(i=0;i<n;i++)
{
    printf("%d, ",arr[i]);
}
printf("\nNo of Steps:%d\n",count);
}

Output:

Enter the No element u want to enter
5
Enter the Elements
1
32
54
6
4
1 ,4, 6, 32, 54
No of Steps:5

Read More

Factorial Algorithm

ALGORITHM F(n)

//Computes n! recursively

//Input: A nonnegative integer n

//Output: The value of n!

if n = 0 return 1

else return F (n - 1) ∗ n

C program:

#include <stdio.h>

 int factorial(int c){

     if(c==1){

        return 1;

     }

     else{

 return c*factorial(c-1);

 }

 }

int main()

{

  int c, n, fact = 1;

  printf("Enter a number to calculate its factorial\n");

  scanf("%d", &n);

  fact=factorial(n);

 // for (c = 1; c <= n; c++)

    //fact = fact * c;

  printf("Factorial of %d = %d\n", n, fact);

  return 0;

}

Output:

Enter a number to calculate its factorial

5

Factorial of 5 = 120

Read More

Binary Algorithm

ALGORITHM Binary(n)

//Input: A positive decimal integer n

//Output: The number of binary digits in n’s binary representation

count ← 1
while n > 1 do

count ← count + 1

n ← n/2

return count

Another Way

ALGORITHM BinRec(n)

//Input: A positive decimal integer n

//Output: The number of binary digits in n’s binary representation

if n = 1 return 1

else return BinRec(n/2) + 1

C program:

// Iterative C program to count the number of

// digits in a number in binary form

#include <stdio.h>

int countDigit(long long n)

{

    int count = 0;

    while (n != 0) {

        n = n /2;

        ++count;

    }

    return count;

}

int main(void)

{

    long long n =1024;

    printf("Number of digits : %d",countDigit(n));

   
     return 0;

}

Output:

Number of digits : 11

Read More

MatrixMultiplication Algorithm

ALGORITHM MatrixMultiplication(A[0..n - 1, 0..n - 1], 

B[0..n - 1, 0..n - 1])

//Multiplies two square matrices of order n by the definition-based 

algorithm

//Input: Two n × n matrices A and B

//Output: Matrix C = AB

for i ← 0 to n - 1 do

forj ← 0 to n - 1 do

C[i, j] ← 0.0

for k ← 0 to n - 1 do

C[i, j] ← C[i, j] + A[i, k] ∗ B[k, j]

return C

C program:

#include <stdio.h>

int main()

{

  int m, n, p, q, c, d, k, sum = 0;

  int first[10][10], second[10][10], multiply[10][10];

  printf("Enter number of rows and columns of first matrix\n");  

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

  printf("Enter elements of first matrix\n");

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

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

      scanf("%d", &first[c][d]);

  printf("Enter number of rows and columns of second matrix\n");

  scanf("%d%d", &p, &q);

  if (n != p)

    printf("The matrices can't be multiplied with each other.\n");

  else

  {

    printf("Enter elements of second matrix\n");

    for (c = 0; c < p; c++)

      for (d = 0; d < q; d++)

        scanf("%d", &second[c][d]);

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

      for (d = 0; d < q; d++) {

            multiply[c][d]=0;

        for (k = 0; k < p; k++) {

          multiply[c][d] = multiply[c][d]+ first[c][k]*second[k][d];

        }

    }

    }

    printf("Product of the matrices:\n");

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

      for (d = 0; d < q; d++)

        printf("%d\t", multiply[c][d]);

      printf("\n");

    }

  }

  return 0;

}

Output:

Enter number of rows and columns of first matrix

2

2

Enter elements of first matrix

1

2

3

4

Enter number of rows and columns of second matrix

2

2

Enter elements of second matrix

1

2

3

4

Product of the matrices:

7       10

15      22

Read More