MSN Messengar: Quickening@live.com

Sunday, March 16, 2008

Simple C Programming: Alternative to Merge Sort By Using Insertion Sort

Note: Purely informative; just in case this might come up in your exams or something. Sometime ago, I was asked by the lecturer to write and compile a simple C-program.

The backbone of the labtest was to re-create the structure of the Merge Sort, but it was so bloody difficult coding that, with me running out of time, I exploited a loophole in the question.

It didn’t specifically said Merge Sort. I instead used an more extensively memorized Insertion Sort... with extra coding. *hehehe!*

Question: Write a c program to merge two ordered lists of numbers and store the result in a third list.

Answer:

---START---

#include
#include
#define MAX 6
#define MAXTWO 12

//Three lists (listOne, listTwo and listMerge)
//Insertion Sort function
//Merge Sort function


void insertion (int list[],int size);
void merge (int list01[],int list02[],int list03[],int size);

void main()
{
int listOne[MAX];
int listTwo[MAX];
int listMerge[MAXTWO];
int i, j=MAX, size=MAX;

printf("Enter 6 set of numbers for the First List: \n");
for(i=0; i{

scanf("%d", &listOne[i]); //Enter for listOne

}
insertion (listOne, size); //Insertion Sort for listOne
printf("\n\n");

printf("Enter 6 set of numbers for the Second List: \n");
for(i=0; i{
scanf("%d", &listTwo[i]); //Enter for listTwo
}
insertion (listTwo, size); //Insertion Sort for listTwo
printf("\n\n");

for(i=0; i{
printf("%d ", listOne[i]); //Display ordered listOne
}
printf("\n");

for(i=0; i{
printf("%d ", listTwo[i]); //Display ordered listTwo
}
printf("\n\n");

size=MAXTWO; //change size from MAX to MAXTWO

for(i=0; i//Merging listOne and listTwo into listMerge
{
listMerge[i]=listOne[i];
listMerge[j]=listTwo[i];
j++;
}
insertion (listMerge, size); //Insertion Sort for ListMerge

printf("Merged list: ");
for(i=0; i{
printf("%d ", listMerge[i]); //Display ordered listMerge
}
printf("\n\n");
}

void insertion (int list[], int size) //Insertion Sort function
{
int a, b, tmp;

for(a=0; a{
tmp = list[a];
for(b = a-1; b >= 0 && tmp < list[b]; b--)
list[b+1]=list[b];
list[b+1]=tmp;
}
}

void merge (int list01[],int list02[],int list03[],int size) //Merge Sort function
{
int a=0, b=0, c;
//int a = listOne counter
//int b = listTwo counter
//int c = listMerge counter

for(c=0; c{
if(list01[a]{
if(a==6)
{
list03[c]=list01[a];
}
else
{
list03[c]=list01[a];
a++;
}
}
else
{
if(b==6)
{
list03[c]=list02[b];
}
else
{
list03[c]=list02[b];
b++;
}
}
}
}
//Weakness: There maybe some repeating values.

---END---


Output Screenshot *click to see*


It was only after I got passed my semester that somebody finally posted the C-programming codes to Merge Sort on Wikipedia. I’ve already passed and moved on to Java (my lecturer, a good sport she was, complimented me on ingenuity, but she still could only give me an A- score for that).

Maybe someday when C-programming becomes compulsory as a primary school subject, I can tell my little grandchildren how to take advantage of exam question loopholes.

Source: Insertion Sort, Merge Sort

4 Minds bloomed here too...:

Anonymous said...

Greetings girls. I am only I start to study c programs
c programming.
I have visited a site http://program.v3host.be/?cat=204.
Much to our regret I have very little found out about it.
You can probably tell to me a good site about arrays c program.
I will be very glad.
Thansk

Anonymous said...

Hi guys. I am only I start to study c program string.
I have visited a site http://program.v3host.be/?cat=204.
Much to our regret I have very little found out about it.
You can probably tell to me a good site about c program array.
I will be very glad.
Thansk

Anonymous said...

Genial post and this mail helped me alot in my college assignement. Say thank you you on your information.

Anonymous said...

Opulently I assent to but I dream the list inform should secure more info then it has.

More Weeds...

Add to Technorati Favorites Blogroll.net Bloggapedia, Blog Directory - Find It! Blog Flux Directory blog directory Blog Directory & Search engine Show off your blog Blogarama - The Blog Directory BlogGod Webloogle Blog Directory Blogging Fusion Blog Directory All Malaysian Bloggers Project