Monday, October 8, 2012

Sorting List using Insertion Sort

Write a program to sort a list using insertion sort.

/*
 * Node of list
 */
struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;

/*
 * Insert a node into its sorted position
 */
void SortedInsert(nodeptr* head, nodeptr newNode)
{
    nodeptr currentNode = *head;
    nodeptr prevNode = NULL;
    while(currentNode != NULL && currentNode->data < newNode->data) {
        prevNode = currentNode;
        currentNode = currentNode->next;
    }
    newNode->next = currentNode;
    if(prevNode == NULL)
        *head = newNode;
    else
         prevNode->next = newNode;

/* 
 * Insert Sort List
 */
void InsertSort(nodeptr* head)
{
    nodeptr current = *head;
    nodeptr list = NULL;
    nodeptr next = NULL;
    while(current!= NULL)
    {
        next = current->next;
        SortedInsert(&list,current);
        current = next;
    }
    *head = list;
}

No comments:

Post a Comment