Bubble Sort Recursively

Question

I have searched Google and I cannot find anything for this. I was looking for various types of sorts (as you can see in a previous question of mine) and I was wondering if anyone knew of a recursive bubble sort code. To me, the idea sounds ridiculous, but I want to be prepared for things and I'm curious as to whether or not this can be done. I'm sure it can, as a professor of mine has asked this of his students in the past. I don't think he'll repeat questions, but I became curious and wanted to know if there was code for a bubble sort recursively.

Duplicate? http://stackoverflow.com/questions/1644440/bubble-sort-using-recursion-in-c — BeemerGuy, Dec 16 '10 at 01:16
I wouldn't think that you'd want to - one of the advantages of bubble sort is that it has a low memory overhead. You could make it trivially recursive, such as having the algorithm switch two values then recurse. — Sam Dufel, Dec 16 '10 at 01:24
This is true, and I couldn't imagine one would want to do so earlier. It was more for curiosity. — muttley91, Dec 16 '10 at 04:12
Bubble sort is generally defined as an iterative algorithm. It could trivially be converted into a recursive form, but that would likely make it less efficient, and it's already not the sharpest tack in the shoe in that regard... So, the question "why?" does indeed come to mind... — twalberg, Aug 26 '15 at 20:49

score 0 · Answer 1 · answered Aug 26 '15 at 19:29

It's certainly possible to do this, since any iterative algorithm can be converted to a recursive one and vice-versa.

Here's one way that we can do this. For simplicity, I'm using C++ and assuming the inputs are all integers.

void bubbleSort(std::vector<int>& list) {
    /* Make one pass of swapping elements. If anything was swapped,
     * repeat this process.
     */
    if (swapPass(list)) {
        bubbleSort(list);
    }
}

/* Does a pass over the array, swapping adjacent elements if they're
 * out of place. Returns true if anything was swapped and false
 * otherwise.
 */
bool swapPass(std::vector<int>& list) {
    return recSwapPass(list, 0, false);
}

/* Does a swap pass starting from index given information about
 * whether a swap was made on the pass so far. Returns true if across
 * the entire pass a swap was made and false otherwise.
 */
bool recSwapPass(std::vector<int>& list, unsigned index,
                 bool wasSwapped) {
    /* Base case: If we're at the end of the array, then there's
     * nothing to do and we didn't swap anything.
     */
    if (index + 1 >= list.size()) return wasSwapped;

    /* Compare the current element against the next one and see if
     * they need to swap.
     */
    if (list[index] > list[index + 1]) {
        std::swap(list[index], list[index + 1]);
        return recSwapPass(list, index + 1, true);
    } else {
        return recSwapPass(list, index + 1, wasSwapped);
    }
}

Interestingly, every recursive function here is tail-recursive, so a good optimizing compiler should be able to generate non-recursive code. In other words, a good compiler should generate pretty much the same code as if we'd written this iteratively. If I get the time, I'll check out whether this actually happens. :-)

Bubble Sort Recursively

1 Answers1