cpppro

Archive for November, 2006|Monthly archive page

Sorting a Linked List

In C Tidbits, Data Structures in C/C++ on November 4, 2006 at 4:35 pm

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:

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

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( ) ;

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

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

getdata( ) ;
printf ( "nLinked List Before Sorting:n" ) ;
displaylist( ) ;

bubble_sort( ) ;
printf ( "nLinked List After Bubble Sorting:n" ) ;
displaylist( ) ;
}

getdata( )
{
int val, n ;
char ch ;
struct node *newnode;
newnode = NULL ;

do
{
printf ( "nEnter a value: " ) ;
scanf ( "%d", &val ) ;

append ( &newnode, val ) ;

printf ( "nAny More Nodes (Y/N): " ) ;
ch = getch( ) ;
} 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 ;
}

}

Here is the selection sort routine

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 ;
}

}

Here is the bubble sort routine…

bubble_sort( )
{
struct node *p, *q, *r, *s, *temp ; s = NULL ;

/* r precedes p and s points to the node up to which comparisons are to
be made */
while ( s != start -> link )
{
r = p = start ;
q = p -> link ;

while ( p != s )
{
if ( p -> data > q -> data )
{
if ( p == start )
{
temp = q -> link ;
q -> link = p ;
p -> link = temp ;
start = q ;
r = q ;
}
else
{
temp = q -> link ;
q -> link = p ;
p -> link = temp ;
r -> link = q ;
r = q ;
}
}
else
{
r = p ;
p = p -> link ;
}
q = p -> link ;
if ( q == s )
s = p ;
}
}
}

Let us understand the selection_sort( ) and the bubble_sort( ) functions one by one. In selection_sort( ), pointers p and q point to the nodes being compared and the pointers r and s point to the node prior to p and q respectively. Initially, p and r are set to start, where start is a pointer to the first node in the list. Also, to begin with q and s are set to p -> link. The outer loop is controlled by the condition p -> link != NULL and the inner loop is controlled by the condition q != NULL.

While adjusting the links of the nodes being compared, we would encounter one of the following four cases:

Nodes being compared are adjacent to one another and p is pointing to the first node in the list.

Nodes being compared are adjacent to one another and p is not pointing to the first node.

Nodes being compared are not adjacent to one another and p is pointing to the first node.

Nodes being compared are not adjacent to one another and p is not pointing to the first node.

Let us now understand these cases one by one.

Case (a):

When the nodes being compared are adjacent and p is pointing to the first node, the following operations are performed:

p -> link = q -> link ;
q -> link = p ;

temp = p ;
p = q ;
q = temp ;

start = p ;
r = p ;
s = q ;

q = q -> link ;

Case (b):

When the nodes being compared are adjacent and p is not pointing to the first node, the following operations are performed:

p -> link = q -> link ;
q -> link = p ;
r -> link = q ;

temp = p ;
p = q ;
q = temp ;

s = q ;
q = q -> link ;

Case (c):

When the nodes being compared are not adjacent and p is pointing to the first node, the following operations are performed:

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 ;

Case (d):
Lastly, when the nodes being compared are not adjacent and p is not pointing to the first node, the following operations are performed:

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 ;

If p -> data is not greater than q -> data then the only changes required are:

s = q ;
q = q -> link ;

These statements are simply moving s and q one node down the list. Once the control comes out of the inner loop, we need to move r and p one node down the list.
Now let us understand the bubble_sort( ) function. In bubble_sort( ), p and q point to the nodes being compared, r points to the node prior to the one pointed to by p. Lastly, s is used to point to the node up to which we have to make the comparisons. Initially, p and r are set to start, q is set to p -> link and s is set to NULL. The outer loop is controlled by the condition s != start -> link and the inner loop is controlled by the condition p != s. Now while comparing the nodes there are only two cases to be tackled. These are:

If p is pointing to the first node
If p is not pointing to the first node
In the first case, the assignments that are carried out are given below:

temp = q -> link ;
q -> link = p ;
p -> link = temp ;

start = q ;
r = q ;

On the other hand, when p is not pointing to start, the following operations should be performed:

temp = q -> link ;
q -> link = p ;
p -> link = temp ;

r -> link = q ;
r = q ;

When the condition p -> data > q -> data becomes false, we need to store the address of node currently being pointed to by p in r and then shift p and q one node down the list. In every iteration of the outer loop, the biggest element gets stored at the end. This element naturally should not be used to carry out the comparisons during the next iteration of the outer loop. That is, during every iteration of the outer loop, the inner loop should be executed one time less. The pointer s is used to keep track of the node up to which the comparisons should be made during the next iteration.

[tags]sorting, sorting a linked list, bubble sort, selection sort[/tags]

Disclaimer: this is not my own post, I’d collected information from usenet and other forums, I bear no responsibility for the accuracy and correctness of this content.