s C Program: Sort numbers using partition sort method - w3resource
w3resource

C Exercises: Sort numbers using partition sort method

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:

Flowchart: C Programming - Sort numbers using partition sort method.

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.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/c-programming-exercises/searching-and-sorting/c-search-and-sorting-exercise-26.php