Quick Sort in Descending Order in C

1. Introduction

Quick Sort is a versatile divide-and-conquer sorting algorithm, celebrated for its robust average-case performance. In essence, it works by choosing a 'pivot' element from the array and subsequently partitioning the other elements into two sub-arrays based on whether they are greater than or less than the pivot. Subsequently, these sub-arrays are sorted recursively.

2. Program Overview

The program comprises:

1. partition: A function that takes the array and the starting and ending positions. It then chooses a pivot, partitions the array around this pivot, and finally returns the pivot's exact position.

2. quickSort: The pivotal function that embodies the Quick Sort algorithm and recursively calls itself.

3. printArray: A utility function designed to exhibit the array's contents.

4. main: The primary function, which signifies the commencement of the program.

3. Code Program

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

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

// This function, taking the last element as the pivot, ensures its apt positioning
// subsequently placing all larger elements to the left and all smaller ones to its right
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // defining the pivot
    int i = (low - 1);  // Index of larger element

    for (int j = low; j <= high - 1; j++) {
        // If the current element is larger than or equal to the pivot
        if (arr[j] >= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// The heart of Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // The pivot's partitioning index, wherein arr[pivot] is perfectly positioned
        int pivot = partition(arr, low, high);

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

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

// The main driver program
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    quickSort(arr, 0, n - 1);

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

Output:

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

4. Step By Step Explanation

1. The process starts with the quickSort function invoking the partition method. Here, a pivot is picked (in our instance, the last element). The function ensures elements larger or equal to the pivot lie to its left and those smaller are on its right.

2. With the pivot correctly positioned, the quickSort function is recursively evoked for the two segments: those greater than the pivot and ones less than the pivot.

3. This recursive approach fragments the array into smaller sub-arrays, with each iteration properly positioning the pivot.

4. The in-place swapping ensures no need for extra storage.

5. Once the recursion concludes, we obtain a completely sorted array.

The efficiency of Quick Sort arises due to its average-case scenario where the algorithm almost divides the array into two equal sections, resulting in an O(n log n) average-case time complexity.

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