Article 91 - Selection Sort Implementation

This article describes an implementation of the Selection Sort Algorithm.

For information about the Selection 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.

Selection Sort implementation.

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

    if( !list ){
        return -1;
    }

    if( !*list ){
        return 0;
    }

    for( sortedListPointer = *list, sortedListPointerPrevious = 0; 
        sortedListPointer; ){
        swapPointer = 0;

        //find the next smallest in the remaining list
        for( unsortedListPointer = sortedListPointer->next, 
            unsortedListPointerPrevious = sortedListPointer, 
            swapPointerPrevious = sortedListPointer,
            swapPointer = sortedListPointer->next; 
            unsortedListPointer; ){

            if( swapPointer->content < unsortedListPointer->content ){
                swapPointerPrevious = unsortedListPointerPrevious;
                swapPointer = unsortedListPointer;
            }

            unsortedListPointerPrevious = unsortedListPointer;
            unsortedListPointer = unsortedListPointer->next;
        }

        //swap the current node with the smallest node found
        if( swapPointer ){
            //update the previous node to point to new smallest node
            if( sortedListPointerPrevious ){
                sortedListPointerPrevious->next = swapPointer;
            }
            else{
                *list = swapPointer;
            }

            swapPointerPrevious->next = sortedListPointer;
            tempPointer = swapPointer->next;
            swapPointer->next = sortedListPointer->next;
            sortedListPointer->next = tempPointer;

            sortedListPointer = swapPointer;   
        }    

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

    return 0;
}

Comments (0)

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.