C Program to Implement Quick Sort

1. Introduction

Quick Sort is a divide-and-conquer algorithm that 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 recursively sorted.

2. Program Overview

In this program, we will:

1. Implement the partition function to select a pivot and partition the array around it.

2. Implement the recursive quickSort function.

3. Sort an array of integers using Quick Sort.

4. Display the sorted array.

3. Code Program

#include <stdio.h>

// Swap function to swap values of two integers
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Partition function for the Quick Sort
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Choosing the pivot as the highest element
    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);
}

// Recursive function to perform the Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pivot
        quickSort(arr, pi + 1, high); // After pivot
    }
}

// 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 code
int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    quickSort(arr, 0, n - 1);

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

    return 0;
}

Output:

Original array:
10 80 30 90 40 50 70
Sorted array:
10 30 40 50 70 80 90

4. Step By Step Explanation

1. The swap function is a utility function to swap two integers.

2. The partition function is the key to the quick sort algorithm. It selects the pivot, rearranges the array elements so that elements less than the pivot come before the pivot, and elements greater come after. It then returns the pivot's index.

3. The quickSort function is a recursive function that sorts the elements before the pivot and after the pivot.

4. The printArray function is a utility function to display the elements of the array.

5. The main function initializes an array, prints it, sorts it using quick sort, and then prints the sorted array.

Quick Sort, in the average case, offers performance close to O(n log n), making it efficient for larger datasets. However, its worst-case time complexity is O(n^2), which occurs when the array is already sorted or in reverse order.