Related Blog Items

• Sorting A Linked List with Bubble Sort
• Sorting a Linked List
• Sorting a Linked List with QuickSort - Simple Algorithm
• Reversing a circular single linked list using pointers
• Reversing a double linked list

The basic idea of selection sorting algorithm is

1)find minimum element in the list
2)swap it with the beginning element
3)repeat the above steps after moving pointer to next element

Here is the graphical representation of operation of this algorithm…

Before we go to linked list sorting understand how do we sort for an array…
Here is the C code for selection sort for an array

void selectionsort(int a[], int size)
{
  int i, j, min, tmp;

  for (i = 0; i < size - 1; i++)
  {
    min = i;
    for (j = i+1; j < size; j++)
      if (a[j] < a[min])
        min = j;

    //swap(a[i], a[min]);
    tmp = a[i];
    a[i] = a[min];
    a[min]=tmp;
  }
}

While sorting linked list, deal with these points carefully..
1)min node and node to be swapped are far apart, swapping routine should need to take care of this
2)min node and node to be swapped are neighbors, so just swap them
3)node to be swapped is header node, then list header node has to be changed (i.e. min node need to be assigned)

take a look at the pointers swapping while swapping neighboring nodes(on of the node to be swapped is header node)

and here is several passes of this algorithm (result of sorting linked list)…

Here is the program (for sorting linked list using selection sort)..

Node *selectionsort(Node *list)
{
  Node *tmp=list, *tmp2, *prev, *iLst, *jLst;
  Node *min;
 
  if (!list)
  {
    //empty list no need sort
    return list;
  }
 
  //swapping the nodes we require previous node (remember this is SLL)
  prev = list;
 
  for (iLst=list; iLst && iLst->next; iLst=iLst->next) 
  {
    min = iLst;
    for (jLst = iLst->next; jLst; jLst = jLst->next)
    {
      //get the minimum node
      if (jLst->info < min->info) 
      {  
        //mark the minimum node we had encountered so far
        min = jLst;
      } 
    } 
    //swap the nodes if required 
    if (iLst != min)
    {
      tmp = min->next;
 
      //go find min's previous node (min node can be many nodes away from base node to be swapped)
      for (tmp2=iLst;tmp2->next; tmp2=tmp2->next)
      {
        if (tmp2->next == min)
        {
          break;
        }
      }
 
 
      //check whether node to swapped is in beggining (i.e. header node)
      if (prev != iLst)
      {
        prev->next = min;
      }
      else
      {
        //as we do not have special header node, if the first node and some 
        //other node, need to be swapped, then update the list (makes new min node as 
        //logical header)
        list = min;
      }
 
      //are nodes to be swapped neibgoring nodes?
      if (iLst->next == min)
      {
        //nodes to be swapped are neibhoring nodes,
        //then swap them simply
        min->next = iLst;
        iLst->next = tmp;
      }
      else
      {
        //nodes to be swapped are not neibhor nodes, they are apart
        //so, consider all scenarios
        min->next = iLst->next;
 
        iLst->next = tmp;
        tmp2->next = iLst;
      }
 
      //after swapping we've changed our iterator address, so 
      //assign correct position to contnue sorting..
      iLst = min;
    }
 
    //readjust previous node before we move our list pointer
    prev = iLst;
  }
  return list;
}

downlaod full [source code]

Popularity: 45%

You need to log on to convert this article into PDF

Related Blog Items

• Sorting A Linked List with Bubble Sort
• Sorting a Linked List
• Sorting a Linked List with QuickSort - Simple Algorithm
• Reversing a circular single linked list using pointers
• Reversing a double linked list

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