Article 97 - Insertion Sort Implementation

This article describes an implementation of the Insertion Sort Algorithm.

For information about the Insertion Sort Algorithm, see Article 35 - Programming Sorting Algorithms.

Implementation

In this implementation, we use the Node structure from the Link List Article, see Article 83 - Data Structure - How to Implement Linked List in C.

To make the implementation challenging, we will swap nodes instead of swapping content.

Insertion Sort implementation.

int insertionSort( Node ** list ){
    Node * sortedListPointer;
    Node * sortedListPointerPrevious;
    Node * unsortedListPointer;
    Node * unsortedListPointerPrevious;
    Node * swapPointer;
    Node * swapPointerPrevious;
    Node * tempPointer;
    Node * tempPointer2;

    if( !list ){
        return -1;
    }

    if( !*list ){
        return 0;
    }

    //iterate remaining (unsorted)
    for( unsortedListPointer = *list, unsortedListPointerPrevious = 0; 
        unsortedListPointer; ){
        swapPointer = 0;

        //iterate sorted list and find appropriate place to insert
        for( sortedListPointer = *list, sortedListPointerPrevious = 0, 
            swapPointerPrevious = 0, swapPointer = *list; 
            sortedListPointer != unsortedListPointer; ){

            if( swapPointer->content < sortedListPointer->content ){
                swapPointerPrevious = sortedListPointerPrevious;
                swapPointer = sortedListPointer;
                break;
            }

            sortedListPointerPrevious = sortedListPointer;
            sortedListPointer = sortedListPointer->next;
        }

        //splice node into the correct location
        if( swapPointer ){
            tempPointer = unsortedListPointer->next;

            if( swapPointerPrevious ){
                swapPointerPrevious->next = unsortedListPointer;
                swapPointerPrevious->next->next = swapPointer;
            }
            else{
                tempPointer2 = *list;

                *list = unsortedListPointer;
                (*list)->next = tempPointer2;
            } 

            unsortedListPointer = tempPointer;
            unsortedListPointerPrevious->next = unsortedListPointer;
        }   
        else{
            unsortedListPointerPrevious = unsortedListPointer;
            unsortedListPointer = unsortedListPointer->next;
        } 
    }

    return 0;
}

Comments (1)

Posted by anonymous - BrandieDaniel32 at Friday, March 1, 2013 4:08 AM

The <a href="http://goodfinance-blog.com">loans</a> are important for people, which want to start their own organization. As a fact, that's easy to get a collateral loan.

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.