C Quicksort Algorithm

Summary: in this tutorial, you will learn how to implement the quicksort algorithm in C.

Introduction to quicksort algorithm

The quicksort algorithm sorts an unordered list based on the divide and conquer strategy. It divides the unordered list into two sub-lists: low elements sub-list and high elements sub-list, and then recursively sort these sub-lists.

The following describes the quicksort algorithm steps:

  1. Pick an element from the list, which is called a pivot.
  2. Reorder the list with a rule that all elements which are less than the pivot come before the pivot, whereas all elements that are higher than the list come after the pivot. After partitioning the list, the pivot is in its position.
  3. With the two sub-lists, apply the above steps recursively.

The complexity of the quicksort algorithm in the worst case is O(n2), in both best and average cases are O(n log n) where n is the number of unsorted elements.

The following picture illustrates how the  quicksort algorithm sort a list of integers:

C Quicksort Algorithm

C Quicksort Algorithm Example (from Wikipedia)

The following animation illustrates how the quicksort algorithm works.

http://upload.wikimedia.org/wikipedia/commons/6/6a/Sorting_quicksort_anim.gif

Quicksort Algorithm Visualization – Pivot values are horizontal lines (from Wikipedia)

C quicksort algorithm implementation

The following is the quicksort program in C that uses the recursive function technique.

In this tutorial, we have introduced you to the quicksort algorithm and shown you how to implement quicksort in C.