# Article 89 - Quicksort Implementation

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;
}``` 