C Exercises: Sort numbers using Stooge Sort method

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

Write a C program that sorts numbers using the Stooge Sort method.

Stooge sort is a recursive sorting algorithm with a time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...). The running time of the algorithm is thus slower compared to efficient sorting algorithms, such as Merge sort, and is even slower than Bubble sort.

Sample Solution:

Sample C Code:

# include <stdio.h>

// Function to perform Stooge Sort on an array
int* stooge_sort(int arr_nums[], int i, int j) {
    int temp_val, k;

    // Swap elements if they are in the wrong order
    if (arr_nums[i] > arr_nums[j]) {
        temp_val = arr_nums[i];
        arr_nums[i] = arr_nums[j];
        arr_nums[j] = temp_val;
    }

    // Base case: if the array has 2 or fewer elements, return the array
    if ((i + 1) >= j)
        return arr_nums;

    // Calculate the value of k
    k = (int)((j - i + 1) / 3);

    // Recursively apply Stooge Sort to the subarrays
    stooge_sort(arr_nums, i, j - k);
    stooge_sort(arr_nums, i + k, j);
    stooge_sort(arr_nums, i, j - k);

    return arr_nums;
}

// Main function
int main() {
    int arr[100], i, n = 0;

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

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

        // Input the array elements
        for (i = 0; i < n; i++)
            scanf(" %d", &arr[i]);

        // Call the stooge_sort function
        int* result_arra = stooge_sort(arr, 0, n - 1);

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

    return 0;
}

Sample Output:

Input number of elements you want to sort: 5

Input the numbers:
5 10 15 20 25 30 35 40 45 50
Sorted array:
5 10 15 20 25

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

Flowchart:

C Programming Code Editor:

Previous: Write a C program to sort a list of elements using the insertionsort algorithm.
Next: Write a C program that sort numbers using Randomised quick sort method.