C Exercises: Sort numbers using Randomised quick sort method

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

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

From Wikipedia:
A simple example is randomized QuickSort, where the pivot is chosen randomly, and divides the elements into three partitions: elements less than pivot, elements equal to pivot, and elements greater than pivot. The randomized QuickSort require a lot of resources but always generate the sorted array as an output.
It is obvious that QuickSort always generates the solution which in this case the sorted array. Unfortunately, the time complexity is not that obvious. It turns out that the running time depends on which element we pick as a pivot.

Sample Solution:

Sample C Code:

// Source: https://bit.ly/325j5aY
# include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Function to find the first element greater than pivot
int getBig(int *a, int i, int right, int pivot) {
    for (int k = i; k <= right; k++) {
        if (a[k] > pivot)
            return k;
    }
    return right + 1;
}

// Function to find the first element smaller than pivot
int getSmall(int *a, int j, int left, int pivot) {
    for (int k = j; k >= left; k--) {
        if (a[k] < pivot)
            return k;
    }
    return -1;
}

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

// Function to perform random quicksort
void random_quick(int *a, int left, int right) {
    // Base case: if the array has one or zero elements, it is already sorted
    if (left >= right)
        return;

    // Choose a random pivot element
    int index = left + (rand() % (right - left));
    int i = left, j = right;
    int pivot_index = index;
    int pivot = a[index];

    // Find the index of the first element greater than pivot from the left
    i = getBig(a, i, right, pivot);

    // Find the index of the first element smaller than pivot from the right
    j = getSmall(a, j, left, pivot);

    // Partition the array into elements smaller and greater than the pivot
    while (i <= j) {
        swap(&a[i], &a[j]);
        i = getBig(a, i, right, pivot);
        j = getSmall(a, j, left, pivot);
    }

    // After partitioning, three cases are possible based on the pivot_index
    if (pivot_index > j && pivot_index > i) {
        // Case 1: Pivot index is greater than both i and j
        swap(&a[i], &a[pivot_index]);
        random_quick(a, left, i - 1);
        random_quick(a, i + 1, right);
    } else if (pivot_index < j && pivot_index < i) {
        // Case 2: Pivot index is smaller than both i and j
        swap(&a[j], &a[pivot_index]);
        random_quick(a, left, j - 1);
        random_quick(a, j + 1, right);
    } else {
        // Case 3: Pivot element is at its original position
        random_quick(a, left, pivot_index - 1);
        random_quick(a, pivot_index + 1, right);
    }
}

// Main function
int main() {
    srand(time(0));
    int num;

    // Input the number of elements
    printf("Input number of elements you want to sort: ");
    scanf("%d", &num);

    // Check if there is at least one element
    if (num >= 1) {
        printf("\nInput the numbers:\n");

        // Input the array elements
        int *arr = (int *)malloc(num * sizeof(int));
        for (int i = 0; i < num; i++) {
            scanf("%d", &arr[i]);
        }

        // Call the random_quick function to sort the array
        random_quick(arr, 0, num - 1);

        // Display the sorted array
        printf("\nSorted array: ");
        for (int i = 0; i < num; i++) {
            printf("%d ", arr[i]);
        }

        // Free the dynamically allocated memory
        free(arr);
    }

    printf("\n");

    return 0;
}

Sample Output:

Input number of elements you want to sort: 5

Input the numbers:
10 20 30 40 50 60 70 80 90

Sorted array: 10 20 30 40 50

--------------------------------
Process exited after 25.93 seconds with return value 0
Press any key to continue . . .

Flowchart:

C Programming Code Editor:

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