C Program For Quick Sort Using Divide And Conquer

Quick Sort is an efficient, comparison-based sorting algorithm that leverages the divide and conquer paradigm. In this article, you will learn how to implement Quick Sort in C using this powerful strategy, understanding its core mechanics and practical application.

Problem Statement

Sorting a list of elements is a fundamental problem in computer science, essential for various applications like searching, data analysis, and database indexing. While simple sorting algorithms exist, they often perform poorly on large datasets. The challenge is to sort an array of elements efficiently, minimizing the time complexity, especially for large inputs.

Example

Consider the following unsorted array: [10, 7, 8, 9, 1, 5]

After applying Quick Sort, the array will be sorted in ascending order: [1, 5, 7, 8, 9, 10]

Background & Knowledge Prerequisites

To understand Quick Sort, readers should have a basic grasp of:

• C Programming Basics: Variables, arrays, loops, functions.
• Recursion: Understanding how functions call themselves.
• Pointers: Basic knowledge of how pointers work in C for array manipulation (though not strictly necessary for this implementation, it helps in understanding memory).

No specific imports or complex setup are needed beyond a standard C compiler.

Use Cases or Case Studies

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

• Database Systems: Used for sorting records based on specific keys, optimizing query performance.
• Search Algorithms: Pre-sorting data significantly speeds up search operations like binary search.
• Data Analysis: Organizing large datasets for easier analysis and pattern recognition.
• Operating Systems: Employed in tasks like scheduling processes or managing memory blocks.
• Graphics and Image Processing: Used for tasks requiring ordering of pixels or geometric objects.

Solution Approaches

Quick Sort operates by picking an element as a 'pivot' and partitioning the array around it. All elements smaller than the pivot are moved to its left, and all greater elements to its right. This process is then recursively applied to the sub-arrays.

Quick Sort (Divide and Conquer)

This approach sorts an array by selecting a pivot element, partitioning the array such that all elements smaller than the pivot are before it, and all larger elements are after it, then recursively applying this process to the sub-arrays.

// Quick Sort using Divide and Conquer
#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) {
    // Step 1: Select the last element as the pivot
    int pivot = arr[high];
    // Index of smaller element and indicates the right position of the pivot found so far
    int i = (low - 1);

    // Step 2: Traverse through all elements and compare each element with pivot
    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]);
        }
    }
    // Step 3: Swap the pivot element with the element at (i + 1)
    swap(&arr[i + 1], &arr[high]);
    // Step 4: Return the partitioning index
    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) {
    // Step 1: Base case for recursion - if low is less than high, continue
    if (low < high) {
        // Step 2: Partition the array and get the pivot index
        int pi = partition(arr, low, high);

        // Step 3: Recursively sort elements before partition and after partition
        quickSort(arr, low, pi - 1);  // Sort the left sub-array
        quickSort(arr, pi + 1, high); // Sort the right sub-array
    }
}

// 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() {
    // Step 1: Initialize an unsorted array
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Apply Quick Sort to the array
    quickSort(arr, 0, n - 1);

    // Step 4: Print the sorted array
    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) Function: A utility function to exchange the values of two integer pointers. This is crucial for rearranging elements within the array.
2. partition(int arr[], int low, int high) Function:

• It selects the last element (arr[high]) as the pivot.
• It maintains an index i (initially low - 1) for the smaller element.
• It iterates through the array from low to high - 1. If an element arr[j] is found to be smaller than the pivot, i is incremented, and arr[i] is swapped with arr[j]. This ensures all elements less than the pivot are gathered on the left side of i.
• Finally, the pivot (originally at arr[high]) is swapped with the element at arr[i + 1]. This places the pivot in its correct sorted position.
• The function returns i + 1, which is the index of the pivot in its final position.

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

• This is the main recursive function. The base case for the recursion is if (low < high). If low is not less than high, it means the sub-array has one or zero elements and is already sorted.
• It calls partition to find the correct position for the pivot and partitions the array, returning the pivot's index pi.
• It then recursively calls quickSort for the sub-array to the left of the pivot (low to pi - 1).
• It also recursively calls quickSort for the sub-array to the right of the pivot (pi + 1 to high).

1. printArray(int arr[], int size) Function: A simple helper function to display the contents of an array.
2. main() Function:

• An example array arr is initialized.
• The printArray function displays the original unsorted array.
• quickSort is called with the array and its bounds (0 to n-1).
• The printArray function then displays the sorted array.

Conclusion

Quick Sort stands as a highly effective sorting algorithm, distinguished by its average-case time complexity of O(n log n). Its reliance on the divide and conquer strategy, where the array is partitioned around a pivot and then recursively sorted, makes it a powerful tool for efficiently organizing large datasets. While its worst-case performance can be O(n^2), proper pivot selection strategies often mitigate this, making it a preferred choice in many real-world applications.

Summary

• Divide and Conquer: Quick Sort breaks down a problem into smaller, more manageable sub-problems, then combines their solutions.
• Pivot Selection: An element is chosen as a pivot, typically the last element in the partition function's common implementation.
• Partitioning: The array is rearranged so that elements smaller than the pivot are to its left, and elements larger are to its right. The pivot ends up in its final sorted position.
• Recursion: The Quick Sort process is recursively applied to the sub-arrays on both sides of the pivot until the entire array is sorted.
• Efficiency: Offers an average-case time complexity of O(n log n), making it very fast for large datasets.