bubble sort recursively without loops

Question

is it even possible to do bubble sort without any global/static variables, only one array and without a loops? I am wondering is it possible and if so, is it hard?

my function would only take array with numbers and size of it.

int bubble_sort_asc_rec(int tab[], int size)

Answer 1

#include <stdio.h>

int bubble_sort_pass(int array[], int size)
{
    /* We return the number of swaps in this iteration. */
    int swaps = 0;

    /* If the array contains 0 or 1 elements, it is already sorted. */
    if (size < 2) {
        return swaps;
    }

    /* Array contains at least 2 elements. */
    if (array[0] > array[1]) {
        /* First two elements are in wrong order. We need to swap them. */
        printf("Swap value %d with value %d\n", array[0], array[1]);
        int temp = array[0];
        array[0] = array[1];
        array[1] = temp;
        swaps += 1;
    }

    /* Recursively bubble sort the array starting at the 2nd element. */
    swaps += bubble_sort_pass(array + 1, size - 1);
    return swaps;
}

void bubble_sort(int array[], int size)
{
    /* Do one pass of bubble sorting the entire array. */
    printf("Start a bubble sort pass.\n");
    int swaps = bubble_sort_pass(array, size);

    /* If there was at least one swap, we have to do another pass. */
    if (swaps >= 1) {
        bubble_sort(array, size);
    }

}


int main()
{
    int numbers[] = {10, 8, 3, 7, 2, 1, 4, 6, 5, 9};
    int count = sizeof(numbers) / sizeof(numbers[0]);
    bubble_sort(numbers, count);
    for(int i=0; i<count; ++i) {
        printf("numbers[%d] = %d\n", i, numbers[i]);
    }
    return 0;
}

In C you would not normally implement bubble sort this way; instead you would use an iterative approach (i.e. loops).

This recursive implementation is strictly for instructional purposes. Some so-called "pure functional" languages do not have any loops, they only have recursion. One such language is Erlang.

Note that the recursive call to bubble_sort is the last statement in bubble_sort. This is called "tail recursion" and it allows the compiler to optimize out pushing a return address on the stack. The C compiler (likely) will not make such a tail recursion optimization, but a functional compiler (e.g. an Erlang compiler) will.

The recursive call to bubble_sort_pass in bubble_sort_pass is currently not a tail recursion call, but it could easily be changed into a tail recursion call (verify this for yourself!)