2
\$\begingroup\$

I often see nested loops as a solution to the bubble sort, but my solution involves a recursive function. Is the following solution less efficient than the traditional method?

public static int[] BubbleSort(int[] arrayOfValues)
{
    var swapOccurred = false;
    
    for (var i = 0; i < arrayOfValues.Length; i++)
    {
        if (i == arrayOfValues.Length - 1)
            continue;

        if (arrayOfValues[i] > arrayOfValues[i + 1])
        {
            //swap values
            var current = arrayOfValues[i];
            var next = arrayOfValues[i + 1];
            
            arrayOfValues[i] = next;
            arrayOfValues[i + 1] = current;

            swapOccurred = true;
        }
    }

    if (swapOccurred)
    {
        // keep going until no further swaps are required:
        BubbleSort(arrayOfValues);
    }

    return arrayOfValues;
}
\$\endgroup\$
1
  • 3
    \$\begingroup\$ If it's recursive anything you can almost bet that it's less efficient the the iterative version of anything. It's much more interesting to find out why some particular recursive implementations of something are actually not less efficient then their iterative versions. \$\endgroup\$ Commented Apr 22, 2021 at 3:34

2 Answers 2

Reset to default
3
\$\begingroup\$

Less efficient? It consumes more stack space, which shouldn’t be a problem for any dataset where a bubble sort would be appropriate.

With the latest version of the c# compiler, tuple deconstruction will allow you to swap the values with a single line of code (although it will probably be slower).

On a side note, I’m not clear on why you have a separate continue instead of having a lower conditional check. It’s the same thing.

Not sure if you know this, but you are examining already sorted elements with your recursive call. An “efficient” bubble sort moves the end position back one cell after each cycle.

Update: I did some rough testing your implementation, and get a stack overflow a bit after 8k items. Sorting 8k random numbers without reducing the end point took ~.75 seconds, sorting with reducing the end point took ~.70 seconds. Much better than I expected. Using Moch Yusup modification to use a more traditional structure the time for 8k items was approximately the same, but it took 116.8 seconds for 80k items.

So, performance wise, within the usable range, recursion was functionally identical, but due to stack overflow the usable range is limited. OTOH, the usable range and "not enough time to go get a cup of coffee" range are fairly close.

Just for comparison, I tried using the standard List.Sort method, which took .0003681 seconds for 8k items, and .006 seconds for 80k items...

\$\endgroup\$
11
  • \$\begingroup\$ Yes, I think a conditional check would be better - I just wanted to prevent the comparison from going outside of the bounds of the array. Thanks, I guess stack space would be a consideration. \$\endgroup\$ Commented Apr 22, 2021 at 3:50
  • \$\begingroup\$ @Alex: if you want to do something different, note that your recursion is basically a GOTO with a parameter and if C# did support tailrecursion that’s what it would look like... \$\endgroup\$ Commented Apr 22, 2021 at 11:08
  • \$\begingroup\$ Thanks for the feedback. \$\endgroup\$ Commented Apr 22, 2021 at 13:37
  • 1
    \$\begingroup\$ In languages that do not natively compile recursions into loops (C# versus functional languages like F#) there is always the issue of a StackOverflow with recursions. If you sort 100.000 elements with your algorithm it probably crashes. Would you use a loop you could sort millions of elements without any problem. \$\endgroup\$ Commented Apr 23, 2021 at 1:43
  • \$\begingroup\$ @Christoph: yeah, but it’s bubble sort. I wouldn’t want to sort much more than 1000 elements under any circumstances. 10k would likely be extremely slow. \$\endgroup\$ Commented Apr 23, 2021 at 11:35
3
\$\begingroup\$

IMHO - I usually use recursive to break down a complex loop code into a simpler and smaller code. So if the function I end up created is still a complex one I'd rather use loop instead. In your case it's simpler and easier to do loop instead of recursion.

public static int[] BubbleSort(int[] arrayOfValues)
{
    bool swapOccurred;
    do
    {
        swapOccurred = false;
        for (var i = 0; i < arrayOfValues.Length - 1; i++)
        {
            if (arrayOfValues[i] <= arrayOfValues[i + 1]) 
                continue;
        
            (arrayOfValues[i], arrayOfValues[i + 1]) = (arrayOfValues[i + 1], arrayOfValues[i]);
            swapOccurred = true;
        }
    } while (swapOccurred);
    return arrayOfValues;
}

The code above is written in c# 9.

So yes, I think it's less efficient doing it with recursive in this case in my opinion.

I usually ask these questions before I use recursive code:

  • Will it be simpler if I use recursive?
  • Does the code loop for small number of times? Because if it does like thousands loop then it may be detected as Stack Overflow.
\$\endgroup\$
1
  • \$\begingroup\$ Ah I like this! The do-while is much cleaner and has the same intent as my recursive function. Thanks. \$\endgroup\$ Commented Apr 24, 2021 at 0:24

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.