Algorithm of Insertion Sort

Written by Kousik : 

This is another efficient way of solving a problem related with sorting. This algorithm works as the way people play cards. We present our procedure for insertion sort by the name INSERTION. This function takes an array of n element as input which is to be sorted. This algorithm sorts given n elements by inserting them into their right position.

Procedure INSERTION

{

  For i=1 to n-1 do

  Insert(i);

 

}

Insert(i)/* assumes a[0], a[1],…,a[i-1] are sorted*/

{                  /* Insert a[i] in appropriate position so that a[0],a[1],…a[i-1],a[i] become sorted*/

}

Time complexity of this algorithm:

Look carefully in the algorithm you will see that the algorithm works for each element in the array by keeping a particular element into its right position. So the time complexity will be

                                T(n) =

                                     =n(n+1)/2

                                        <=n²/2=O(n²)

So it is efficient algorithm because it takes the polynomial time complexity for executing.

Now we have to write the C code for this algorithm

/* A c program for insertion sort*/

#include<stdio.h>

#include<stdlib.h>

int *a,n;

void insert();

int main()

{

  int i;

  printf("Enter the total number of elements: ");

  scanf("%d",&n);

  a=(int *)calloc(n,sizeof(int));

  printf("Enter the values: ");

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

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

  insert();

  printf("The sorted array: ");

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

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

  return 0; 

}

void insert(void)

{

    int i,j,temp;

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

                {

                  temp=a[i];

                  j=i-1;

                  while((temp<a[j])&&(j>=0))

                  {

                  a[j+1]=a[j];

                  j=j-1;

                  }

                  a[j+1]=temp;

                }

}

Continue

Algorithm of Quicksort

Written by Kousik : 
 QUICKSORT(S)

 {

1.       If ||S||<=1 return;

else {

       2.                Select a first element e as pivot from s.

       3.                 Compare elements of s with e to partition S into subsets S₁, S₂, S₃  such that

                               Elements of S₁ are less than e.

                                Elements of S₂ are equal to e.

                                Elements of S₃ are greater than e.

      4. return (QUICKSORT(S₁), followed by S₂, QUICKSORT(S₃)) ;

}

Implementation of step 2 [Partitioning]

1)      Select the very first element of S as pivot.(Simplest implementation)

2)      Select pivot from S at random.(Randomized implementation)

Analysis of Time complexity of this algorithm:

Let T(n) be the time complexity of this algorithm.

i)                    Worst Case

T(n) = T(0) + T(n-1) + n -1

        = 1+ T(n-1) + n -1

        = T(n-1)+n

        = n(n+1)/2 = O(n²)

This is a polynomial in time complexity. So this is a nice algorithm for solving a sorting problem. But we use this algorithm in a better way such that the time complexity of this algorithm reduced to O(nlogn).

ii)                   Best Case:

<- n/2 elements

->n/2 elements

Time complexity will be

                        T(n)=2T(n/2)+n

                        T(n)=O(nlogn)

iii)                 Average case:

                      [Assumption: all elements of S are equal probable to be the pivot in QUICKSORT(S)]

Let ith smallest element appear as pivot then

T(n)=n -1+T(i-1)+T(n-i)

        =cn+T(i-1)+T(n-i)

Total time require by randomized quick sort algorithm is T(n).

T(n)=(1/n)

Assume T(0)=T(1)=b

Then T(n)=(1/n)

           T(n)=(1/n)

                  = cn+(1/n)

                   = cn+(2/n)

                   = O(nlogn) [ for proof follow this book: Design and analysis of algorithm (aho: hofcroft: ullman)]

Now it is time for writing the average or randomized algorithm for quick sort.

Same procedure will be used in here except the method of pivot element.

QUICKSORT(S)

 {

1.       If ||S||<=1 return;

else {

       2.                select an element e as pivot from s in a random manner.

       3.                 compare elements of s with e to partition S into subsets S₁, S₂, S₃  such that

                               Elements of S₁ are less than e.

                                Elements of S₂ are equal to e.

                                Elements of S₃ are greater than e.

      4. return (QUICKSORT(S₁), followed by S₂, QUICKSORT(S₃)) ;

}

See carefully at the line 2.

Before the pivot was the very first element but now it would be any element of s.

This is the big advantage of randomized quick sort algorithm.

Now we have to write the C code for randomized quick sort algorithm.

/* A program for randomized quick sort*/

#include<stdio.h>

#include<stdlib.h>

int *a,n;

void swap(int *a1,int *a2)/* function for swapping two element*/

{

      int k;

       k=*a1;

      *a1=*a2;

      *a2=k;

}

int partition(int i,int j)/* function for partition the array into three sub arrays*/

{

             int x,p,v;

                x=a[j];

                p=i-1;

                for(v=i;v<=j-1;v++)

                {

                 if(a[v]<=x)

                 {

                  p++;

                  swap(a+p,a+v);

                 }

                }

              swap(&a[p+1],&a[j]);

                return(p+1);

}

int rand_partition(int i,int j)/* function to finding the random number*/

{

     int q;

     q=rand()%(j-i)+i;

     swap(a+q,a+j);

     return partition(i,j);  

}

void quicksort(int i,int j)/* function for main alogorithm QUICKSORT(S)*/

{

     

    int b;

    if(i<j)

    {

       b=rand_partition(i,j);

       quicksort(i,b-1);

       quicksort(b+1,j);

    }

    else

    return;

}

void main()

{

    int i;

    printf("\n Enter the number of elements in the array: ");

    scanf("%d",&n);

    a=(int*)malloc(n*sizeof(int));

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

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

    scanf("%d",a+i);

    printf("\n The array before sorting is: ");

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

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

    quicksort(0,n-1);         

    printf("\n");

    printf("\n The array after sorting is:");

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

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

    printf("\n");

    return;

}
Continued...  

Continue

Sorting

Written by Kousik : 

“Sorting”, this word must come when you are reading C programming language as well as algorithm. This is important part of C programming and very interested problem. Many algorithms for sorting are there. In this section we discuss about several sorting algorithms and their time and space complexity.

Definition:

Input: A sequence of n numbers from linearly ordered set or totally ordered set.

Output: A permutation of the given input sequence such that a[i] <=a[i+1] , where I =1,2,3…,n

Sorting algorithms:

There are many algorithms for sorting. Every algorithm took some time for performing. Different algorithms for same problem would take different complexity.

Problem: Sorting

Name of algorithms	Time complexity	Space Complexity
Insertion sort	O( )	O(n)
Bubble sort	O( )	O(n)
Quick sort	O(nlogn) (In Expected case)	O(n)
Heap sort	O(nlogn)	O(n)
Radix sort or bucket sort	O(n)	O(n)

Now we will analysis about the algorithms shown in above table:

Quick Sort:

This is a way of solving a problem related with sorting. This is a divide-conquer method for sorting. It works by following rule.

1)      Partition the array into two parts.

2)      Sort the two sub array.

3)      Combine the solutions to get the solution for main problem.

Mainly the performance of this method depends upon the position where the partition is to be done. Partition can be done by three following ways.

1)      At first or last position.(Worst case)

2)      At middle position.(Best case)

3)      Randomly choose an element for partition(Randomized quick sort)

We will call the partitioning element by name ‘PIVOT’.

After selecting pivot element we scan the whole array. If we find an element greater than or equal to the pivot element then we keep it at right side of pivot element and otherwise keep it in left side.

By doing this we can claim that the pivot element gets it right position into the array. Then we recursively call the function to right and left side. So, at the end we will get the sorted array.

First we select the middle element as pivot element.

Now it is the time for writing the algorithm.

Method: We use a function named QUICKSORT(S) which works recursively.

Input: Sequence S of n elements a_1, a₂ ...a_n

Output: The elements of S in sorted order.
Continued...  

Continue

C Program for Merge Sort

#include<stdio.h>
#include<stdlib.h>
int *a;
void m_sort(int,int);
void sort(int,int,int);

main()
{
  int n,i;
  printf("Enter the number of elements (it should be power of 2) ");
  scanf("%d",&n);
  a=(int *)calloc(n,sizeof(int));
  printf("Enter the values ");
  for(i=0;i<n;i++)
  scanf("%d",a+i);
  m_sort(0,n-1);
  printf("The sorted array is \n");
  for(i=0;i<n;i++)
  printf("%d ",a[i]);
  return;
}
void m_sort(int i,int j)
{
  int mid;
  if(j-i==0)
  return;
  else
  {
  mid=(i+j)/2;
  m_sort(i,mid);
  m_sort(mid+1,j);
  sort(i,mid,j);
  return;
  }
}
void sort(int i,int mid,int j)
{
  int *b,k,n,m;
  n=i;
  m=mid+1;
  b=(int *)calloc((j+1),sizeof(int));
  for(k=0;k<=j;k++)
  {
  if(n<=mid&&m<=j)
  {
  if(a[n]<a[m])
  b[k]=a[n++];
  else
  b[k]=a[m++];
  }
  else if(n>mid)
  b[k]=a[m++];
  else
  b[k]=a[n++];
  }
  for(k=0;k<=j;k++)
  a[i++]=b[k];
  return;
}

Continue

Example of Quick Sort

Written by Wyes

#include<stdio.h>
#include<stdlib.h>
int *a;
void quicksort(int,int);
int partition(int,int);
void swap_w(int,int);
int random_partition(int,int);
int random_number(int,int);
main()
{
  int i,j,n;
  printf("Enter the number of elements ");
  scanf("%d",&n);
  a=(int *)calloc(n,sizeof(int));
  printf("Enter the elements\n");
  for(i=0;i<n;i++)
  scanf("%d",a+i);
  quicksort(0,n-1);
  printf("The sorted sequence is\n");
  for(i=0;i<n;i++)
  printf("%d ",a[i]);
  printf("\n");
  return;
}
void quicksort(int i,int j)
{
  int k;
  if(j-i<1)
  return;
  else
  {
  k=random_partition(i,j);
  quicksort(i,k-1);
  quicksort(k+1,j);
  return;
  }
}
random_partition(int i,int j)
{
  int k;
  k=random_number(i,j);
  swap_w(k,j);
  return(partition(i,j));
}
int partition(i,j)
{
  int m,n;
  m=i-1;
  for(n=i;n<j;n++)
  {
    if(a[n]<=a[j])
{
m++;
swap_w(m,n);
}
  }
  swap_w(m+1,j);
  return(m+1);
}
int random_number(int i,int j)
{
  return((rand()%(j-i))+i);
}
void swap_w(int i,int j)
{
  int temp;
  temp=a[i];
  a[i]=a[j];
  a[j]=temp;
  return;
}

Continue

Example of bubble sort

Written by Kousik

/* c program for bubble sort*/
#include<stdio.h>
int a[20];
void bubble(int n)
{
   int t, i,j;
   for(j=n-1;j>0;j++)
   {
    for(i=0;i<j;i++)
{
if(a[i+1]>a[i])
{
 t=a[i];
 a[i]=a[i+1];
 a[i+1]=t;
}
}
   }
}
int main()
{
  int n,i;
  printf("Enter the total number of elements: ");
  scanf("%d",&n);
  printf("Enter the values: ");
  for(i=0;i<n;i++)
  scanf("%d",&a[i]);
  bubble(n);
  printf("The sorted sequence: ");
  for(i=0;i<n;i++)
  printf(" %d",a[i]);
  return 0;
} 

Continue

CONSTANTS,VARIABLES & KEYWORDS IN C

Written by Kousik : 
Every programming language has a grammar. Different programming language has different grammar. So to learn C programming language we have to be familiar with that grammar which is related to C program. The grammar is nothing but CONSTANTS, VARIABLES, & their DATA TYPES.

CONSTANTS:

There are two types of C constants. One is PRIMARY and other is SECONDARY.

Primary constants are of three types.

1)      Integer Constant

2)      Real Constant

3)      Character Constant

Secondary constants are of several types.

1)      Array

2)      Pointer

3)      Structure

4)      Union

5)      Enum etc…

Now we have to primary constants first…

Integer Constants:

Characteristics: a) An integer constants must have at least one digit. It must not have a decimal point.

                                b) It can either positive or negative. If no sign proceeds then the integer assumed to be positive.

                                c) The range for integer constants is -2147483648 to +2147483647. The range of integer constants is depend upon the compiler (visual studio, gcc  , turbo c etc).

Example : 400, -421,+755 etc

Real Constants (Floating Point Constants) :

Real constants can be shown in two forms. One is fractional form and other is exponential form.

Characteristics   of Fractional form  :

a)      A real constants must have at least one digit . It must have a decimal point.

b)      It can be either positive or negative. If no sign proceeds then the integer assumed to be positive.

c)       No blanks are allowed within a real constant.

Example  : -69.35 , 12.00 , +39.355 etc

In exponential form the real is represented in two major parts  . The part coming before ‘e’ is called ‘mantissa’ and the part coming after ‘e’ called ‘exponent’ .

Characteristics of exponential form:

a)      The word ‘e’ separate the exponential part and the mantissa part of real constants.

b)      The mantissa part may have +ve or –ve sign. . If no sign proceeds then the integer assumed to be positive.

c)       The exponent must have at least one digit.

d)      Range = -3.4e38 to +3.4e38

Example: 3.2e-23, -0.45e+33 etc

Character Constants:

Characteristics: 

a)      A character constant can be a single alphabet, single digit or a single special symbol enclosed with single inverted commas.

b)      The maximum length of a character constant is 1 character.

Example: ‘A’, ‘c’, ‘5’, ‘/’ etc

*Secondary constants will be discussed later.

VARIABLE:

To store the data value in computer memory we have to know about VARIABLES.  Variables names are names given to location in memory. These locations can contain Integer, real, character constants .Type of variables are depending upon the type of constants. For example an integer type of variable can holds only the integer constants. The variable name is chosen by the programmer in such a way that shows its nature in the program.

Example:  class, roll, count etc

Characteristics of variables:

a)      They must begin with a letter.

b)      A variable name is any combination of 1 to 31 alphabets, digits or underscores. The length of variables is depending upon the compiler.

c)       No special symbol other than an underscore can be used in a variable name.

d)      Uppercase and lowercase are very significant.

C KEYWORDS:

C compiler has some words whose meaning has already been explained. There are 32 keywords available in C. Different keywords have different meaning.

auto                       double                     int                                        struct  Break                     else                        long                                      switch  case                       enum                      register                                typedef  char                       extern                     return                                  union  const                     float                        short                                 unsigned  continue                 for                            signed                                  void  default                  goto                         sizeof                                   volatile  do                          if                           static                                    while

To know more about c keywords you can follow LET UC C(by yashvant kanetkar) & ANSI C (by Balaguruswamy) .

                `              

Continue

Divide and Conquer : Explained with Example

Written by Saikat :

DIVIDE AND CONQUER ALGORITHM:

The most commonly used & convenient algorithm is the 'Divide & conquer' algorithm. If a problem is tough to solve, then we can assume that this problem is made up by some small problems. Then we can break the main problem in some small sub-problems. Now we can easily solve the sub-problems. By this we can solve the whole problem very easily. This method is called Divide and Conquer method. By this method we can also develop efficient programs to solve a particular problem. 

STEPS INVOLVED IN THIS ALGORITHM: 

1) Divide the total problem into several sub problems of equal length.

2) Obtain the solution of the individual sub problems.

3) Combine the solutions to get the main solution.

ASPECT:

The basic aspect of this algorithm is to minimize the time complexity of a given problem as much as possible. There may be various types of algorithms to solve a particular problem. Among   those we shall choose that one, which will take a polynomial order of time complexity, i.e. we will have to choose in such a way that it requires a least number of operations. It will be better if it takes time complexity of linear order.

EXAMPLE:

           Take the example of the finding out the maximum and minimum from a set of integers. If we look the overall problem then we will face some challenges. So, just forget the whole problem. Now if there are two numbers then we can easily find out which is smaller and which is bigger by following algorithm.

If(a>b)  then  MAX <- a and MIN <- b

Else MAX <- b and MIN <- a

This is an easy problem to solve. So, we assume this problem as a unit problem and break the whole problem into sub problems.

Now look at the program and find out what we are doing in it.

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

int *a;

typedef struct list
{
  int min,max;
}ln;

ln minmax(int,int);
int min(int,int);
int max(int,int);

main()
{
  int i,n;
  ln ext;
  printf("Enter the number of element ");
  scanf("%d",&n);
  a=(int *)calloc(n,sizeof(int));
  printf("Enter the numbers ");
  for(i=0;i<n;i++)
  scanf("%d",(a+i));
  ext=minmax(0,n-1);
  printf("The minmum value is %d and the maximum value is %d",ext.min,ext.max);
  return;
}

ln minmax(int n1,int n2)
{
  ln ext,ext1,ext2;
  if(n2-n1==1)
  {
    ext.min=min(a[n1],a[n2]);
ext.max=max(a[n1],a[n2]);
return ext;
  }
  else
  {
  ext1=minmax(n1,(n1+n2)/2);
  ext2=minmax((n1+n2)/2+1,n2);
  ext.min=min(ext1.min,ext2.min);
  ext.max=max(ext1.max,ext2.max);
  return ext;
  }
}

int max(int a, int b)
{
  if(a>b)
  return a;
  else
  return b;
}

int min(int a, int b)
{
  if(a<b)
  return a;
  else
  return b;
}

Continue

Age Calculator Program

Posted by Kousik

This is a program to calculate your age.

/*AGE CALCULATE*/

#include<stdio.h>

int main()

{

int dd,dm,dy,cd,cm,cy,d,m,y;

printf(“Enter your DATE OF BIRTH in dd mm yyyy format\n”);

scanf(“%d %d %d”,&dd,&dm,&dy);

printf(“Enter Current Date in dd mm yyyy format\n”);

scanf(“%d %d %d”,&cd,&cm,&cy);

y=cy-dy;

if(dm>cm)

{

y--;

m=12-(dm-cm);

if(dd>cd)

{

m--;

d=30-(dd-cd);

}

else

{

d=cd-dd;

}

}

else

{

m=cm-dm;

if(dd>cd)

{

m--;

d=30-(dd-cd);

}

else

{

d=cd-dd;

}

printf(“You AGE is \n”);

printf(“%d days %d months %d years\n”,d,m,y);

}

Continue

C program to turn binary number to decimal and decimal number to binary

This is a program to convert binary to decimal

/* author- WYES KARNY */
#include<stdio.h>
int main()
{
  int a,rem,des=0,i=1;
printf("Enter a binary number ");
scanf("%d",&a);
while(1)
{
rem=a%10;
a=a/10;
des+=rem*i;
i=i*2;
if(a==0)
break;
}
printf("\nThe equevalent desimal value is %d \n",des);
return 0;
}

And for the Decimal to binary

#include<stdio.h>
int main()
{
int a,i,shift,bit;
scanf("%d",&a);
for(i=0;i<16;i++)
{
shift=a<<i;
shift=shift>>15;
bit=shift&1;
if(bit==1)
printf("1");
else
printf("0");
}
}

Continue

Implement linked list

Linked List is collection of data which is linked together in a specific way.
It is very efficient for computer memory. It consumes memory usage and save memory spaces.
It works as Dynamic Allocation System (DMA).
First we have to know -

1. What is Linked List?
2. Why we use Linked List?
3. How do we implement Linked list?

We will find answers for all of these questions.
I have given some introduction of linked list above but did not define yet.
Linked List is a list consisting element of structure type, which contains the data and link to the next element.
The picture can clear your confusion.

Here every block represents an element of the linked list. Every block contains two sub-blocks.

One block is for the data, saved in the element and other for the link to the next element.

Next question is, why we use it. Let us consider an example, in a school, there is a class consisting 50 students. If we save their marks in an array according to their roll numbers, then we have to declare an array of 50 elements. If we do this then when a new student gets admission, we have no space for the new student.

If we declare an array of 100 elements at first then it would be possible but it wastes a huge memory space.

Therefore in this case we can use Linked List.

Next, implementation of linked list, 

Here is a program to implement linked list.

#include<stdio.h>

#include<stdlib.h>

typedef struct link_list

{

  int number;

  struct link_list *next;

}l;

void create(l *list);

void print_list(l* list);

main()

{

  l *head;

  head=(l*)malloc(sizeof(l));

  create(head);

  print_list(head);

}

void create(l *list)

{

  char c;

  printf("Enter the number\n");

  scanf("%d",&list->number);

  printf("continue...  ");

  getchar();

  c=getchar();

  if(c=='y')

  {

  list->next=(l*)malloc(sizeof(l));

  create(list->next);

  }

  else

  list->next=NULL;

}

void print_list(l* list)

{

  if(list->next!=NULL)

  {

  printf("%d  ",list->number);

  print_list(list->next);

  }

  else

  printf("%d\n",list->number);

}

(If you have any question, feel free to ask me)

  

Continue