Program Explanation

Quick Sort is a highly efficient sorting algorithm that uses the divide-and-conquer principle.
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.

Program Structure

The program consists of the following main components:

• Partition Function: This function takes the last element as a pivot,
  places the pivot element at its correct position in the sorted array,
  and places all smaller (smaller than pivot) to the left and all greater elements to the right.
• Quick Sort Function: This function recursively sorts the sub-arrays.
• Main Function: This is where the program execution begins.
  It initializes the array and calls the Quick Sort function.

C Code

#include 

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

// Partition function
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++; // Increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Quick Sort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partitioning index
        int pi = partition(arr, low, high);

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

// Main function
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("Unsorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}
        

How to Compile and Run

To compile the program, use a C compiler such as gcc.
Save the code in a file named quick_sort.c and run the following commands in your terminal:

gcc quick_sort.c -o quick_sort
./quick_sort

Output

The program will output the unsorted and sorted array:

Unsorted array: 10 7 8 9 1 5 
Sorted array: 1 5 7 8 9 10