Hello, I wrote two programs which sort first names which are already sorted by their last names.One is with Selection sort and the other is with Quicksort!

The question is , "is any one of them stable?."

"If the names with same first names are still in sorted order by their last names, we call that sort a stable sort"

I got in-stable results for both the sorts by the programs i wrote.Am I correct?
Or is any thing wrong with my codes?
I'm a newbie please help me somebody...
Quicksort

//by ABVK
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int quick(char fname[][10],char lname[][10],int left,int right){
	if(left<right){
		int newpivi;
		newpivi=partition(fname,lname,left,right);
											//positioning pivot in its correct position.......
		quick(fname,lname,left,newpivi-1);					//left part of the pivot element....
		quick(fname,lname,newpivi+1,right);					//right part of the pivot element.....
		}
}
int partition(char fname[][10],char lname[][10],int left,int right){			//partition function for positioning pivot
		int k=left,i=left+1,j=right;						//left most element is selected as pivot
		char temp1[50],temp2[50];
		char pivot1[50],pivot2[50];
		strcpy(pivot1,fname[left]);
		strcpy(pivot2,lname[left]);
		do {
		while(strcasecmp(fname[k],fname[i])>=0)
				i++;
		while(strcasecmp(fname[k],fname[j])<0)
				j--;
		if(i<j){
			strcpy(temp1,fname[i]);
			strcpy(temp2,lname[i]);
			strcpy(fname[i],fname[j]);
			strcpy(lname[i],lname[j]);
			strcpy(fname[j],temp1);
			strcpy(lname[j],temp2);
			}
		}while(j>i);
		strcpy(temp1,fname[j]);
		strcpy(temp2,lname[j]);
		strcpy(fname[j],fname[k]);
		strcpy(lname[j],pivot2);
		strcpy(fname[k],temp1);
		strcpy(lname[left],temp2);
		return j;
}
main(){
	int i,j,key;
	printf("These names are already sorted by lastname:\n");
	char fname[8][10]={"Phil","Jane","Fred","Bill","Jane","Mary","Fred","Jane"},
     	     lname[8][10]={"Doe","Doe","Doe","Jones","Jones","Smith","Smith","Smith"};
	for(i=0;i<8;i++)
		printf("%s %s\n",fname[i],lname[i]);
	quick(fname,lname,0,7);						
	printf("After applying QUICK SORT ALGORITHM:\n");
	for(i=0;i<8;i++)
		printf("%s %s\n",fname[i],lname[i]);
	printf("Hence, quicksort is not a stable sorting Algorithm:::\n");
}

Selection sort

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
main(){
	int n,p,i,j,k;
	char a[8][10]={"Phil","Jane","Fred","Bill","Jane","Mary","Fred","Jane"},
	b[8][10]={"Doe","Doe","Doe","Jones","Jones","Smith","Smith","Smith"};
	printf("These names are already sorted by lastname:\n");
	char temp1[100],temp2[100];
	for(i=0;i<8;i++)
		printf("%s %s\n",a[i],b[i]);					//if first gre...returns pos else returns 
											
	printf("The names after applying selection sort on First names:\n");
	for(i=0;i<7;i++){
		for(j=i+1;j<8;j++){
			if(strcasecmp(a[i],a[j])>0){
				strcpy(temp1,a[i]);
				strcpy(temp2,b[i]);
				strcpy(a[i],a[j]);
				strcpy(b[i],b[j]);
				strcpy(a[j],temp1);
				strcpy(b[j],temp2);
			}
		}
		
		
	}
	for(i=0;i<8;i++)
		printf("%s %s\n",a[i],b[i]);
	printf("Hence, Selection is not a stable sorting Algorithm\n");
}

Thanks in advance!

It doesn't look like you are considering the last name when sorting. If the names are already sorted by last name you should only be sorting the first names where the last names match.
For example if you have the names Phil Doe, Jane Doe, Fred Doe, Bill Doe, Jane Jones and Mary Jones, you shouldn't be comparing Phil with Mary to order them as the last names don't match.

It doesn't look like you are considering the last name when sorting. If the names are already sorted by last name you should only be sorting the first names where the last names match.
For example if you have the names Phil Doe, Jane Doe, Fred Doe, Bill Doe, Jane Jones and Mary Jones, you shouldn't be comparing Phil with Mary to order them as the last names don't match.

Actually the concerned question is to determine whether the quick sort and selection sort algorithms are stable for these type of problems.
Actually the given input consists of names which are already sorted by their last name....
Now I have to sort all strings by their first names (when moving a first name, we should also move its corresponding last name) and should check for its stability.That's what the question!.
There is no condition that I should only check names which have the same last name.....
Thank you!

Edited 4 Years Ago by challarao: added a sentence

I'm not sure I understand...

your first post seem to say
1) You want to make sure your sorts are stable.
2) You run both sorts on data and find out they are stable.
3) The code works for your test so far.
So what is your question?

Try more tests. Bigger tests. That's how we all discover if the programs work properly.

I'm not sure I understand...

your first post seem to say
1) You want to make sure your sorts are stable.
2) You run both sorts on data and find out they are stable.
3) The code works for your test so far.
So what is your question?

Try more tests. Bigger tests. That's how we all discover if the programs work properly.

My programs are running fine..But I don't know whether quicksort and selections sort are stable sorting algorithm.....If I know will conclude that my programs are correct.
This is actual question....
Q)Suppose you have a list of names. You could sort the list into alphabetical order either by first name or by last name. Suppose that the list is already sorted by last name. For example:

Phil Doe

Jane Doe

Fred Doe

Bill Jones

Jane Jones

Mary Smith

Fred Smith

Jane Smith

Now, suppose that you take this list and sort it into alphabetical order by first name. In the new list, Jane Doe, Jane Jones, and Jane Smith will be grouped together. The question is, will they be in that order. That is, will people with the same first name still be in alphabetical order by last name? For some algorithms, the answer is yes. Other algorithms, however, can mess up the relative order of a group of people with the same first name. A sorting algorithm that will always preserve the order of people with the same first name is said to be stable. Is Selection Sort a stable algorithm? Why or why not? How about quick Sort? Why or why not?
Thank you.

Edited 4 Years Ago by challarao: n/a

My programs are running fine..But I don't know whether quicksort and selections sort are stable sorting algorithm.....If I know will conclude that my programs are correct.

So how do you find out whether they are stable? As I said before

Try more tests. Bigger tests. That's how we all discover if the programs work properly.

And in this case, since your programs are running fine, that's how we tell if the sorts are stable.

This article has been dead for over six months. Start a new discussion instead.