Breadth First Search in Graphs

http://install4install.com

Breadth First Search is a technique to visit all the nodes of graph in a well-defined way.This technique can be applied  to  directed,undirected,weighted or unweighted  graph.Queues are used as a data structure to store elements.

  • BFS traverses all the nodes and edges of graph.
  • BFS in graph with m vertices and n edges takes O(n+m) time.

Example

Say we have a graph as shown in  Fig 1

Screen Shot 2014-07-15 at 5.09.35 PM

Fig 1 : A Graph

 

  • Start from any vertex say A.(Fig 2)
  • Visit and mark A.
  • Look for neighbors of A.
  • Result list –> A
  • Find all the vertices connected to A.E,B,D are connected to A .
  • Pick any random neighbor of A.Say B.
Screen Shot 2014-07-16 at 1.26.21 PM

Fig 2 : Mark A

1

Fig 2 : Mark B

 

  • Visit B and mark it.(Fig 2)
  • Add B to the queue.
  • Result –> AB
  • Look for next vertex which is connected to A.
  • Say  D is chosen.
  • Result –>ABD
  • Visit D and mark it.(Fig 3)
  • Add D to the queue.
Screen Shot 2014-07-15 at 5.27.56 PM

Fig 3 : Mark D

  • Look for any another vertex connected  to A.
  • E is connected to A.(Fig 4)
  • Visit E and mark it.
  • Result –>ABDE
  • Add E to the queue.
  • Screen Shot 2014-07-15 at 5.30.31 PM

    Fig 4 : Mark E

  • Look for any other vertex connected to A.
  • No other vertex is connected to A.
  • Now,dequeue B.
  • Screen Shot 2014-07-15 at 5.35.13 PM
  •  Find neighbor vertices  connected to B.
  • Visit C and mark it.(Fig 5)
  • Result –> ABDEC
  • Add C to the queue.
Screen Shot 2014-07-15 at 5.39.08 PM

Fig 5 : Mark C

  • Look for next unvisited element connected to B.
  • No other unvisited element is connected to B.
  • Dequeue D.
  • Screen Shot 2014-07-15 at 5.42.49 PM
  • Look for another unvisited vertices connected to D.
  • No other unvisited vertex is connected to D.
  • Dequeue E.
  • Screen Shot 2014-07-15 at 5.44.40 PM
  • Look for unvisited neighbors of E.
  • Visit F and mark it.(Fig 6)
  • Result –> ABDECF
  • Add F to the queue.
Screen Shot 2014-07-15 at 6.07.19 PM

Fig 6 : Mark F

 

  • Look for another vertex connected to E.
  • G is connected to E.
  • Visit G and mark it.(Fig 7)
  • Result –> ABDECFG
  • Add G to the queue.
Screen Shot 2014-07-15 at 6.08.57 PM

Fig 8 : Mark G

 

  • There are no unvisited neighbors of C,F, and G.
  • Dequeue C,F and G one by one.

Short URL: http://tinyit.cc/c27b00
By Cusp2207 on July 16, 2014 | Computer Science | A comment?
Tags:

Strings

String is a collection of characters that forms a word.It is stored in one dimensional array and terminated by null(\0) character.The size of array is one more than the length of string as it required to store null character.The compiler itself places a null character at the end of array during its initialization

Syntax

char array_name[array_size] = {‘character 1′,’character 2′,…….,’\0′};

or

char array_name[] = ‘string_name';

Example

#include <stdio.h>
int main() 
{
char website[12]= {'L','e','t','s','l','e','a','r','n','C','S','\0'};//or char website[]="LetslearnCS";
printf("Name of the website is:\t");
printf("%s",website);
return 0;
}

Run

 

 Memory Representation of String

The memory representation of a string is given in Fig 1.The addresses of character is assumed for

Screen Shot 2014-07-11 at 12.31.36 PM

Fig 1 : Representation of a String in memory

 

String Functions

There are various predefined  functions in C that are used to perform various operations on strings.In order to use these function a header file string.h must be included in the program.The function definitions are placed in this file.We just call these functions through function call statements.

  • strlen()
  • strcpy()
  • strcat()
  • strcmp()
  • strsstr()
  • strchr()

strlen()

This function finds the length of string and gives answer in numeric form.

Syntax

strlen(string_name);

Example

#include <stdio.h>
#include<string.h>//header file for string functions

int main()
{
	char website_name[] ="LetsLearnCS";//string initialization
	int len;//len is of int type to store length of string
	len = strlen(website_name);//function call
	printf("The length of string is %d",len);
	return 0;
}

 

Run

TipIf a space is given in between the string,then that is also counted in length by strlen function.

 

strcpy()

strcpy function copies the content of one string into another string.

Syntax

strcpy(string_1,string_2);

It copies the content of string 2 into string 1.

Example

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

int main() 
{
char string1[] = "Two-Dimensional";
char string2[] = "Arrays";
printf("String 1 before strcpy() function :%s\n",string1);
printf("String 2 before strcpy() function: %s\n\n",string2);
strcpy(string1,string2);
printf("String 1 after strcpy() function: %s\n",string1);
printf("String 2 after strcpy()function: %s\n",string2);
return 0;
}

Run

 

 

strcat()

This function concatenates/combines two strings.

Syntax

strcat(string1,string2);

string2 is combined to end of string1.The second string remains as it is.

Example

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

int main() 
{
char string1[] = "Two-Dimensional";
char string2[] = "Arrays";
printf("String 1 before strcat() function :%s\n",string1);
printf("String 2 before strcat() function: %s\n\n",string2);
strcat(string1,string2);
printf("String 1 after strcat() function: %s\n",string1);
printf("String 2 after strcat()function: %s\n",string2);
return 0;
}

Run

 

strcmp()

This function returns 0 if string 1 and string 2 are same and 1 if they are not same.If the first or few initial characters of both the strings are same then it returns -1.

Syntax

strcmp(string1,string2)

Example

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

int main() 
{
char string1[] = "Arrays";
char string2[] = "Arrays";
int val;
val= strcmp(string1,string2);
printf("%d",val);
return 0;
}

Run

 

 


Short URL: http://tinyit.cc/8f4440
By Cusp2207 on July 11, 2014 | Computer Science | A comment?
Tags:

Loop Control Statements

Loop Control Statements alter  execution of a program from the normal execution sequence.The statements are as follows

  • break
  • continue
  • goto

break statement

break statement terminates the execution of loop immediately ineffective of the condition status.The control is transferred to the first statement after the loop block.If break statement is used in nested loops      (Refer : Nesting of Loops) then innermost loop is terminated and control is transferred to outer loop.

Syntax

break;

Program 1

#include <stdio.h>

int main() 
{
	int i;
	for(i=1;i<20;i=i+2)
	{
		if(i>15)
		{
		break;
		}
	printf("%d\n",i);
	}
	return 0;
}

Run

 

Program 2

#include <stdio.h>

int main() 
{
int i;
while(i<=15)
{
if(i%2 == 0)
{
	printf("%d\n",i);
}
i++;
if(i>10)
{
	break;
}

}
	return 0;
}

Run

continue statement

continue statement forces to execute( instead of termination)the next iteration and skips some statements.

Syntax

continue;

Program 3

#include <stdio.h>

int main()
{
	int i;

	for(i=0;i<10;i++)
	{
		if(i >5)
		{
		continue;
		i=i+5;
		printf("%d\n",i);
		}
		printf("%d\n",i);
		}
	return 0;
}

Run

goto statement

goto statement jumps the control to a desired labelled statement of a program.The use of goto is generally avoided as it leads to difficult understanding of the control flow.

Syntax

goto label;

…..

….

label:statement;

 

Program 4

#include <stdio.h>
 
int main ()
{
   int i,j;
   int num;
   //printf("Enter the no");
   scanf("%d",&num);
   for(i=0;i<10;i++)
   {
   	if(num>5)
   	{
   		num = num +2;
   		printf("%d\n",num);
   	}
   	else
   	{
   		goto LOOP;
   	}
   }
   LOOP:for(i=0;i<10;i++)//LOOP is a label
   {
   	num=num+3;
   	printf("%d\n",num);
   }
   return 0;
}

Run


Short URL: http://tinyit.cc/d42290
By Cusp2207 on July 10, 2014 | Computer Science | 2 comments
Tags:

Nesting of loops

Loops can be nested if required.Nesting means to have one or more loops inside the main loop.

Syntax of nested for loops

for(initialization;condition;iteration)

{

for(……)

{

for(…)

{…

}

…….

}

}

Syntax of nested while loops

while(condition)

{

…..

while(condition)

{

……..

}

….

}

Syntax of nested do-while loop

do

{

statements;

do

{

statements;

}

while(condition);

}

while(condition);

Example 1

Say we want to print a pattern like

#
# #
# # #
# # # #
# # # # #

Program 1

 

#include <stdio.h>

int main() 
{
int i,j;
for(i=0;i<5;i++)
{
	for(j=0;j<=i;j++)
	{
		printf("*");
	}
	printf("\n");
}
	return 0;
}

Run

Illustration 

The working of Program 1 is explained in Fig 1.

 

Screen Shot 2014-07-08 at 6.06.39 PM

Fig 1 : Working of Program 1

 

Example 2

Say we want to print table of numbers from 5 t0 10.If we need to print a table of single number then single loop can be used.In order to print table of different numbers in a single go,we need nested loop.

 

Program 2

#include <stdio.h>

int main()
{
	
	int i,j;
	int res;
	
	for(i=5;i<=10;i++)
	{
		printf("\n");
		for(j=1;j<=10;j++)
		{
			res = i*j;
			printf("%d * %d = %d",i,j,res);
			printf("\n");
		
		}
		
	}
	return 0;
}

Run


Short URL: http://tinyit.cc/00849b
By Cusp2207 on July 9, 2014 | Computer Science | A comment?
Tags:

do-while loop

The functionality of do-while is slightly different from while and for loop.The condition of do-while is at the bottom of loop and it executes at least once even if the condition is false.The initialization of a variable loop is done before the loop block.

Syntax

do

{

set_of_statements;

}

while(condition);

 

Example 1

Say we need to print  numbers from 0 to 100.

Program 1

#include <stdio.h>

int main()
{
int i = 0;
do
{
	printf("%d\t",i);
	i++;
}
while(i<=100);
	return 0;
}

 

Run

 

Example 2

Say we want to print a table of a user entered number.

Program 2

#include <stdio.h>

int main() 
{
	int num,i=1;
	int tab;
	//printf("Enter the number");
	scanf("%d",&num);
	do
	{
		
		tab = num * i;
		printf("%d * %d = %d\n",num,i,tab);
		i++;
		
		
	}
	while(i<=10);

	return 0;
}

Run

 

Example 3

Say we want to print even numbers and odd numbers from 0-100  separately .

Program 3

#include <stdio.h>

int main()
{
int i=0;
int j=1;
printf("The even mumbers are :\n");
do
{
	printf("%d\t",i);
	i=i+2;
}
while(i<=100);
printf("\nThe odd numbers are :\n");
do
{
	printf("%d\t",j);
	j=j+2;
}
while(j<100);
return 0;
}

 

Run

 

Example 4

Say we want to print series like 30,27,24,21,18,15,12,9,3.

Program 4

#include <stdio.h>

int main() 
{
int i=30;
do
{
	printf("%d\t",i);
	i=i-3;
	
}
while(i>=3);
	return 0;
}

 

Run

 


Short URL: http://tinyit.cc/ec0f9d
By Cusp2207 on July 8, 2014 | Computer Science | A comment?
Tags:

while loop

While loop keeps on executing the given statements as long as the condition is true.When the condition  turns out to be false then set of statements in the block never gets executed and the control goes to first line after the while block.

Syntax

while(condition)

{

set_of_statements;

iteration statement;

}

If the condition is true,then set of statements are executed.The value of i is iterated and then control again returns to while condition.If condition is true again then same process is followed otherwise control exits the loop.

 

Example 1

Say we need to print  numbers from 0 to 100.while loop can also be used instead of for loop to fulfill this task.

Program 1

#include <stdio.h>

int main() 
{
int i=0;
while(i<=100)
{
	printf("%d \t",i);
	i++;
}
	return 0;
}

 

Run

 

 

Example 2

Say we want to print a table of a user entered number.

Program 2

#include <stdio.h>

int main()
{
int n,i=1;
int res;
//printf("Enter the number");
scanf("%d",&n);
while(i<=10)
{
	res = n * i;
	printf("%d * %d = %d\n",n,i,res);
	i++;
}
	return 0;
}

 

Run

 

Example 3

Say we want to print even numbers and odd numbers from 0-100  separately .

Program 3

#include <stdio.h>

int main() 
{
int i=0;
int j=1;
printf("The even numbers are:\n");
while(i<=100)
{
	printf("%d\t",i);
	i=i+2;
}
printf("\nThe odd numbers are :\n");
while(j<100)
{
	printf("%d\t",j);
	j=j+2;
}
	return 0;
}

 

 

Run

 

Example 4

Say we want to print series like  15625,3125,625,125,25,5.

Program 4

#include <stdio.h>

int main() 
{
int i=15625;
while(i>=5)
{
	printf("%d\t",i);
	i=i/5;
}
	return 0;
}

 

Run

 

 

Illustration 

The working of program 4 is explained in Fig 1.

Screen Shot 2014-07-08 at 11.09.51 AM

Fig 1 : Working of Program 4


Short URL: http://tinyit.cc/8489e9

for loop

Loops are control structures that are used to execute a code several times.There may be situation when we need to print series from 1-100 or we need to print our name 1000 times on screen.It will be inappropriate to use 100 or thousand  times printf for this scenario.Loops can be used to efficiently perform the task as many times as required.There are 3 types of loops used in C language.They are:

  • for loop
  • while
  • do-while

for loop

for loop is a control structure which has  initialization statement,condition  and iteration statement.

Syntax

for(initialization,condition,iteration)

{

body_of_loop

}

  • In initialization,variable is initialized i.e variable is assigned some value.Declaration can also be done in this step.
  • If the condition is true,body of the loop is executed otherwise flow of control jumps to next lines of code after the ending of loop.After this,control jumps back to increment statement.
  • The incrementation/ decrementation  is done and condition is checked again.If it is true then control goes to body of loop and executes it.
  • The same process happens again and again until the condition becomes false.
  • When the condition becomes false control exits the for loop.

Example 1

Say we need to print  numbers from 0 to 100.For loop can be used to fulfill this task.

Program 1

#include <stdio.h>

int main() 
{
int i;
printf("Numbers are ");
for(i=0;i<=100;i++)
{
	printf("%d\t",i);
}
	return 0;
}

Run

 

Illustration

The working of program 1 is explained in Fig 1.

Screen Shot 2014-07-02 at 4.25.26 PM

Fig 1 : Working of Program 1

 

Example 2

Say we want to print a table of a user entered number.

 

Program 2

#include <stdio.h>

int main() 
{
int n;
int i;
int t;
//printf("Enter the number");
scanf("%d",&n);
printf("The table of %d is:\n ",n);
for(i=1;i<=10;i++)
{
	t=n*i;
	printf("%d * %d = %d\n",n,i,t);
}

	return 0;
}

Run

 

Example 3

Say we want to print even numbers and odd numbers from 0-100  separately .

 

Program 3

 

#include <stdio.h>

int main() 
{
	int i,j;
	printf("The even numbers are:\n");
	for(i=0;i<=100;i=i+2)
	{
		printf("%d\t",i);
	}
	printf("\nThe odd numbers are:\n");
	for(j=1;j<100;j=j+2)
	{
		printf("%d\t",j);
	}
	return 0;
}

Run

 

Example  4

Say we want to print series like  64,32,16,8,4,2,1

Program 4

#include <stdio.h>

int main() 
{
	int i;
	for(i=64;i>0;i=i/2)
	{
		printf("%d\t",i);
	}

	return 0;
}

Run

 


Short URL: http://tinyit.cc/24ddd
By Cusp2207 on July 3, 2014 | Computer Science | A comment?
Tags:

Decision Making Statements

Decision Making Statements are the statements that imposes one or more conditions on the expression and if the conditions evaluates to be true then specific actions are followed,if not true then some other actions are followed.They are called as decision making as it leads to a particular conclusion/decision.In C,true values are treated as non-zero i.e.1 and false values are treated as 0.The various types of decision making statements are :

  • if statement
  • if-else statement
  • nested if statement
  • switch

if statement

The if statement consists of boolean expression followed by group of statements.If the expression evaluates to be true then block of code inside if is executed otherwise nothing happens.

Syntax

if(boolean_expression)

{

//lines_of_code ;

}

Example

Say we need to find whether a child is eligible for admission in school on basis of age.If his age is greater than/equal to 5 but less than 6 then he is eligible for admission otherwise not.To specify this in C programming language we can use if statement.

Program

#include <stdio.h>

int main() 
{
int age;
//printf("Enter the age of child");
scanf("%d",&age);
if((age>=5) && (age < 6))
{
printf("Chid is eligible for admission");
}
return 0;
}

Run

 

if-else statement

In if-else statement if the condition in if part evaluates to be true then code of lines in if block is executed otherwise code of lines in else part gets executed.

Syntax

if(boolean_expression)

{

code 1;

}

else

{

code 2;

}

Example

Say we need to find larger of two numbers and print the same.The bigger no. can be found out by using if-else statement.

Program

#include <stdio.h>

int main() 
{
	int a;
	int b;
	//printf("Enter two numbers :");
 	scanf("%d",&a);
 	scanf("%d",&b);
	if(a > b)
	{
		printf("%d is bigger",a);
	}
	else
	{
		printf("%d is bigger",b);
	}
	return 0;
}

Run

 

Nested if statement

In nested if statement,one or more if statements are inside another if statement.

Syntax

if(boolean_expression_1)

{

 if(expression 2)

{

lines_of_code

}

if(expression 3)

{..}

}

Program

#include <stdio.h>

int main()
{
int marks;
//printf("Enter the marks of child");
scanf("%d",&marks);
if((marks >=50) && (marks <=100))
{
	if((marks >=50) && (marks <=60))
	{
	printf("Child needs improvement");
	}
	if((marks >60) && (marks <=70))
	{
		printf("Child can do better");
	}
	if((marks >70) && (marks <=80))
	{
		printf("Good Attempt");
	}
	if((marks >80) && (marks <=100))
	{
		printf("Excellent");	
	}

}
else
{
	printf("Failed");
}
	return 0;
}

Run

 

switch statement

The functionality of switch statement is same as of if-else statement.It uses cases for different conditions and code of lines are executed according to the case (whichever is true).Each case has a break statement so that control gets transferred (if case is valid)to out of switch block and other false cases are not executed.It has a default case where code of lines are executed if none of the cases satisfy the mentioned conditions.The expression of switch is the variable on which conditions are based.Constant expressions of cases must match the data type of expression mentioned in switch.

Syntax

switch(expression)

{

case constant-expression 1:

set of statements;

break;

case constant-expression 2:

set of statements;

break;

..

default:

statements;

….

}

Example

#include <stdio.h>

int main() 
{
	char alphabet;
	//printf("Enter the alphabet:");
	scanf("%c",&alphabet);
	switch(alphabet)
	{
		case 'a':
		case 'A':
		printf("%c is a vowel",alphabet);
		break;
			
		case 'e':
		case 'E':
			printf("%c is a vowel",alphabet);
		break;
			
		case 'i':
		case 'I':
			printf("%c is a vowel",alphabet);
		break;
		
		case 'o':
		case 'O':
			printf("%c is a vowel",alphabet);
		break;
		
		case 'u':
		case 'U':
			printf("%c is a vowel",alphabet);
		break;
		default:
		printf("%c is not a vowel",alphabet);
		
	}

	return 0;
}

Run

 


Short URL: http://tinyit.cc/298821

Functions

A function is a group of statements that performs some specific task.They can be used in other programs depending on their accessibility and are ended by brackets.In order to define a function inside  a program we need to specify three things:

  • Function Declaration
  • Function Definition
  • Function Calling

Some functions are pre-defined like main(),printf(),scanf().We just need to call these type of functions in our program as their definition and declaration are  already stored in other files.The purpose of main() is to start the execution of program.

Function Declaration

Functions are declared at the top of program in which function call has been placed.It is required to be declared when we define a function in one program and call it another program.It  includes return type,function name and parameters.It tells the compiler how to call the function.

Syntax

return_type function_name(parameter 1, parameter 2,parameter 3,….parameter n);

return_type function_name();

  • return_type is the data type of function.It can be void,int,float or char.
  • function_name is the name of function.
  • parameters are the arguments passed to the function.Parameter has return type and parameter name.Return type is compulsory to mention whereas parameter name is optional in this function declaration.

Example

float area_circle(int r)

or

float area_circle(int)

Function Definition

Function definition defines the task/purpose of the function.The purpose is defined in the body of function.

Syntax

return_type function_name(parameters)

{

body_of_function

}

  •  return_type is the data type of function
  •  function_name is the name of function.
  • parameters are the arguments passed to the function.They are optional   in definition.
  • body_of_function defines the purpose/task of function.

Example

float area_circle(int r)
{
float area;
area =3.14 *r*r;
return area;
}

Function Calling

To use a function and return results function calling is used.When the control in program reaches the function calling,it gets transferred to function definition and the required task is performed.When return statement or function ending close brace is encountered control gets transferred back to the main program.To call a function simply function name along with arguments is required.The arguments are passed in function calling according to the declaration/definition.There is no need to mention return_type in function calling.

Syntax

function_name(arguments);

 Example

area_circle(5);

Program 1

#include <stdio.h>

float area_circle(int r);//Function Declaration
int main() //main function
{
	float result;
	result = area_circle(5);//Function calling
	printf("Area of circle is %f",result);
	return 0;
}
float area_circle(int r)//Function Definition
{
	float area;
	area = 3.14 *r *r;
	return area;
}

Run

 

Program 2

#include <stdio.h>
int largest(int,int,int);
int main() 
{
int big;// int p=2,q=1,r=7;
big = largest(2,1,7);//largest = (p,q,r);
printf("The largest no is %d",big);
return 0;
}
int largest(int a,int b,int c)
{
if((a>b) && (a>c))
	{
	return a;
	}
else if((b>a && b>c))
	{
   return b;
	}
else
	{
	return c;
	}

}
	
	

Run

 

 

Program 3

#include <stdio.h>

float area_rectangle(float,float);
float area_triangle(float,float);
float area_square(float);
int main()
{
	float res1,res2,res3;
	res1 = area_rectangle(3.5,6);
	res2 = area_triangle(4.5,7);
	res3 = area_square(3);
	printf("The area of rectangle is %f\n",res1);
	printf("The area of triangle is %f\n",res2);
	printf("The area of square is %f\n",res3);
	return 0;
}
float area_rectangle(float length,float breadth)//Function definition
{
	float area;
	area = length * breadth;
	return area;
}
float area_triangle(float base,float height)
{
 float area; area = 0.5 * base * height; 
 return area; 
}

 float area_square(float side)
 {
 float area; 
 area = side * side; 
 return area; 
}

Run

 

 


Short URL: http://tinyit.cc/8e898

Merge Sort

Merge sort is the divide and conquer method to arrange elements in the order.The steps followed in merge sort are :

  • Divide the sequence of n elements into two sub-sequences of n/2 elements each.
  • Sort the sub-sequences using merge sort.If the size of sequence is 1,nothing more can be done.
  • Merge the sub-sequences to form a sorted sequence of elements.

The complexity of merge sort is O(n log n).It runs faster than insertion and bubble sort but requires large amount of memory.

 

Program

#include<stdio.h>
void merge(int [],int ,int ,int );
void partition(int [],int ,int );
int main()
{
 int a[20];
 int i,size;
 printf("Unsorted List:\t");
 //printf("Enter total no. of elements : ");
 scanf("%d",&size);
 for(i=0; i<size; i++)
 {
   scanf("%d",&a[i]);
   printf("%d\t",a[i]);
 }
 printf("\n");
 partition(a,0,size-1);
 printf("Sorted List  :\t");
 for(i=0; i<size; i++)
 printf("%d \t",a[i]);
 return 0;
}
void partition(int a[],int min,int max)
{
 int mid;
 if(min<max)
 {
   mid=(min+max)/2;
   partition(a,min,mid);
   partition(a,mid+1,max);
   merge(a,min,mid,max);
 }
}
void merge(int a[],int min,int mid,int max)
{
  int temp[20];
  int i,j,k,m; 
  j=min;
  m=mid+1;
  for(i=min; j<=mid && m<=max ; i++)
  {
     if(a[j]<=a[m])
     {
        temp[i]=a[j];
      	j++;
     }
     else
     {
         temp[i]=a[m];
         m++;
     }
  }
  if(j>mid)
  {
     for(k=m; k<=max; k++)
     {
         temp[i]=a[k];
         i++;
     }
  }
  else
  {
     for(k=j; k<=mid; k++)
     {
        temp[i]=a[k];
        i++;
     }
  }
  for(k=min; k<=max; k++)
     a[k]=temp[k];
}

Run

 

Example

Consider a sequence 7,44,2,10,1,35,74,88,5,3,15.We need to sort this  using merge sort.The list contains 11 elements(Fig 1).Divide the list such that first sub-list has 6 elements and second sub-list has 5 elements(vice-versa is also possible).Keep on dividing till we get single elements in the last.After dividing merge all the elements step by step as shown in Fig 2.

Screen Shot 2014-06-26 at 1.53.09 PM

Fig 1 : Dividing

 

Screen Shot 2014-06-26 at 1.57.46 PM

Fig 2 : Merging

 


Short URL: http://tinyit.cc/d2ed
By Cusp2207 on June 26, 2014 | Computer Science | A comment?
Tags:

Algorithms
Computer Science
Data Structures