Recursive BubbleSort vs normal BubbleSort

Question

I have coded 2 bubblesort algorithms. One is without recursion, the other is with recursion. I am interested on knowing which of these two are more efficient and with and explain why.

Recursive bubbleSort:

private static int list[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

public int[] recursiveBubble(int[] args, int startIndex, int endIndex) {
    if(startIndex > endIndex){
        System.out.println("Recursive bubblesort:");
        System.out.println(Arrays.toString(args));
        return args;
    }

    if (startIndex == endIndex - 1) {
        recursiveBubble(args, 0, endIndex - 1);
    } else if (args[startIndex] > args[startIndex+1]) {
        int currentNumber = args[startIndex];
        args[startIndex] = args[startIndex + 1];
        args[startIndex + 1] = currentNumber;

        recursiveBubble(args, startIndex + 1, endIndex);
    } else  {
        recursiveBubble(args, startIndex + 1, endIndex);
    } 
    return args;
}

BubbleSort using loops:

 public int[] bubblesort(int[] args) {
    System.out.println("Normal BubbleSort:");
    for (int j = 0; j < args.length; j++) {
        for (int i = 0; i < args.length; i++) {
            int currentNumber = args[i];
            if (i + 1 < args.length) {
                if (currentNumber > args[i + 1]) {
                    args[i] = args[i + 1];
                    args[i + 1] = currentNumber;
                }
            }
        }
    }
    System.out.println(Arrays.toString(args));
    return args;
}

Possible duplicate: http://stackoverflow.com/questions/72209/recursion-or-iteration — Simon Arsenault, Oct 02 '13 at 15:29
This isn't the forum for such a question - try [Code Review](http://codereview.stackexchange.com/). — Boris the Spider, Oct 02 '13 at 15:29
@SimonArsenault it's worth noting that javac does not do tail-recursion optimisation and that the above method is not tail-recursive in any case. — Boris the Spider, Oct 02 '13 at 15:31

score 3 · Accepted Answer · answered Oct 02 '13 at 15:33

3

I am not sure what you mean by which is better but bubble sort must inherently have a best and worst case performance time by nature of the way the algorithm works. Best case O(n) worst case O(n^2) see http://en.wikipedia.org/wiki/Bubble_sort . Iteration vs. recursion shouldn't make too much of a difference. I suppose recursion will take up more stack memory. Recursion tends to be harder to write and trace than iteration. Since there is no time benefit if both are actual bubble sort implementations I would stick to iteration.

answered Oct 02 '13 at 15:33

ford prefect

7,096
11
56
83

Okay, well basically I mean which one runs the quickest. Since I'm unable to find out on netbeans the runtime. It will just say 0 seconds. So I just want to know which one achieves the goal the quickest during run time. – JP24 Oct 02 '13 at 15:35
Though you are right that the performance of the algorithm with best case and worst case will tend to not change. – JP24 Oct 02 '13 at 15:36
If you have coded it correctly the difference _should_ be negligible. Try running it on a huge data set and profiling but I would be surprised to see a big difference. Is this homework? http://stackoverflow.com/questions/895371/bubble-sort-homework?rq=1 – ford prefect Oct 02 '13 at 15:39
No, this is just me practicing as much Java as I can during my spare time. This is the first time i've used recursion as well lol. Glad it's working. :D – JP24 Oct 02 '13 at 15:49
A better way to practice might be to look up factorial or implementing a binary search tree and searching that. Tree structure search and parsing is a common use of recursion and something I do in my work. Or an inherently recursive sort such as merge sort – ford prefect Oct 02 '13 at 15:51
Right, I'll give that a go. I basically decided to start off small with bubblesort since it's not such a complex algorithm but now that it works I'm going to go on to code more complex algorithms using recursion. The ones I've done so far all have loops. – JP24 Oct 02 '13 at 15:53
If you like the answer though feel free to give it a bump – ford prefect Oct 02 '13 at 15:55

score -1 · Answer 2 · answered Oct 02 '13 at 16:05

In the above example you are more less replacing loops to recursion. In java recursive version is possibly not good because it can lead a stackoverflow error based on long array length. complexity wise I don't see any difference. IF you compare memory management of JVM then recursive version is going to take more space in memory than your normal loop one. if you increase length of your variable you may notice that difference or you may encounter an stackoverflow exception based on allocated size for your memory generations.

Recursive BubbleSort vs normal BubbleSort

2 Answers2