C Program: Quick Sort in Ascending Order

1. Introduction

Quick Sort is a divide-and-conquer sorting algorithm, known for its impressive average-case performance. 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.

2. Program Overview

The program is structured as:

1. partition: A function that takes the array and positions of the start and end elements. It selects a pivot, partitions the array around the pivot, and returns the pivot's position.

2. quickSort: The main function that implements the Quick Sort algorithm by recursively calling itself.

3. printArray: A utility function to display the contents of the array.

4. main: The primary function where program execution starts.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

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

// This function takes the last element as pivot, places it in its correct position
// and places all smaller elements to the left and all greater elements to the right
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 or equal to pivot
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Main Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pivot is partitioning index, arr[pivot] is now at the right place
        int pivot = partition(arr, low, high);

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

// Function to print the array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver program to test above functions
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array is \n");
    printArray(arr, n);
    return 0;
}

Output:

Given array is
10 7 8 9 1 5
Sorted array is
1 5 7 8 9 10

4. Step By Step Explanation

1. quickSort begins by calling the partition function. This function chooses a pivot (in our case, the last element) and ensures that elements less than or equal to the pivot are on its left, and those greater than the pivot are on its right.

2. Once the pivot is placed at its correct position, the quickSort function is called recursively for the two halves: elements less than the pivot and elements greater than the pivot.

3. This process continues recursively, breaking down the array into smaller and smaller sub-arrays, each time placing the pivot at its correct position.

4. The swapping of elements is done in place, so no additional storage is required.

5. As the recursion unwinds, you're left with a fully sorted array.

Quick Sort's efficiency comes from the fact that on average (for random pivots), the algorithm divides the array into nearly two equal parts, leading to an average-case time complexity of O(n log n).

Related C Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in C
2. Bubble Sort in Descending Order in C
3. Selection Sort in Ascending Order in C
4. Selection Sort in Descending Order in C
5. Insertion Sort in Ascending Order in C
6. Insertion Sort in Descending Order in C
7. Merge Sort in Ascending Order in C
8. Merge Sort in Descending Order in C
9. Quick Sort in Ascending Order in C
10. Quick Sort in Descending Order in C
11. Heap Sort in Ascending Order in C
12. Heap Sort in Descending Order in C