Article 103 - Bubble Sort Implementation

This article describes an implementation of the Bubble Sort Algorithm.

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

Bubble Sort implementation.

int bubblesort( Node ** list ){
    Node * listPointer;
    Node * list1PointerNext;
    Node * list1Pointer;
    Node * list1PointerPrevious;
    Node * swapPointer;
    int listSize = 0;
    int i = 0;
    
    if( !list ){
        return -1;
    }

    if( !*list ){
        return 0;
    }

    if( !(*list)->next ){
        return 0;
    }

    for( listPointer = *list; listPointer; 
        listPointer = listPointer->next ){
        listSize++;
    }

    //iterate the list
    for( i = 0; i < listSize; i++ ){

        //for each iteration, swap adjacent element
        for( list1PointerPrevious = 0, list1Pointer = *list, 
            list1PointerNext = (*list)->next; list1PointerNext; ){
            if( list1PointerNext->content < list1Pointer->content ){
                if( list1PointerPrevious ){
                    list1PointerPrevious->next = list1PointerNext;                    
                }
                else{
                    *list = list1PointerNext;
                }

                list1Pointer->next = list1PointerNext->next;
                list1PointerNext->next = list1Pointer;
            }

            if( list1PointerPrevious ){                    
                list1PointerPrevious = list1PointerPrevious->next;
            }
            else{
                list1PointerPrevious = *list;
            }

            list1Pointer = list1PointerPrevious->next;
            list1PointerNext = list1Pointer->next;
        }
    }

    return 0;
}

Comments (1)

Posted by anonymous - NV U at Tuesday, April 2, 2013 3:10 PM

Cool interview question.

What is the Big-Oh time!?

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


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