Related Blog Items

• Sorting a Linked List with Selection Sort
• Sorting a Linked List
• Questions asked in various job interviews (in Programming)
• Sorting a Linked List with QuickSort - Simple Algorithm
• Reversing a circular single linked list using pointers

The basic idea of this sorting algorithm is to
compare two neighboring objects, and to swap them if
they are in the wrong order.

here is an example, which shows sorted list in several passes..

5   10   20   13   7   17
5   10   13   7    17  20
5   10   7    13   17  20
5   7    10   13   17  20
5   7    10   13   17  20

Here’s a snippet of C code for bubble sort for sorting an array:

for (i=0; i<n-1; i++) 
{
  for (j=0; j<n-1-i; j++)
  {
    /* compare the two neighbors */
    if (a[j+1] < a[j]) 
    {      
      /* swap a[j] and a[j+1]      */
      tmp = a[j];         
      a[j] = a[j+1];
      a[j+1] = tmp;
    }
  }
}

Here is the code for sorting linked list..

Node *bubblesort(Node *list)
{
  Node *lst, *tmp = list, *prev, *potentialprev = list;
  int idx, idx2, n = 0;
 
  //determine total number of nodes
  for (;tmp->next; tmp=tmp->next)
  {
    n++;
  }
 
  for (idx=0; idx<n-1; idx++) 
  {
    for (idx2=0,lst=list; 
         lst && lst->next && (idx2<=n-1-idx);
         idx2++)
    {
      if (!idx2)
      {
        //we are at beginning, so treat start 
        //node as prev node
        prev = lst;
      }
 
      //compare the two neighbors
      if (lst->next->info < lst->info) 
      {  
        //swap the nodes
        tmp = (lst->next?lst->next->next:0);
 
        if (!idx2 && (prev == list))
        {
          //we do not have any special sentinal nodes
          //so change beginning of the list to point 
          //to the smallest swapped node
          list = lst->next;
        }
        potentialprev = lst->next;
        prev->next = lst->next;
        lst->next->next = lst;
        lst->next = tmp;
        prev = potentialprev;
      }
      else
      {
        lst = lst->next;
        if(idx2)
        {
          //just keep track of previous node, 
          //for swapping nodes this is required
          prev = prev->next;
        }
      }     
    } 
  }
  return list;
}

The above code swaps two linked list nodes (swaps node pointers not data) if they are in wrong order. For swapping two nodes we require previous and next node of swapping nodes, this is  what induced the complexity in our simple algorithm. We are keeping track of a "prev" pointer to aid swapping, and some special variables for to track new start of the sorted list (as we do not have special head or tail nodes, we need to keep an eye on beginning of the linked list, which may get required to altered by swapping the nodes).

Download the code here…

let me know you comments… 

Popularity: 100%

You need to log on to convert this article into PDF

Related Blog Items

• Sorting a Linked List with Selection Sort
• Sorting a Linked List
• Questions asked in various job interviews (in Programming)
• Sorting a Linked List with QuickSort - Simple Algorithm
• Reversing a circular single linked list using pointers

This entry was written by ponnada and posted on April 11, 2007 at 10:01 pm and filed under C Tidbits, Data Structures in C/C++, Pointers & Callbacks. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.