C Program For Quick Sort With Time Complexity

Quick Sort is a highly efficient, comparison-based sorting algorithm known for its performance on large datasets. In this article, you will learn how Quick Sort works, its C implementation, and analyze its time complexity.

Problem Statement

Efficiently sorting data is a core requirement in many computational tasks, ranging from database management to search algorithms. Unsorted data significantly increases the time needed for operations like searching, merging, and retrieving information. The challenge is to arrange elements in a specific order (ascending or descending) as quickly and effectively as possible.

Example

Consider an unsorted array of integers. Quick Sort will rearrange these elements into ascending order.

• Input Array: [10, 7, 8, 9, 1, 5]
• Output Array (after Quick Sort): [1, 5, 7, 8, 9, 10]

Background & Knowledge Prerequisites

To understand Quick Sort, readers should be familiar with:

• Arrays: Basic data structures for storing collections of elements.
• Recursion: A function calling itself, which is fundamental to Quick Sort's divide-and-conquer strategy.
• Pointers: Used in C to manipulate array elements efficiently by passing their addresses.
• Divide and Conquer: An algorithmic paradigm where a problem is broken into smaller subproblems until they are simple enough to be solved directly, and the solutions to the subproblems are then combined to solve the original problem.

For C implementation, the standard input/output library (stdio.h) is sufficient.

Use Cases or Case Studies

Quick Sort is widely used in various applications due to its average-case efficiency:

• Database Management Systems: Used for sorting query results to present data in a structured manner.
• File Systems: Employed to sort files and directories by name, size, or date.
• Data Analysis and Visualization: Essential for preparing large datasets for analysis or graphical representation.
• Operating Systems: Utilized in memory management and process scheduling algorithms.
• Graphics and Image Processing: For sorting pixel data or vertices in rendering pipelines.

Solution Approaches

Quick Sort primarily relies on a "partition" operation. We'll detail one common implementation strategy.

1. Implementing Quick Sort using Lomuto Partition Scheme

This approach selects a pivot element and partitions the array around it, such that all elements smaller than the pivot come before it, and all elements greater come after it.

// Quick Sort Implementation
#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
   array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // pivot
    int i = (low - 1);     // Index of smaller element

    for (int j = low; j <= high - 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[high]);
    return (i + 1);
}

/* The main function that implements QuickSort
   arr[] --> Array to be sorted,
   low   --> Starting index,
   high  --> Ending index */
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        int pi = partition(arr, low, high);

        // Separately sort elements before
        // partition and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

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

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

• Sample Output:

Original array: 10 7 8 9 1 5 
Sorted array: 1 5 7 8 9 10

• Stepwise Explanation:

1. swap(int* a, int* b): A helper function to exchange the values of two integer pointers.
2. partition(int arr[], int low, int high):

• It selects the last element (arr[high]) as the pivot.
• It initializes i (index of the smaller element) to low - 1.
• It iterates through the array from low to high - 1. If an element arr[j] is smaller than the pivot, i is incremented, and arr[i] is swapped with arr[j]. This moves smaller elements to the left side of i.
• Finally, the pivot (arr[high]) is swapped with arr[i + 1], placing the pivot in its correct sorted position.
• The function returns the index of the pivot (i + 1).

1. quickSort(int arr[], int low, int high):

• This is the recursive function. The base case is low < high, meaning there's more than one element to sort.
• It calls partition to find the correct position for the pivot.
• It then recursively calls quickSort for the subarray to the left of the pivot (low to pi - 1) and the subarray to the right of the pivot (pi + 1 to high).

1. main():

• An example array is declared and initialized.
• The quickSort function is called with the array and its bounds (0 to n - 1).
• The original and sorted arrays are printed using printArray.

2. Time Complexity Analysis

The efficiency of Quick Sort heavily depends on the choice of pivot and how balanced the partitions are.

• Best Case Time Complexity: O(n log n)
• This occurs when the pivot element consistently divides the array into two roughly equal halves. Each partitioning step takes O(n) time, and because the array is halved at each step, there are log n levels of recursion.
• Average Case Time Complexity: O(n log n)
• Even with random pivot selections, Quick Sort generally performs very well. The probability of consistently picking bad pivots is low, leading to an average performance similar to the best case.
• Worst Case Time Complexity: O(n^2)
• This happens when the pivot consistently results in highly unbalanced partitions, for example, always picking the smallest or largest element as the pivot. In such a scenario, one partition is empty (or has one element), and the other contains n-1 elements. This degenerates into a linear scan for each recursive call, similar to Bubble Sort or Insertion Sort in the worst case. This can be mitigated by choosing a random pivot or a median-of-three pivot strategy.

Conclusion

Quick Sort is a powerful and widely used sorting algorithm, valued for its efficiency on average. Its divide-and-conquer approach, coupled with efficient partitioning, makes it a top choice for sorting large datasets. While its worst-case scenario can be inefficient, practical implementations often use strategies to avoid it, ensuring consistent O(n log n) performance.

Summary

• Quick Sort is an efficient, comparison-based sorting algorithm using a divide-and-conquer strategy.
• It works by partitioning an array around a pivot element and recursively sorting the sub-arrays.
• The C implementation involves a partition function to rearrange elements and a recursive quickSort function.
• Time Complexity:
• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n^2)
• Its efficiency makes it suitable for various real-world applications, from databases to operating systems.