Quick Sort in C (With Code Examples)

Sorting is a fundamental operation in computer science, and one of the most efficient sorting algorithms is Quick Sort. This article delves into the intricacies of Quick Sort in C, providing a detailed understanding of the algorithm, its implementation, and its advantages.

What is Quick Sort in C

Quick Sort is a highly efficient sorting algorithm that employs the divide-and-conquer strategy. It was developed by Tony Hoare in 1959 and has since become one of the most widely used sorting algorithms due to its superior performance in practical applications. The primary idea behind Quick Sort is to partition the array into smaller sub-arrays, sort these sub-arrays, and then combine them to form the final sorted array.

How QuickSort Works

Quick Sort operates 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. This process can be broken down into the following steps:

1. Choose a Pivot: Select an element from the array as the pivot. Various methods can be used to choose the pivot, such as picking the first element, the last element, the middle element, or a random element.
2. Partitioning: Rearrange the array so that all elements less than the pivot come before it, and all elements greater than the pivot come after it. This partitioning step ensures that the pivot is in its final sorted position.
3. Recursively Apply: Recursively apply the above steps to the sub-arrays formed by the partitioning step.

Quick Sort Visualization

Pseudocode for Quick Sort in C Program

QUICKSORT(arr, low, high)
    if low < high then
        pivotIndex = PARTITION(arr, low, high)
        QUICKSORT(arr, low, pivotIndex - 1)
        QUICKSORT(arr, pivotIndex + 1, high)

PARTITION(arr, low, high)
    pivot = arr[high]
    i = low - 1
    for j = low to high - 1 do
        if arr[j] <= pivot then
            i = i + 1
            SWAP(arr[i], arr[j])
    SWAP(arr[i + 1], arr[high])
    return i + 1

SWAP(a, b)
    temp = a
    a = b
    b = temp

Explanation of Quick Sort Code in C

QUICKSORT Function:

• This is the main function that sorts the array.
• It takes three parameters: arr (the array to be sorted), low (the starting index of the array/sub-array), and high (the ending index of the array/sub-array).
• If low is less than high, it means there are at least two elements to be sorted.
• The array is partitioned around a pivot element returned by the PARTITION function, and then QUICKSORT is called recursively on the left and right sub-arrays formed by the partitioning process.

PARTITION Function:

• This function partitions the array around a pivot element and places the pivot in its correct position in the sorted array.
• It takes three parameters: arr, low, and high.
• The pivot is chosen as the last element of the array (arr[high]).
• A pointer i is initialized to low - 1. This pointer keeps track of the last position of the smaller elements relative to the pivot.
• A loop iterates through the array from low to high - 1. If an element is smaller than or equal to the pivot, i is incremented, and the element is swapped with the element at position i.
• After the loop, the pivot element is swapped with the element at position i + 1 to place the pivot in its correct position.
• The function returns the index of the pivot element (i + 1).

SWAP Function:

• This utility function swaps two elements.
• It takes two parameters a and b, which are the elements to be swapped.
• A temporary variable temp is used to hold the value of a during the swap.

Detailed Steps of the Quick Sort Algorithm in C

Initialization:

• Start with the entire array to be sorted (low = 0, high = length of array - 1).

Partitioning:

• Select the pivot element (usually the last element in the current sub-array).
• Initialize a pointer i to low - 1.

Element Comparison and Swapping:

• Iterate through the array from low to high - 1.
• For each element, if it is less than or equal to the pivot, increment i and swap the current element with the element at position i.

Final Pivot Placement:

• After the loop, swap the pivot element with the element at position i + 1.
• The pivot is now in its correct position in the sorted array.

Recursive Sorting:

• Recursively apply the above steps to the sub-arrays to the left and right of the pivot.
• Continue the process until the base case is reached (when low is not less than high).

Example Walkthrough

Let's walk through an example to see how the pseudocode translates into action. Consider the array: [10, 7, 8, 9, 1, 5].

1. Initial Call: QUICKSORT(arr, 0, 5)
   • Partition the array with pivot = 5:
     • i starts at -1.
     • 10 > 5 (no swap, i remains -1).
     • 7 > 5 (no swap, i remains -1).
     • 8 > 5 (no swap, i remains -1).
     • 9 > 5 (no swap, i remains -1).
     • 1 <= 5 (increment i to 0, swap arr[0] with arr[4]).
   • Swap pivot with arr[1]: [1, 5, 8, 9, 10, 7].
   • Return pivotIndex = 1.
2. Recursive Calls:
   • QUICKSORT(arr, 0, 0) (base case, single element).
   • QUICKSORT(arr, 2, 5):
     • Partition with pivot = 7:
       • i starts at 1.
       • 8 > 7 (no swap, i remains 1).
       • 9 > 7 (no swap, i remains 1).
       • 10 > 7 (no swap, i remains 1).
     • Swap pivot with arr[2]: [1, 5, 7, 9, 10, 8].
     • Return pivotIndex = 2.
3. Further Recursive Calls:
   • QUICKSORT(arr, 2, 1) (base case, invalid range).
   • QUICKSORT(arr, 3, 5):
     • Partition with pivot = 8:
       • i starts at 2.
       • 9 > 8 (no swap, i remains 2).
       • 10 > 8 (no swap, i remains 2).
     • Swap pivot with arr[3]: [1, 5, 7, 8, 10, 9].
     • Return pivotIndex = 3.
4. Final Recursive Calls:
   • QUICKSORT(arr, 3, 2) (base case, invalid range).
   • QUICKSORT(arr, 4, 5):
     • Partition with pivot = 9:
       • i starts at 3.
       • 10 > 9 (no swap, i remains 3).
     • Swap pivot with arr[4]: [1, 5, 7, 8, 9, 10].
     • Return pivotIndex = 4.

After these steps, the array is sorted: [1, 5, 7, 8, 9, 10].

Quick Sort Program in C

#include <stdio.h>

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

// Partition function
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 or equal to 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
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi is partitioning index, arr[p] 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");
}

// Driver program to test above functions
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

Explanation

Swap Function: This utility function swaps two elements in the array.

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

The swap function uses a temporary variable to swap the values of two integers. This function is crucial in the partitioning process to move elements around the pivot.

Partition Function: This function takes the last element as the pivot, places the pivot at its correct position in the sorted array, and places all smaller elements to the left of the pivot and all greater elements to the right.

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 (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

The partition function is where the array is rearranged. It places the pivot element in its correct position and ensures all elements less than the pivot are on its left and all elements greater are on its right.

QuickSort Function: This is the main function that implements the Quick Sort algorithm. It recursively calls itself to sort the sub-arrays.

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

The quickSort function calls the partition function to get the pivot index and then recursively sorts the sub-arrays before and after the pivot.

PrintArray Function: This utility function prints the array.

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

The printArray function is a simple loop that prints each element of the array.

Main Function: This is the driver function that initializes the array, calls the quickSort function, and prints the sorted array.

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: ");
    printArray(arr, n);
    return 0;
}

The main function initializes the array, calculates its size, and calls quickSort to sort the array. Finally, it prints the sorted array.

Learn more with our latest blogs “History of C Language” and “Bubble Sort in C”

Analysis of Quick Sort

Quick Sort is known for its efficiency and is often faster in practice than other O(n log n) algorithms like Merge Sort and Heap Sort. However, its performance depends on the choice of the pivot.

• Time Complexity:
  • Best Case: O(n log n) - This occurs when the pivot divides the array into two nearly equal halves.
  • Average Case: O(n log n) - This occurs when the pivots are reasonably balanced.
  • Worst Case: O(n^2) - This occurs when the pivot always divides the array into two unbalanced sub-arrays, for example, if the smallest or largest element is always chosen as the pivot.
• Space Complexity: O(log n) - This is due to the recursive stack space.

Choosing the Pivot

The efficiency of Quick Sort largely depends on the choice of the pivot. Here are some common strategies for choosing the pivot:

1. First Element: Choosing the first element as the pivot is simple but can lead to poor performance on already sorted arrays.
2. Last Element: Choosing the last element as the pivot is equally simple but can also result in poor performance on sorted arrays.
3. Middle Element: Choosing the middle element as the pivot can provide a better balance.
4. Random Element: Choosing a random element as the pivot reduces the chance of poor performance.
5. Median-of-Three: Choosing the median of the first, middle, and last elements as the pivot is a popular strategy that often results in good performance.

Advantages of Quick Sort

Efficient for Large Datasets: Quick Sort is one of the fastest sorting algorithms for large datasets.

In-Place Sorting: Quick Sort does not require additional storage space, making it more memory-efficient than Merge Sort.

Divide-and-Conquer Approach: The divide-and-conquer strategy allows for efficient parallelization, which can further enhance performance on modern multi-core processors.

Disadvantages of Quick Sort

Unstable Sorting: Quick Sort is not a stable sort, meaning that equal elements may not retain their relative order. However, this can be mitigated with modifications to the partitioning scheme.

Worst-Case Performance: Its worst-case time complexity is O(n^2), which can be mitigated by using randomized or median-of-three pivot selection techniques.

Applications of Quick Sort

1. General Sorting

• Databases: Quick Sort is often used to sort records in a database based on one or more fields.
• File Systems: It is used in file systems to sort file names or directories.
• E-commerce: Sorting product lists by price, rating, or popularity.

2. Searching Algorithms

• Binary Search: Quick Sort is used to sort data before performing binary search operations, which require sorted data.
• Data Indexing: It is used to sort data for efficient indexing and retrieval.

3. Algorithm Design

• Divide and Conquer: Quick Sort is a classic example of the divide-and-conquer algorithm, which is foundational in algorithm design and analysis.
• Parallel Algorithms: Its structure is conducive to parallel execution, making it useful in parallel computing environments.

4. Data Analysis

• Statistical Analysis: Used to sort large datasets in statistical analysis and data mining.
• Median Finding: Quick Sort can be adapted to find the median or other order statistics efficiently.

5. Computer Graphics

• Rendering: Used in graphics algorithms for tasks such as depth sorting (Painter’s Algorithm).
• Object Sorting: Sorting objects based on various attributes like distance from the camera.

6. Networking

• Packet Sorting: Used in networking to sort packets based on different criteria, such as priority or arrival time.
• Routing Algorithms: Helps in sorting routing paths based on cost or distance.

7. Operating Systems

• Task Scheduling: Used in operating systems to sort tasks based on priority or deadlines.
• Memory Management: Sorting memory blocks or pages for efficient allocation and deallocation.

8. Game Development

• Leaderboard Sorting: Sorting player scores or ranks in real-time.
• Collision Detection: Sorting objects in a game environment to efficiently check for collisions.

9. Scientific Computing

• Simulation Data: Sorting simulation data for analysis and visualization.
• Numerical Methods: Used in numerical methods that require sorted data, such as certain interpolation techniques.

10. Libraries and Frameworks

• Standard Libraries: Quick Sort is often implemented in standard libraries of various programming languages due to its efficiency and simplicity.
• Frameworks: Used in frameworks that provide sorting functionalities.

Conclusion

Quick Sort in C is a highly efficient sorting algorithm that uses a divide-and-conquer approach to partition and sort arrays. This article has provided a comprehensive look at Quick Sort, including its theoretical basis, pseudocode, implementation in C, and example walkthrough.

Quick Sort is widely applicable across various domains, such as databases, file systems, e-commerce, searching algorithms, data analysis, and more. Its performance can be optimized by choosing a good pivot and employing simpler sorting algorithms for small sub-arrays.

Understanding and implementing Quick Sort can significantly enhance your ability to efficiently sort data, making it an essential tool in your programming arsenal.

Enroll in our full stack web development course with a pay after placement opportunity to enhance your skills and secure your future!