Article 89 - Quicksort Implementation

This article describes an implementation of the Quicksort Algorithm.

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

Quicksort relies on pivoting the list into, ideally, two equal sized lists. This is essentially partitioning the list into two smaller groups.

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.

In this implementation, for the sake of simplicity, we will use the first element to partition.

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

The Quicksort function is recursive, for the given invocation, it will sort the list passed to it. The list is divided into two sub lists based on the pivot and Quicksort is recursively invoked on both lists. Afterwards, it joins the two sub lists together with the pivot in the middle.

Quicksort implementation.

int quicksort( Node ** list ){
    Node * pivot;
    Node * leftSide = 0;
    Node * rightSide = 0;
    Node * leftSideEndNode = 0;
    Node * listPointer;

    if( !list ){
        return -1;
    }

    if( !*list ){
        return 0;
    }

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

    //use first node as pivot
    pivot = *list;

    *list = (*list)->next;    

    //partition into two lists
    for( ; *list;  ){
        listPointer = (*list)->next;

        if( (*list)->content < pivot->content ){
            (*list)->next = leftSide;
            leftSide = *list;

            if( !leftSideEndNode ){
                leftSideEndNode = leftSide;
            }
        }
        else{
            (*list)->next = rightSide;
            rightSide = *list;
        }

        *list = listPointer;
    }

    //recursively call quicksort on both sub lists
    quicksort( &leftSide );
    quicksort( &rightSide );

    //join two sub lists back into one sorted list
    leftSideEndNode->next = pivot;
    pivot->next = rightSide;

    *list = leftSide;

    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.