Sorting a linked list of employees into alphabetical order using the code below?

How do you sort a linked list of employees into alphabetical order by surname using the code below?

The code below is an example of a linked list taken from
http://www.eca.com.ve/cs/Study%20Notes/linked_lists.htm
Escuela Campo Alegre, Shashi Krishna, HS Computer Science

# include<iostream.h>
# include<stdlib.h>
# include<conio.h>
# include<string.h>


struct ListEntry
{
int roll;
char first_name[10],last_name[10];
int age,join_dt,join_month;
char sex;
float pay;
struct ListEntry *next;
}start,*node,*prev;

/******************FUNCTION PROTOTYPES******************************/
void add();
void append();
void view();
void del();
void modify();
void viewdb();
void view_emp_size();
void query();
int droll;
int roll_count;
/********************MAIN FUNCTION***********************************/

void main()
{
int choice;


system("cls");
cout<<"\t\t========================\n\n";
cout<<"\t\tS.K. DATABASE SOLUTIONS\n";
cout<<"\t\t========================\n\n";
cout<<"Choose operation from menu below:\n\n";
cout<<"[1] Insert a record\n";
cout<<"[2] Append a record\n";
cout<<"[3] View a record\n";
cout<<"[4] View the database\n";
cout<<"[5] Modify a record(Only pay is modified)\n";
cout<<"[6] Delete a record\n";
cout<<"[7] View Number of Employees\n";
cout<<"[8] Query\n";
cout<<"[9] Exit\n";
cout<<"\t\tEnter ur choice:";
cin>>choice;


switch(choice)
{
case 1:
add();
break;
case 2:
append();
break;
case 3:
view();
break;
case 4:
viewdb();
break;
case 5:
modify();
break;
case 6:
del();
break;
case 7:
view_emp_size();
break;
case 8:
query();
break;
case 9:
cout<<"\t\tExiting SK DB SOLUTIONS...\n\n";
exit(1);


}
}

/************************************************** *******************/


void add()
{
char choice;
start.next=NULL; //Empty List
node=&start; //Point to the start of the list
roll_count=1001;
do
{

system("cls");
cout<<"\t\t\t==============================\n\n";
cout<<"\t\t\t SK DATABASE SOLUTIONS\n";
cout<<"\t\t\t EMPLOYEE ENTRY SHEET\n\n";
cout<<"\t\t\t==============================\n\n";
node->next=(struct ListEntry*)malloc(sizeof(struct ListEntry));
node=node->next;
node->roll=roll_count;
cout<<"[Mode:Insert]\n\n";
cout<<"ID\t\t\t"<<node->roll<<endl;
cout<<"First Name\t\t";
cin>>node->first_name;
cout<<"Last Name\t\t";
cin>>node->last_name;
cout<<"Age\t\t\t";
cin>>node->age;
cout<<"Gender\t\t\t";
cin>>node->sex;
cout<<"Join Day(number)\t";
cin>>node->join_dt;
cout<<"Join Month(number)\t";
cin>>node->join_month;
cout<<"Pay(in USD)\t\t";
cin>>node->pay;
++roll_count;
cout<<"Record saved. Input another?\n";
cin>>choice;
node->next=NULL;
}while(choice=='Y'||choice=='y');
main();
}

/************************************************** ******************/
//Displaying the list
void viewdb()
{

node=start.next;
system("cls");
cout<<"\t\t\t==============================\n\n";
cout<<"\t\t\t SK DATABASE SOLUTIONS\n\n";
cout<<"\t\t\t==============================\n\n";
cout<<"ID\tNAME\t\tJOIN DATE\tPAY(in $)\n\n";
cout<<"=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n";
while(node)
{
cout<<node->roll<<"\t"<<node->last_name<<", "<<node->first_name<<"\t"<<node->join_dt<<"-"<<node->join_month<<"-2000\t"<<node->pay<<endl;
node=node->next;
}
cout<<endl;
getch();
main();
}

/************************************************** ******************/

//Viewing a record from the list
void view()
{
int flag=0;
node=start.next;
prev=&start;
cout<<"Enter the roll you want to view details of:";
cin>>droll;
cout<<"Searching..."<<droll<<endl<<endl;
getch();
while(node)
{
if(node->roll==droll)
{
flag=1;
system("cls");
cout<<"\tSEARCH RESULTS\n\n";
cout<<"ID\t\t\t"<<node->roll<<endl;
cout<<"Name\t\t\t"<<node->last_name<<","<<node->first_name<<endl;
cout<<"Age\t\t\t"<<node->age<<endl;
cout<<"Gender\t\t\t"<<node->sex<<endl;
cout<<"Joined on\t\t"<<node->join_dt<<"-"<<node->join_month<<"-2000"<<endl;
cout<<"Pay\t\t\t"<<node->pay<<"\n";
cout<<"=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-"<<endl;
break;
}
else
{
node=node->next;
prev=prev->next;
flag=0;
}
}
if(flag==0)
{
cout<<"Search retreived 0 records."<<endl;
getch();
}
main();
}

/************************************************** ******************/

void del()
{
int id,flag=0;
node=start.next;
prev=&start;
cout<<"Enter the ID to be deleted:\n";
cin>>id;


while(node)
{
if(node->roll==id)
{
prev->next=node->next;
free(node);
flag=1;
cout<<"Record Index #"<<id<<" deleted."<<endl;
getch();
break;
}
else
{
node=node->next;
prev=prev->next;
flag=0;
}
}
if(flag==0)
{
cout<<"Search retreived 0 records."<<endl;
getch();
}
main();
}

/************************************************** ******************/

void view_emp_size()
{
int size=1;
node=start.next;
while(node->next!=NULL)
{
++size;
node=node->next;
}

cout<<"\n\n\n\n\n\t"<<size<<" employee(s) work in SK DB SOLUTIONS currently"<<endl;
getch();
main();
}






/************************************************** ******************/


void modify()
{
int idtomodify;
int flag=0;
float newpay;

cout<<"NOTE: Only pay is modifiable field!\n\n";
cout<<"Enter Employee ID:";
cin>>idtomodify;

node=start.next;

while(node)
{
if(node->roll==idtomodify)
{
flag=1;
break;
}
else
{
flag=0;
break;
}
}


if(flag==1)
{
cout<<"Old Pay for "<<node->first_name<<" was $"<<node->pay<<endl;
cout<<"Enter new pay(in USD) ";
cin>>newpay;
node->pay=newpay;
cout<<"\n\nRecord modified and updated successfully!"<<endl;
getch();
viewdb();
}
if(flag==0)
{
cout<<"\t\tSearch retreived 0 records\n"<<endl;
getch();
main();
}
}
/************************************************** ******************/

void append()
{
system("cls");
node=&start;

getch();
while(node->next)
{
node=node->next;

if(node->next==NULL)
{
node->next=(struct ListEntry*)malloc(sizeof(struct ListEntry));
node=node->next;
node->roll=roll_count;
cout<<"[Mode:Append]\n\n";
cout<<"ID\t\t\t"<<node->roll<<endl;
cout<<"First Name:\t\t";
cin>>node->first_name;
cout<<"Last Name:\t\t";
cin>>node->last_name;
cout<<"Age\t\t\t";
cin>>node->age;
cout<<"Gender\t\t\t";
cin>>node->sex;
cout<<"Join Day(Number)\t";
cin>>node->join_dt;
cout<<"Join Month(Number)\t";
cin>>node->join_month;
cout<<"Pay(in USD)\t\t";
cin>>node->pay;
node->next=NULL;
}
}
++roll_count;
main();
}
/************************************************** ******************/

void query()
{
int choice,match=0,month,mcount=0,fcount=0;
char lname[10];

node=start.next;
prev=&start;

system("cls");
cout<<"What would u like to query upon?(Enter 0 to go back)\n";
cout<<"[1] Employee Name\n";
cout<<"[2] Date of Joining\n";
cout<<"[3] Gender\n";
cout<<"I will query on Option:";
cin>>choice;

switch(choice)
{
case 1:
cout<<"Enter LAST NAME of employee for search criteria:";
cin>>lname;
cout<<"ID\tNAME\t\tJOIN DATE\tPAY(in $)\n\n";
cout<<"=-=-=-=-=-=--=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n";

while(node)
{
if(strcmp(node->last_name,lname)==0)
{
++match;
cout<<node->roll<<"\t"<<node->last_name<<","<<node->first_name<<"\t"<<node->join_dt<<"-"<<node->join_month<<"-2000\t"<<node->pay<<"\n";
}
node=node->next;
}
cout<<"\n\n\n\t\t"<<match<<" record(s) match search criteria"<<endl;
getch();
break;



case 2:
cout<<"Enter month of search criteria:";
cin>>month;
while(node)
{
if(node->join_month==month)
{
++match;
cout<<node->roll<<"\t"<<node->last_name<<","<<node->first_name<<"\t"<<node->join_dt<<"-"<<node->join_month<<"-2000\t"<<node->pay<<"\n";
}
node=node->next;
}
cout<<match<<" record(s) match search criteria"<<endl;
getch();
break;


case 3:
while(node)
{
if(node->sex=='M'||node->sex=='m')
++mcount;
else
++fcount;

node=node->next;
}

cout<<"\n\n\t\tSK DB SOLUTIONS has the following employee ratio\n\n";
cout<<"\t\tMale: "<<mcount<<"\n\n";
cout<<"\t\tFemale: "<<fcount<<endl;
getch();
break;

case 0:
main();
break;


default:
cout<<"See the message!";
break;
}

getch();
query();

}

If you want them sorted then it'd probably be better to store them in a binary tree rather than a linked list. Or at least an array so you can call qsort on the structure. A linked list (even doubly) is generally fairly bad for sorting.

-KM-