C Program For Quick Sort In Ascending Order

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. When dealing with large datasets, the choice of sorting algorithm can significantly impact performance. In this article, you will learn how to implement Quick Sort, a highly efficient comparison-based sorting algorithm, in C to arrange elements in ascending order.

Problem Statement

Efficiently sorting an array of elements in ascending order is a common requirement in many applications, from database indexing to search algorithms. A suboptimal sorting method can lead to increased processing time and resource consumption, especially with large inputs. The challenge lies in finding an algorithm that balances average-case speed with memory efficiency.

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 as: [1, 5, 7, 8, 9, 10].

Background & Knowledge Prerequisites

To understand and implement Quick Sort, familiarity with the following concepts is beneficial:

• C Language Basics: Variables, data types, arrays, functions, loops (for, while).
• Pointers in C: Understanding how to pass array elements and modify them within functions.
• Recursion: Quick Sort is a recursive algorithm, so knowledge of recursive function calls and base cases is essential.
• Divide and Conquer Paradigm: Quick Sort is an excellent example of this algorithmic strategy, where a problem is broken down into smaller subproblems.

Use Cases or Case Studies

Quick Sort is widely used due to its efficiency and in-place sorting nature. Here are a few practical applications:

• Database Systems: Used for sorting records based on specific keys, improving query performance.
• Search Algorithms: Pre-sorting data enables the use of highly efficient search algorithms like binary search.
• Computational Geometry: Essential for algorithms that require points or objects to be ordered by coordinates.
• Operating Systems: Used in internal sorting routines, such as scheduling processes by priority or size.
• Data Analysis and Visualization: Sorting data helps in identifying patterns, outliers, and preparing data for graphical representation.

Solution Approaches

Quick Sort employs a divide-and-conquer strategy, partitioning an array around a 'pivot' element.

Standard Quick Sort Implementation

Quick Sort works by selecting 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 in Ascending Order
#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() {
    // Step 1: Define the array to be sorted
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Step 2: Call quickSort function to sort the array
    quickSort(arr, 0, n - 1);

    // Step 3: Print the sorted array
    printf("Sorted array in ascending order: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output

Original array: 10 7 8 9 1 5 
Sorted array in ascending order: 1 5 7 8 9 10

Stepwise Explanation

1. swap(int* a, int* b) Function: This utility function takes two integer pointers and exchanges the values they point to. It's a fundamental operation for rearranging elements during sorting.
2. partition(int arr[], int low, int high) Function:

• It selects the last element (arr[high]) as the pivot.
• It maintains an index i (initialized to low - 1), which points to the position where the next element smaller than the pivot should be placed.
• It iterates through the array from low to high - 1 using index j.
• If an element arr[j] is found to be smaller than the pivot, i is incremented, and arr[i] and arr[j] are swapped. This ensures that all elements smaller than the pivot are kept to the left of i.
• Finally, the pivot element (arr[high]) is swapped with the element at arr[i + 1]. This places the pivot in its correct sorted position, with all elements to its left being smaller and all to its right being greater.
• The function returns i + 1, which is the index of the pivot after partitioning.

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

• This is the main recursive function.
• Its base case is if (low < high), meaning if the sub-array has more than one element.
• It calls partition() to place the pivot at its correct position and get the partitioning index pi.
• It then recursively calls quickSort() for the sub-array before the pivot (low to pi - 1).
• It also recursively calls quickSort() for the sub-array after the pivot (pi + 1 to high).

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

• Initializes an unsorted integer array.
• Calculates the size n of the array.
• Prints the original array.
• Calls quickSort() with the array, starting index (0), and ending index (n - 1).
• Prints the sorted array.

Conclusion

Quick Sort is a highly efficient, in-place sorting algorithm that uses a divide-and-conquer strategy. Its average-case time complexity of O(N log N) makes it a preferred choice for many real-world applications where performance is critical. While its worst-case complexity is O(N^2), this scenario is rare with good pivot selection strategies.

Summary

• Quick Sort is a divide-and-conquer sorting algorithm.
• It works by partitioning an array around a chosen pivot element.
• Elements smaller than the pivot are moved to its left, and larger ones to its right.
• The partitioning process is recursively applied to the sub-arrays.
• Its average-case time complexity is O(N log N), making it very efficient for large datasets.
• The C implementation involves swap, partition, and quickSort recursive functions.