Quick Sort in C

Quick Sort in C. In this article, we are going to see a quick sort algorithm in C.

Introduction of Quick Sort

Quick sort, developed by Tony Hoare in 1960 is a highly efficient sorting algorithm that is still widely used due to its superior performance in most cases. Quick sort follows the divide and conquer strategy to sort elements in an array which makes it significantly faster than simpler sorting algorithms like Bubble Sort or Selection Sort for large data sets.

Quick Sort Algorithm Explaination

The essence of quick sort lies in its partitioning process, where the arrays are divided into subarrays based on a pivot element, such that elements less than the pivot are on its left and that creator is on its right. This pivot can be any element from the array- choice varies from the first element, the last element, the median, or a random element. The choice of pivot affects the algorithm’s efficiency but does not impact its correctness.

Implementing Quick Sort in C

Implementing quick sort in C involves understanding the partitioning logic and the recursive structure of the algorithm. The implementation starts with the function to partition the array and another function that utilizes this partition to sort the array recursively.

• Partition Function: This function selects the pivot and partitions array around the pivot. It moves all elements smaller than the pivot to its left and all larger elements to its right. The function then returns the index of the pivot element after partitioning.
• Quick Sort Function: This function calls itself recursively to sort the sub-arrays formed after partitioning.

Quick Sort C Program

#include <stdio.h>
void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int array[], int low, int high)
{
    int pivot = array[high];
    int i = low - 1;
    for (int j = low; j <= high; j++)
    {
        if (array[j] < pivot)
        {
            i++;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i + 1], &array[high]);
    return i + 1;
}
void quickSort(int array[], int low, int high)
{
    if (low < high)
    {
        int partitionIndex = partition(array, low, high);
        quickSort(array, low, partitionIndex - 1);
        quickSort(array, partitionIndex + 1, high);
    }
}
void main()
{
    int array[] = {6, 7, 8, 4, 2, 67, 23, 56};
    int n = sizeof(array) / sizeof(array[0]);
    printf("Array before sorting\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", array[i]);
    }
    quickSort(array, 0, n - 1);
    printf("\nArray after sorting\n");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", array[i]);
    }
}

Output

Quick Sort Complexity

The performance of quick sort depends significantly on the choice of the pivot. On average the time complexity of quick sort is O(n logn) making it one of the fastest algorithms for large data sets. However, in the worst case, it’s time complexity can decrease to O(n^2), particularly when the smallest and largest element is always chosen as the pivot. The space complexity of quick sort is O(logn) due to the recursive call.

Applications of Quick Sort

Quick sort is often used in systems where high performance is critical and memory use needs to be minimized. It is suitable for sorting large data sets, like database algorithms or operations requiring fast and efficient sorting in memory. However, for datasets that are too large to fit in memory, other algorithms like merge sort might be preferred due to their predictable performance.

Happy Coding & Learning

See Also

• How to Remove Vowels from a String in Java
• Selection Sort in C