C Exercises: Quick sort algorithm

Last update on December 20 2024 13:08:33 (UTC/GMT +8 hours)

Write a C program to sort a list of elements using the quick sort algorithm.

Note: Quick sort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.
Read n values into array and Sort using Quick Sort.

Visual presentation - Quick Sort algorithm:

Sample Solution:

Sample C Code:

#include<stdio.h>
int n; // Global variable to store the number of elements
int main() {
    int arr[30], l, r, i;
    // Function declaration
    void quick_sort(int arr[], int low, int high);
    // Input the number of elements
    printf("\nInput number of elements: ");
    scanf("%d", &n);
    // Input array values one by one
    printf("\nInput array values one by one: ");
    for (i = 0; i < n; i++)
        scanf("%d", &arr[i]);
    l = 0;
    r = n - 1;
    // Call the quick_sort function to sort the array
    quick_sort(arr, l, r);
    // Display the quick sorted array
    printf("\nThe quick sorted array is: ");
    for (i = 0; i < n; i++)
        printf(" %d", arr[i]);
    printf("\n");
    return 0;
}

// Function to perform quick sort on array arr[] from index low to high
void quick_sort(int arr[], int low, int high) {
    int temp, left, right, x, k;
    // Base case: If low is greater than or equal to high, return
    if (low >= high)
        return;
    else {
        x = arr[low];
        right = low + 1;
        left = high;
        // Partition the array
        while (right <= left) {
            // Find an element greater than x on the right side
            while (arr[right] < x && right <= high) {
                right++;
            }
            // Find an element smaller than x on the left side
            while (arr[left] > x && left > low) {
                left--;
            }
            // Swap the elements if right is less than left
            if (right < left) {
                temp = arr[right];
                arr[right] = arr[left];
                arr[left] = temp;
                right++;
                left--;
            }
        }
        // Swap the pivot (x) with the element at left
        arr[low] = arr[left];
        arr[left] = x;
        // Recursive calls for the two subarrays
        quick_sort(arr, low, left - 1);
        quick_sort(arr, left + 1, high);
    }
}

Sample Input:

3
12
15
56

Sample Output:

Input number of elements:  
Input  array values one by one: 
The quick sorted array is:   12 15 56

Flowchart:

C Programming Code Editor:

Click to Open Editor

Previous: Write a C program to sort numbers using heap algorithm(MAX heap).
Next: Write a C program to sort a list of elements using the radix sort algorithm.