Quick sort algorithm in C programming

What is Quick Sort? 

Before reading through this article, check out the video below for better understanding of the Quick sort 

algorithm.

Quick sort Quick-sort with Hungarian folk dance 

Quick sort algorithm is a comparison-based algorithm that follows the divide-and-conquer approach to 

sort data. It starts by  selecting a 'pivot' element from the array and partitioning the other elements into 

two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then 

sorted recursively.

Lomuto Partition Scheme: 

The Lomuto partition scheme is one of the methods used to partition the array in Quick sort. It selects the 

last element of the array as the pivot and rearranges the array so that all elements less than the pivot are 

placed before it, and all elements greater than the pivot are placed after it. This partitioning process is 

performed in linear time.

Implementation: 

The Quick sort algorithm is implemented using the Lomuto partition scheme. Here's a breakdown of the 

key functions used in the implementation:

1. swap: This function swaps two integers in an array.

2. lomuto_partition: This function partitions the array based on the pivot element using the Lomuto

    partition scheme.

3. quicksort_recursive: This function recursively sorts the sub-arrays generated by partitioning.

4. quick_sort: This is the main function that initiates the Quick sort algorithm. It checks for base

    cases and calls the recursive sorting function.

Here is the code implementation of quick sort algorithm

#include <stdio.h>

#include <stddef.h>

/**

 * print_array - prints the elements of the array

 * @array:Pointer to the array

 * @size: Size of the array

 */

void print_array(int *array, size_t size)

{

    for (size_t i = 0; i < size; i++) // Iterate over each element of the array

    {

    printf("%d ", array[i]); // Print each element of the array

    }

    printf("\n"); //Print a newline character

}

/**

 * swap - Swaps two integers in an array

 * @a: Pointer to the first integer

 * @b: Pointer to the second integer

 */

void swap(int *a, int *b)

{

int temp;  // Temporary variable to hold the value during swapping

temp = *a;  // Store the value of a in temp

*a = *b; // Assign the value of b to a

*b = temp;  // Assign the stored value of a (temp) to b

}

/**

 * lomuto_partition - Lomuto partition scheme for quicksort

 * @array: The array to be sorted

 * @low: The starting index of the partition to be sorted

 * @high: The ending index of the partition to be sorted

 * @size: The size of the array

 *

 * Return: Index of the pivot element

 */

int lomuto_partition(int *array, int low, int high, size_t size)

{

int pivot, temp, i, j;

pivot = array[high];  // Select the pivot element

i = low - 1;  // Initialize the index of the smaller element

for (j = low; j <= high - 1; j++) // Iterate over each element in the partition

{

     if (array[j] < pivot)  // If current element is smaller than the pivot

     {

         i++;  // Increment index of smaller element

         if (i != j)  // If the current and previous index are not the same

         {

             temp = array[i];  // Swap array[i] and array[j]

             array[i] = array[j];

             array[j] = temp;

             print_array(array, size);  // Print the array after swapping

         }

     }

}

if (array[i + 1] != array[high])  // If the pivot element is not in its correct position

{

     temp = array[i + 1];  // Swap array[i+1] and array[high]

     array[i + 1] = array[high];

     array[high] = temp;

     print_array(array, size);  // Print the array after swapping

}

return (i + 1);  // Return the index of the pivot element

}

/**

 * quicksort_recursive - Recursive function to perform quicksort

 * @array: The array to be sorted

 * @low: The starting index of the partition to be sorted

 * @high: The ending index of the partition to be sorted

 * @size: The size of the array

 */

void quicksort_recursive(int *array, int low, int high, size_t size)

{

if (low < high)  // If there are elements in the partition

{

     int pi = lomuto_partition(array, low, high, size);  // Partition the array

     quicksort_recursive(array, low, pi - 1, size);  // Recursively sort the left subarray

     quicksort_recursive(array, pi + 1, high, size);  // Recursively sort the right subarray

}

}

/**

 * quick_sort - Sorts an array of integers in ascending order

 * @array: The array to be sorted

 * @size: The size of the array

 */

void quick_sort(int *array, size_t size)

{

if (array == NULL || size < 2)  // If array is NULL or size is less than 2

     return;  // No need to sort

quicksort_recursive(array, 0, size - 1, size);  // Call the recursive quicksort function

}

int main() {

int arr[] = {10,7,8,9,1,5};

int n = sizeof(arr) / sizeof(arr[0]);

// Function call

quick_sort(arr, n);

// Print the sorted array

printf("Sorted Array\n");

for (int i = 0; i < n; i++) {

     printf("%d ", arr[i]);

}

return (0);  // Return 0 to indicate successful execution

}

Output

Time Complexity Analysis: 

The time complexity of Quick sort varies depending on  factors such as the choice of pivot and the input 

array's distribution. Here's a summary of the time complexity in different scenarios:

• Best Case: O(n log n) - This occurs when the pivot divides the array into two equal-sized partitions.

• Average Case: O(n log n) - Quick sort typically performs well on average, making it a popular 

  choice for sorting large datasets.

• Worst Case: O(n^2) - This occurs when the pivot is either the smallest or largest element in the 

  array, leading to unbalanced partitions.

Advantages 

It is much easier to solve problems since it uses divide and conquer algorithms.

It is very efficient when large data sets are to be used.

It has low overhead since it only needs a small amount of memory to operate. 

Disadvantages

It is not suitable for small data sets.

It is not stable and due to pivot based swapping elements with same key may not retain their original order. 

It has a worst-case time complexity of O(N^2).

Applications

In database management to retrieve and organize data effectively. 

In operating systems to organize file systems and process scheduling. 

In search engines to retrieve and display search results in a relevant order quickly. 

It can be used for call routing, network optimization, and traffic management in telecommunication. 

It can be applied in bioinformatics and genomics for genome sequencing, DNA sequence alignment and 

protein structure prediction.

Conclusion: 

Quick sort is a powerful sorting algorithm known for its efficiency and versatility. By understanding its 

working principles, implementation details, and time complexity analysis, developers can leverage Quick 

sort to efficiently sort arrays of integers and other data types. It still remains the most preferred choice for 

sorting large datasets because of its average case performance. Mastering the Quick sort algorithm can 

significantly improve one's problem-solving skills and algorithmic understanding.