C Program to Implement Quick Sort

Introduction

Quick Sort is an efficient, in-place, comparison-based sorting algorithm. It works 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 continues until the entire array is sorted.

Example:

• Input: Unsorted array [10, 7, 8, 9, 1, 5]
• Output: Sorted array [1, 5, 7, 8, 9, 10]

Problem Statement

Create a C program that:

• Implements the Quick Sort algorithm to sort an array.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Partition Function: This function partitions the array around the pivot element.
3. Implement the Quick Sort Function: This function recursively sorts the sub-arrays.
4. Create a Main Function: Allow the user to input the array, apply quick sort, and display the sorted array.

C Program to Implement Quick Sort

#include <stdio.h>

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

// Function to perform the partitioning of the array
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Select the last element as the pivot
    int i = (low - 1);  // Index of the smaller element

    for (int j = low; j <= high - 1; j++) {
        // If the current element is smaller than or equal to the pivot
        if (arr[j] <= pivot) {
            i++;  // Increment index of smaller element
            swap(&arr[i], &arr[j]);  // Swap the elements
        }
    }
    swap(&arr[i + 1], &arr[high]);  // Swap the pivot element with the element at i+1
    return (i + 1);  // Return the partitioning index
}

// Function to implement Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partition the array and get the partition index
        int pi = partition(arr, low, high);

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

int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Apply Quick Sort
    quickSort(arr, 0, n - 1);

    // Output the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Swap Two Elements

• The swap function exchanges the values of two variables using a temporary variable.

Function to Perform the Partitioning of the Array

• The partition function chooses the last element of the array as the pivot.
• It rearranges the elements in the array such that all elements less than the pivot come before it, and all elements greater than the pivot come after it.
• The pivot is then placed in its correct position in the sorted array.
• The function returns the index of the pivot.

Function to Implement Quick Sort

• The quickSort function is a recursive function that sorts the array by repeatedly partitioning the array and sorting the resulting sub-arrays.
• It continues to partition and sort until the base case is reached, where the sub-array has one or zero elements.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Quick Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 6
Enter 6 elements:
10 7 8 9 1 5
Sorted array: 1 5 7 8 9 10

Example Output (Already Sorted):

Enter the number of elements in the array: 5
Enter 5 elements:
1 2 3 4 5
Sorted array: 1 2 3 4 5

Conclusion

This C program demonstrates how to implement Quick Sort, an efficient sorting algorithm with an average time complexity of O(n log n). Quick Sort is widely used due to its efficiency and ability to sort large datasets. The program is a useful example for understanding the Quick Sort algorithm and its implementation in C programming.