This blog post explains the Quick Sort Algorithm and its implementation using the C programming language. So before writing the C code for the Quick Sort let’s first understand the QuickSort algorithm.

Note: However, always choosing the last element in the partition as the pivot in this way results in poor performance (O(n²)) on already sorted arrays or arrays of identical elements. 

QuickSort Algorithm Steps:

Let’s see the required steps to sort a list using the QuickSort algorithm.

1. Choose the Pivot Element:

In the beginning, we have already discussed the ways to select the pivot elements. Here, we are selecting the last element of the array as the pivot element.

                  3 ,7 ,8 ,5 ,2 , 1, 9 ,5, 4

/* partition function takes last element as pivot and places
   the pivot element at its correct position. It means all
   smaller element will be plaved to left all greater elements
   to right of pivot
 */
int partition(arr[],  start,  end)
{
    // pick last element as pivot
    pivot = arr[end];

    i = (start - 1)  // Index of smaller element and indicates the
        // right position of pivot found so far

    for (j = start; j <= (end- 1); ++j)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[end]
    return (i + 1);
}

Explanation of the above pseudo code:

arr[] = {3, 7, 8, 5, 2, 1, 9, 5, 4}
Indexes: 0  1  2  3  4  5  6  7  8


start = 0, end =  8, pivot = arr[h] = 4
Initialize index of smaller element, i = -1





Traverse elements from j = start to end-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0 
arr[] = {3, 7, 8, 5, 2, 1, 9, 5, 4}// No change as i and j 
                                     // are same both are 0


j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]


j = 2 : Since arr[j] > pivot, do nothing
// No change in i and arr[]


j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]



j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {3, 2, 8, 5, 7, 1, 9, 5, 4} // We swap 2 and 7 


j = 5 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {3, 2, 1, 5, 7, 8, 9, 5, 4} // We swap 1 and 8 


j = 6 : Since arr[j] > pivot, do nothing
// No change in i and arr[]


j = 7 : Since arr[j] > pivot, do nothing
// No change in i and arr[]



We come out of loop because j is now equal to end-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[end] (or pivot) 

arr[] = {3, 2, 1, 4, 7, 8, 9, 5, 5} // We swap 4 and 5 


Now 4 is at its correct place. All elements smaller than
4 are before it and all elements greater than 4 are after
it.

3. Apply the above steps recursively to both sub-lists on the left and right of the pivot

Let’s seen an image for better understanding, it explains all the steps taken by the quick Sort to sort the given random set of elements. It is an expanded version of the above steps and also chosen the last element is as ‘pivot‘. You can see the below image in which the shaded element is the pivot.

Now let’s see the example code for the QuickSort Algorithm using the C programming language.

#include <stdio.h>

//function to swap variable
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

/* partition function takes last element as pivot and places
   the pivot element at its correct position. It means all
   smaller element will be placed to left all greater elements
   to right of pivot
 */
int partition (int arr[], int start, int end)
{
    int pivot = arr[end]; // pivot
    int i = (start - 1);
    int j = start;

    for (j = start; j <= (end - 1); j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++; // increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[end]);

    return (i + 1);
}

/*
arr[] --> Array to be sorted,
start --> Starting index,
end --> Ending index */
void quickSort(int arr[], int start, int end)
{
    if (start < end)
    {
        // find the pivot element such that
        // elements smaller than pivot are on left of pivot
        // elements greater than pivot are on right of pivot
        int pi = partition(arr, start, end);

        // recursive call on the left of pivot
        quickSort(arr, start, pi - 1);

        // recursive call on the right of pivot
        quickSort(arr, pi + 1, end);
    }
}

//print array element
void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}


int main()
{
    int arr[] = {3, 7, 8, 5, 2, 1, 9, 5, 4};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, arr_size - 1);

    printf("Sorted array: \n");

    printArray(arr, arr_size);

    return 0;
}

Output: 1 2 3 4 5 5 7 8 9

Recommended Articles for you:

• Insertion Sort Algorithm.
• Merge Sort Algorithm.
• Selection Sort Algorithm.
• Bubble Sort Algorithm in C.
• Radix Sort Algorithm.
• Counting Sort Algorithm.
• Best programming laptop for programmers.
• How do you reverse an array in C?
• C program to find the Median of two sorted arrays of different sizes.
• Basics of the recursive function.
• Merge Sort algorithm with example code.
•  C program to rearrange array such that even positioned are greater than odd.
• How to rotate an array left and right by a given number K?
• Why is it faster to process sorted array than an unsorted array?
• How to access 2d array in C?
• How to remove duplicates from a given array in C?
• Array interview questions.
• How to create dynamic array in C?
• How to pass an array as a parameter in C?