C Exercises: Sort numbers using Quick Sort method

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

Write a C program that sorts numbers using the QuickSort method.

Note: According to Wikipedia "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. Inefficient implementations it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quick sort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting."

Sample Solution:

Sample C Code:

// Shell Sort Implementation
// Source: https://bit.ly/2rcvXK5
#include <stdio.h>
// Function to perform shell sort on an array
void shell_sort(int *a, int n) {
    int h, i, j, t;
    // Iterate over different values of h (gap sequence)
    for (h = n; h /= 2;) {
        // Iterate through the array with the current gap h
        for (i = h; i < n; i++) {
            t = a[i];
            // Insertion sort within the subarrays created by the gap
            for (j = i; j >= h && t < a[j - h]; j -= h) {
                a[j] = a[j - h];
            }
            // Place the current element in its correct position
            a[j] = t;
        }
    }
}
// Main function
int main(int ac, char **av) {
    // Input array
    int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
    int n = sizeof a / sizeof a[0];
    int i;
    // Display original array
    printf("Original Array:\n");
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    // Sort the array using shell sort
    shell_sort(a, n);
    // Display sorted array
    printf("\nSorted Array:\n");
    for (i = 0; i < n; i++)
        printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
    return 0;
}

Sample Output:

Original Array:
4 65 2 -31 0 99 2 83 782 1

Sorted Array:
-31 0 1 2 2 4 65 83 99 782

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using shell sorting method.
Next: Write a C program that sort numbers using Bead Sort method.