Sorting a Linked List

Suppose, we wish to sort the elements of a linked list. We can use any of the standard sorting algorithms for carrying out the sorting. While performing the sorting, when it is time to exchange two elements, we can adopt any of the following two strategies:

1. Exchange the data part of two nodes, keeping the links intact.

2. Keep the data in the nodes intact. Simply readjust the links such that effectively the order of the nodes changes.

Of the two methods suggested above, the first one is easier to implement, but the second one is likely to be more efficient. This is because if the data part contains an employee record (containing name, age, salary etc.) then to carry out exchange of this record would be inefficient time wise as well as space wise. In this case, to perform one exchange of records, we need to copy the entire record thrice using the following statements:

struct emp
{

char name ;

int age ;

float salary ;

} temp ;

struct empl
{

char name ;

int age ;

float salary ;

struct empl *link ;

} *p, *q ;

strcpy ( temp.name, p -> name ) ;
strcpy ( p -> name, q -> name ) ;
strcpy ( q -> name, temp.name )

temp.age = p -> age ;
p -> age = q -> age ;
q -> age = temp.age ;

temp.sal = p -> sal ;
p -> sal = q -> sal ;
q -> sal = temp.sal ;

Thus a great deal of time would be lost in swapping the records.
Instead if we adopt second method, since we are readjusting only the links this would involve only pointers and not the bulky structures representing records. This limitation can be overcome if we readjust links instead of exchanging data. This has been achieved through the following program.

#include "alloc.h"
struct node
{

int data ;

struct node *link ;

} *start, *visit ;

main( )
{

getdata( ) ;

clrscr( ) ;

printf ( "\nLinked List Before Sorting:\n" ) ;

displaylist( ) ;

selection_sort( ) ;

printf ( "\nLinked List After Selection Sorting:\n" ) ;

displaylist( ) ;

getch( ) ;

getdata( ) ;

clrscr( ) ;

printf ( "\nLinked List Before Sorting:\n" ) ;

displaylist( ) ;

bubble_sort( ) ;

printf ( "\nLinked List After Bubble Sorting:\n" ) ;

displaylist( ) ;

getch( ) ;

}

getdata( )
{

int val, n ;

char ch ;

struct node *newnode;

clrscr( ) ;
newnode = NULL ;

do

{

printf ( "\nEnter a value: " ) ;

scanf ( "%d", &val ) ;

append ( &newnode, val ) ;

printf ( "\nAny More Nodes (Y/N): " ) ;

ch = getche( ) ;

} while ( ch == 'y' || ch == 'Y' ) ;

start = newnode ;

}

/* adds a node at the end of a linked list */
append ( struct node **q, int num )
{

struct node *temp ; temp = *q ;

if ( *q == NULL ) /* if the list is empty, create first node */

{

*q = malloc ( sizeof ( struct node ) ) ;

temp = *q ;

}

else

{

/* go to last node */

while ( temp -> link != NULL )

temp = temp -> link ;

/* add node at the end */

temp -> link = malloc ( sizeof ( struct node ) ) ;

temp = temp -> link ;

}

/* assign data to the last node */

temp -> data = num ;

temp -> link = NULL ;

}

/* displays the contents of the linked list */
displaylist( )

{

visit = start ;

/* traverse the entire linked list */

while ( visit != NULL )

{

printf ( "%d ", visit -> data ) ;

visit = visit -> link ;

}

}

selection_sort( )

{

struct node *p, *q, *r, *s, *temp ;

p = r = start ;

while ( p -> link != NULL )

{

s = q = p -> link ;

while ( q != NULL )

{

if ( p -> data > q -> data )

{

if ( p -> link == q ) /* Adjacent Nodes */

{

if ( p == start )

{

p -> link = q -> link ;

q -> link = p ;

temp = p ;

p = q ;

q = temp ;

start = p ;

r = p ;

s = q ;

q = q -> link ;

}

else

{

p -> link = q -> link ;

q -> link = p ;

r -> link = q ;

temp = p ;

p = q ;

q = temp ;

s = q ;

q = q -> link ;

}

}

else

{

if ( p == start )

{

temp = q -> link ;

q -> link = p -> link ;

p -> link = temp ;

s -> link = p ;

temp = p ;

p = q ;

q = temp ;

s = q ;

q = q -> link ;

start = p ;

}

else

{

temp = q -> link ;

q -> link = p -> link ;

p -> link = temp ;

r -> link = q ;

s -> link = p ;

temp = p ;

p = q ;

q = temp ;

s = q ;

q = q -> link ;

}

}

}

else

{

s = q ;

q = q -> link ;

}

}

r = p ;

p = p -> link ;

}

}

bubble_sort( )

{

struct node *p, *q, *r, *s, *temp ; s = NULL ;