C Exercises: Sort numbers using partition sort method

Last update on November 17 2023 13:05:38 (UTC/GMT +8 hours)

C Programming Searching and Sorting Algorithm: Exercise-21 with Solution

Write a C program that sorts numbers using the partition sort method.

Partition-exchange sort is an efficient sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.

Sample Solution:

Sample C Code:

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

// Function to swap two values
void swap_val(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

// Function to partition the array and return the pivot index
int partition(int arra_nums[], int low, int high) {
    int pivot = arra_nums[low];
    int i = low - 1, j = high + 1;

    while (1) {
        // Find leftmost element >= pivot
        do {
            i++;
        } while (arra_nums[i] < pivot);

        // Find rightmost element <= pivot
        do {
            j--;
        } while (arra_nums[j] > pivot);

        // If two pointers met
        if (i >= j)
            return j;

        // Swap elements at i and j
        swap_val(&arra_nums[i], &arra_nums[j]);
    }
}

// Recursive function to perform partition sort
int* partitionSort(int arra_nums[], int low, int high) {
    if (low < high) {
        // Get the pivot index
        int value = partition(arra_nums, low, high);
        // Recursively sort the two sub-arrays
        partitionSort(arra_nums, low, value);
        partitionSort(arra_nums, value + 1, high);
        return arra_nums;
    }
}

// Main function
int main() {
    int arra_nums[100], i, size=0;    
    // Input the number of elements
    printf("Input number of elements you want to sort: ");
    scanf("%d", &size);
    printf("\nInput the numbers:\n");    
    for (i = 0; i < size; i++)
        scanf(" %d", &arra_nums[i]);

    // Check if there is at least one element
    if (size >= 1) {
        // Call the partitionSort function to sort the array
        int* result_arra = partitionSort(arra_nums, 0, size-1);

        // Display the sorted array
        printf("Sorted Array: \n");
        for (i = 0; i < size; i++) {
            printf("%d ", result_arra[i]);
        }
        printf("\n");
    }

    return 0;
}

Sample Output:

Input number of elements you want to sort: 5

Input the numbers:
10 15 20 25 30 35 40 45
Sorted Array:
10 15 20 25 30
--------------------------------
Process exited after 18.03 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

Previous: Write a C program that sort numbers using Pigeonhole sort method.
Next:Write a C program that sort numbers using Pancake sort method.