EQuestionAnswers.com Notes, Syllabus, Questions, Ideas,
Books, Reference materials on Electronics
#Login #Sign up #Forum #Feedback
 

#Previous question #Index of C Questions #Next question

This type of sorting follows the divide and rule policy. This algorithm divides the array of n elements into n separate arrays of size 1 (each array contains one element) and then rejoins the divided arrays one by one with each other to form the array of size n.

To explain this sorting technique we take an array ar[] containing s elements.

Two variables “upper” and “lower” stores the upper limit (position of last element, generally s-1) and the lower limit (position of first element, generally 0) of the array respectively. The middle position of the array is obtained by adding upper and lower and dividing the result by 2.

The obtained position is used to divide the array into two sub arrays. The procedure is followed repeatedly on the sub arrays and the subsequent sub arrays until upper equals lower (this happens when each sub array contains one element each, i.e. when the array has been divided into s sub arrays).

This process can be better explained with an example:

Let an array ar[] contain the following elements:

34 45 89 23 38 76 12 28

The length of the array is 8, so s=8. Thus lower=0 (since position of elements in array starts from 0) and upper=s-1=7.

Thus the array will be split from the middle, i.e. (0+7)/2=3 (element at 4th position). The array becomes:

[34 45 89 23] [38 76 12 28]  ([] represents a sub array)

Now each sub array will be considered an individual array and the procedure will be applied to each sub array again.

The left sub array has four elements and so, lower=0 and upper=3. Thus middle point occurs at 1 (position of second element)

The right sub array also has four elements and so, lower=4 and upper=7. Thus the middle point occurs at 5 (position of 6th element)

Thus the sub arrays get divided and the result becomes:

[34 45] [89 23] [38 76] [12 28]

This process is repeated till all sub arrays contain 1 element each.

[34] [45] [89] [23] [38] [76] [12] [28] 

The s divided arrays are joined together to form the complete array and the elements are sorted at the same time. This is done by sorting the elements of two arrays while joining them in a third array.

This process can be better explained with an example:

Let us take the divided array shown above:

[34] [45] [89] [23] [38] [76] [12] [28] ([] indicate a separate array)

The combining procedure takes place as follows:

The single array obtained at the end is the sorted array.

The mergesort algorithm generally contains two distinct methods:

mergesort(ar[],lower,upper):This method shares its name with the sorting technique and is generally used to split the array of n elements into n sub arrays each containing 1 element. This is done by using a recursive function for most convenience.

An algorithm for the method is as follows:

mergesort(ar[],lower, upper)
/* this method takes three arguments: the array pointer ar[],
   the lower limit of the array(the position of the first element)
   and the upper limit of the array (the position of the last element) */

	int mid; //stores the position of middle element

	if(upper>lower)
	{

		mid=(lower+upper)/2; //calculates middle position

		mergesort(ar,lower,mid); // recursively splits the left subarray
		mergesort(ar,mid+1,upper); // recursively splits the right subarray

		merge(ar,lower,mid,mid+1,upper);// merges the separated arrays

	}

merge(ar[],lower,mid,mid+1,upper):This method joins the two separated arrays into a temporary array before transferring the elements to the original array. The method also sorts the array while joining them.

Let us consider an array ar[] with s elements. Let us also consider that the array has been split into two sub arrays at the middle position.

The array ar[] has been sent to the merge() method along with the position of the first element and the position of the last element of both the sub arrays. Two variables p and q(initialized to the position of the first element of first sub array and second sub array respectively) are used to point to the elements in the arrays.

Now the elements in the two sub arrays are put into a third temporary array D[] in the following manner:

  • The element at p and q are compared.
  • If element at p matches the condition, the element is put into D and p is incremented by 1.
  • If element at q matches the condition, the element is put into D and q is incremented by 1.
  • This is continued till either p or q reaches the last element in its array.
  • If p reaches its end, the remaining elements in the array pointed by q is put in D[] or vice versa.

(The condition refers to elements being greater or lesser than each other.)

After all the elements in the sub arrays have been sorted in D[], the elements are put back into the sub arrays in the order it is present in D[].

Let us take an example to better understand this method:

Let an array ar[] have 8 elements:

23 34 45 89 12 28 38 76

Let it be split up into two sub arrays:

Left sub array: [23 34 45 89]
Right sub array: [12 28 38 76]

p will point to the beginning of left sub array while q will point to the beginning of the second sub array.

The elements will be stored in D[] in the following manner:(considering ar[p]

 P			     q				D
[23	34	45	89] [12	   28	  38	76]*	[]

 P			     	   q			D
[23	34	45	89] [12	   28	  38	76]	[12]

 P			     	   q			D
[23	34	45	89] [12	   28	  38	76]*	[12]

 	P			   q			D
[23	34	45	89] [12	   28	  38	76]	[12 23]

        P			   q			D
[23	34	45	89] [12	   28	  38	76]*	[12 23]

 	P			      	  q		D
[23	34	45	89] [12	   28	  38	76]	[12 23 28]

	P			     	  q		D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28]

 		P			  q		D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34]

		P			  q		D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34]

 		P			      	q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38]

		P			     	q	D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34 38]

 			P			q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38 45]

			P			q	D
[23	34	45	89] [12	   28	  38	76]*	[12 23 28 34 38 45]

 			P			q	D
[23	34	45	89] [12	   28	  38	76]	[12 23 28 34 38 45 76]

* indicates elements being pointed by p and q are being compared

Since q reaches limit, the remaining element of p is transferred to D[]. Thus the elements of D[] are:

[12 23 28 34 38 45 76 89]

These elements are put into the sub arrays in the order it is present in D[].

An algorithm for this method is as follows:

merge(ar[], lower1, upper1, lower2, upper2)
/*the arguments include: the array pointer ar[],
the position of first element of the left sub array, 
the position of last element of the left sub array,
the position of first element of the right sub array, 
the position of last element of the right sub array */

	
int p,q,n,j,D[100];

	p=lower1;
	q=lower2;

	n=0; // position counter for D[]

	while((p<=upper1)&&(q<=upper2))
	
		/* conditionally placing elements in D[] */
		D[n++]=(ar[p]<ar[q]?ar[p++]:ar[q++]); 
	
	while(p<=upper1)
		// placing remaining elements of sub array pointed by p in D[]
		D[n++]=ar[p++]; 
	
	while(q<=upper2)
		// placing remaining elements of sub array pointed by p in D[]
		D[n++]=ar[q++]; 

	
	n=0;
	for(p=lower1;p<=upper1;p++,n++)
		// placing elements from D[] to left sub array 
		ar[p]=D[n]; 
	
	for(q=lower2,j=n;q<=upper2;q++,j++)
		// placing elements from D[] to right sub array
		ar[q]=D[j]; 
	

Mergesort may be done using array or linked list. Fully working codes of mergesort using array and linked list has been given below. The programs have been written in C.

Mergesort using array:

#include<stdio.h>
#include<conio.h>
void merge(int ar[],int lower1,int upper1,int lower2,int upper2)
{
	int p,q,n,j,D[100];
	p=lower1;
	q=lower2;
	n=0;
	while((p<=upper1)&&(q<=upper2))
	{
		D[n++]=(ar[p]<ar[q]?ar[p++]:ar[q++]);
	}
	while(p<=upper1)
	{
		D[n++]=ar[p++];
	}
	while(q<=upper2)
	{
		D[n++]=ar[q++];
	}
	n=0;
	for(p=lower1;p<=upper1;p++,n++)
	{
		ar[p]=D[n];
	}
	for(q=lower2,j=n;q<=upper2;q++,j++)
	{
		ar[q]=D[j];
	}
}
void mergesort(int ar[],int lower,int upper)
{
	int mid;
	if(upper>lower)
	{
		mid=(lower+upper)/2;
		mergesort(ar,lower,mid);
		mergesort(ar,mid+1,upper);
		merge(ar,lower,mid,mid+1,upper);
	}
}
void main()
{
	clrscr();
	int ar[100],s,i,lower,upper;
	printf("\nEnter the size of the array: ");
	scanf("%d",&s);
	printf("\nEnter the elements of the array:");
	for(i=0;i<s;i++)
	{
		scanf("%d",&ar[i]);
	}
	lower=0;
	upper=s-1;
	mergesort(ar,lower,upper);
	printf("\nThe sorted array is:");
	for(i=0;i<s;i++)
	{
		printf("\n%d",ar[i]);
	}

	getch();
}

Mergesort using linked list:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include<stdlib.h>
struct link
{
	int data;
	struct link *next;
};
struct link *getnode()
{
	struct link *n;
	n=(struct link *)malloc(sizeof(struct link));
	return n;
}
int getans()
{
	int i;
	printf("\n Press 1 to continue and 0 to quit");
	scanf("%d",&i);
	return i;
}
void putdata(struct link *n)
{
	printf("\n Enter the value:");
	scanf("%d",&(n->data));
	n->next=NULL;
}
void display(struct link *n)
{
	while(n!=NULL)
	{
		printf("\n %d",n->data);
		n=n->next;
	}

}
struct link *merge(struct link *head_one,struct link *head_two)
{
	struct link *head_three;
	if(head_one == NULL)
	{
		return head_two;
	}
	if(head_two == NULL)
	{
		return head_one;
	}
	if((head_one->data) < (head_two->data))
	{
		head_three=head_one;
		head_three->next=merge(head_one->next,head_two);
	}
	else
	{
		head_three=head_two;
		head_three->next=merge(head_one,head_two->next);
	}
	return head_three;
}
struct link *mergesort(struct link *head)
{
	struct link *head_one;
	struct link *head_two;
	if((head==NULL)||(head->next == NULL))
	{
		return head;
	}
	head_one=head;
	head_two=head->next;
	while((head_two != NULL) && (head_two->next != NULL))
	{
		head=head->next;
		head_two=(head->next)->next;
	}
	head_two=head->next;
	head->next=NULL;
	return merge(mergesort(head_one),mergesort(head_two));
}
void main()
{
	clrscr();
	struct link *head,*node;
	head=getnode();
	putdata(head);
	node=head;
	while(getans())
	{
		node->next=getnode();
		node=node->next;
		putdata(node);
	}
	display(head);
	node = mergesort(head);
	printf("\nThe sorted list is:");
	display(node);
	getch();
}

You have viewed 1 page out of 204. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

structured programming language, first C program, header files, library, compilation, pre-processing, compilation, optimization, linking format, debugging with GDB, data types, storage classes, if, if-else, if-else-if, label and goto, switch case, loop statements, break and continue, pointers, enum type, macro, basic operators, logical operators, logical vs bitwise operators, bit shifting, bit set, reset/clear, toggle, Operator precedence, array, multidimensional arrays, 2D and 3D dynamic array, add Matrix, multiply Matrix, adjacency Matrix, Circuler buffer, user defined types, typedef, struct type, union type, struct vs union, struct pack padding, bit fields, obtain bit mask, reverse bits, swap bits, structure as function argument, array as function argument, printing pointers, scanf string input, scan string with blanks, scanf string ends with newline, return of scanf, return of printf, scanf with printf, print using fprintf, take input using fscanf, floating point formatting, multiple arguments in printf and scanf, variadic functions, variadic macro, calling conventions, calling convention of C,C++ and PASCAL, operator precedence, ternary operator, switch statement, continue in switch and loops, for, while, do-while loop syntax, for to while, do-while and while usage, infinite loops, function declaration and definition, library function linking, call-by-value and call-by-reference, parameter passing call-by-value, parameter passing call-by-reference, address of local and dynamic variable, volatile variable, external vs static, global vs static variable, register vs auto variable, const, macro vs constant, debug builds, debug macros, compiler macro for C++, FILE, LINE, DATE, TIME, compiler marcos, token pasting, characterizing, const char *,char * const, const char * const, char array and char pointers, enum vs macro, macro vs typedef, size of a structure, upper and lower 16bit of 32bit unsigned, near, far and huge pointer, typed pointers and void pointer, sizeof void, sizeof void and void pointer, operators for void pointer, l-value, struct and array, NULL pointer, inline-functions, macro vs inline-function, malloc vs calloc, function pointer, compare with ==, argc and argv, C startup routine, strcpy and strcat source, memcpy vs memmove, strrev source, strdup, strtok, palindrome, reverse decimal digits, signed and unsigned compare, string vs integer pointer, xor operator, bitwise shifting, logical and bitwise or, macro definition, long pointer increment, default C++ argument value, short pointer increment, short pointer increment, execution sequence, exceptions, setjump and longjump, trace a memory leak, detect memory corruption, Big Endian and Little Endian, stack grows up or down, prime number, HCF, LCM, star triangle, Exchange variables, C and Data Structures, Data Structures using array, Linked List, Single Linked list, Doubly Linked list, Circular Linked list, Doubly Circular Linked list, Queue, reverse single linked list, delete single linked list, Stack, Tree and Binary tree, Binary tree, traverse Binary tree, Binary search tree, double Binary tree, mirror Binary tree, height of Binary tree, heap, Complexity, Linear Search, Binary Search, Hash Table, Sorting, Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort, Merge sort, Radix Sort, Recursion, factorial using recursion, Fibonaci using recursion, amrongstrong number, argv environ, system(), atexit, raise signal, abort exit, Libraries, static linking, dynamic linking methods, implicit dynamic linking, explicit dynamic linking, access C from VB, access C from Java, sleep/delay, sound, nosound, alpha numeric, convert case, string to int, int to string, fprintf, fscanf working principal, palindrome digits, arithmeic math, trigonometric, fopen, fdopen, write vs append mode, binary vs text mode, binary mode, fseek, fprintf, fscanf, fflush, ioctl, mmap, fcntl, poll, select, poll, select, fputs,fgets,fgetc,fputc, printf, scanf, DOS graphics, compilers, Turbo C, GCC, VC++,

# C/C++ Interview questions and answers - Shetty's World
# C Interview Questions and Answers - C Interview FAQs & C Books
# C interview questions and answers | TechInterviews
# C Interview Questions and Answers :: ALL Interview .com
# C Interview Questions and Answers

* #1 webmaster Sun 02 Feb/2014 03:09:23(GMT)  Like 0 Unlike 0

Dear Users,

We are pleased to inform you that a forum/blog has been incorporated with www.mybestnotes.co.in. You are welcomed to add your comments, requests, codes, solutions and feedback to it. Please login(if already a member) or signup(for free) to avail to this facility.

Regards,
Webmaster

Your message goes here:

Name:Guest
Email:anonymous@unknown.com
My Post:*
Secutiry Code: ******  *
Preview this compose before posting this in discussion forum.
 
Note:
  1. Use [Sxx] code to show smiles. Example [S02]
  2. Use [URL ], example [URL http://www.google.com/]
  3. To display code or un formatted text use [CODE] [/CODE]. Example: [CODE] printf("Hello world"); [/CODE]
 [S01]   [S02]   [S03]   [S04]   [S05]   [S06]   [S07]   [S08] 
 [S09]   [S10]   [S11]   [S12]   [S13]   [S14]   [S15]   [S16] 
 [S17]   [S18]   [S19]   [S20]   [S21]   [S22]   [S23]   [S24] 

Note: Only members are allowed, * fields are mandatory.