C Program For Quick Sort Algorithm In Data Structure

Quick Sort is an efficient, comparison-based sorting algorithm that often excels in practical applications. It employs a divide-and-conquer strategy, making it one of the fastest sorting algorithms in practice for large datasets. In this article, you will learn how Quick Sort works, its advantages, and how to implement it efficiently in C.

Problem Statement

Efficiently organizing data is a fundamental task in computer science. Unsorted data can lead to slow search times, inefficient data processing, and difficulties in data analysis. The core problem is to rearrange a collection of items into a specific order, typically numerical or alphabetical, in a way that is both fast and resource-efficient. For large datasets, a naive sorting approach can become computationally expensive, highlighting the need for advanced algorithms like Quick Sort.

Example

Consider an unsorted array of integers: [10, 7, 8, 9, 1, 5]

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

Background & Knowledge Prerequisites

To understand and implement Quick Sort in C, readers should be familiar with the following concepts:

• C Language Basics: Variables, data types, arrays, loops (for, while).
• Functions: Defining and calling functions, passing arguments, return types.
• Pointers: Understanding how pointers work, especially in the context of arrays and passing them to functions.
• Recursion: Quick Sort is inherently a recursive algorithm, so a solid grasp of recursion (base cases, recursive calls) is essential.
• Basic Sorting Concepts: An initial understanding of what sorting entails and why it's important.

Use Cases

Quick Sort is widely used in various applications due to its average-case efficiency. Here are a few practical examples:

• Database Management Systems: Used for sorting records based on specific keys to optimize query performance and data retrieval.
• Operating Systems: Employed in scheduling algorithms (e.g., sorting processes by priority) and file system management.
• Data Analysis and Visualization: Sorting data helps in identifying patterns, calculating statistics, and preparing data for graphical representation.
• Search Algorithms: Many search algorithms, like binary search, require sorted data to function efficiently. Quick Sort can pre-process data for these searches.
• E-commerce Product Sorting: Websites often use sorting to display products based on price, popularity, or relevance, improving user experience.

Solution Approaches

Quick Sort operates on the principle of divide and conquer. It partitions an array into two sub-arrays around a "pivot" element such that elements smaller than the pivot are on one side, and elements greater than the pivot are on the other. It then recursively sorts the sub-arrays.

Standard Quick Sort Implementation

Quick Sort works by picking an element as a pivot and partitioning the given array around the picked pivot. The most common approach involves selecting the last element as the pivot.

// Quick Sort Algorithm in C
#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 (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() {
    // Step 1: Define an array to be sorted
    int arr[] = {10, 7, 8, 9, 1, 5, 2, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Call the Quick Sort function
    quickSort(arr, 0, n - 1);

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

    return 0;
}

Run

Sample Output:

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

Stepwise Explanation:

1. swap(int* a, int* b) Function: This utility function is used to exchange the values of two integers. It takes pointers to the integers to modify them directly.
2. partition(int arr[], int low, int high) Function:

• It selects the last element arr[high] as the pivot.
• It initializes i (index of smaller element) to low - 1.
• It iterates through the array from low to high - 1 using index j.
• If arr[j] is smaller than the pivot, it increments i and swaps arr[i] with arr[j]. This moves smaller elements to the left of i.
• Finally, it swaps the pivot (originally at arr[high]) with arr[i + 1]. This places the pivot in its correct sorted position.
• It returns the index of the pivot (i + 1).

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

• This is the main recursive function. The base case for recursion is 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 get the pivot's correct position (pi).
• It then recursively calls quickSort() for the sub-array to the left of the pivot (arr[low...pi-1]).
• It also recursively calls quickSort() for the sub-array to the right of the pivot (arr[pi+1...high]).

1. main() Function:

• An unsorted integer array arr is defined.
• The size of the array n is calculated.
• The original array is printed.
• quickSort() is called with the array and its initial low (0) and high (n-1) indices.
• The sorted array is then printed.

Conclusion

Quick Sort is a highly efficient sorting algorithm with an average time complexity of O(n log n), making it suitable for large datasets. Its in-place nature also contributes to its efficiency by minimizing additional memory usage. While its worst-case time complexity is O(n^2), practical implementations often mitigate this by using various pivot selection strategies. Understanding its recursive, divide-and-conquer approach is key to mastering this fundamental algorithm.

Summary

• Algorithm Type: Divide and Conquer, Comparison Sort.
• Time Complexity:
• Average Case: O(n log n)
• Worst Case: O(n^2) (e.g., when array is already sorted or reverse sorted and pivot choice is naive)
• Best Case: O(n log n)
• Space Complexity: O(log n) on average due to recursion stack (O(n) in worst case).
• Stability: Not a stable sorting algorithm by default (relative order of equal elements may change).
• Key Idea: Selects a pivot element, partitions the array such that elements smaller than the pivot are on one side and larger elements are on the other, then recursively sorts the sub-arrays.