Thread: Bubblesorting Array elements

Originally Posted by Hodor

Code:

void dodgybubblesort(int a[], size_t n)
{
    size_t i, j;
    for (i = n - 1; i > 0; --i) {
        for (j = 0; j < i; ++j) {
            if (a[j + 1] < a[j]) {
                int t = a[j];   /* Swap */
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

This definitely looks like a better candidate for a bubble sort, and it looks like it was taken directly (with expansion of the swap function/macro) from your "Bubble sort misconceptions" link under the introduction of "Actual bubble sort looks like this:".

Let's compare this to wufflz's code from post #1, with variable renaming, reformatting, etc for easier equivalence checking:

Code:

void arraySortieren(int a[], size_t n)
{
    size_t i, j;
    for (int i = n; i > 1; --i) {
        for (int j = 0; j < n - 1; ++j) {
            if (a[j] < a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

In your version, the outer loop starts i from n-1 and loops down until it reaches 0, whereas in wufflz's version, i starts from n and loops down until it reaches 1. Because wufflz's code is extra inefficient in that it doesn't use i in the inner loop, this makes the outer loop effectively identical to yours: its only function is to loop n-1 times, so we could just as well have changed it to your version.

In your version, the inner loop loops j from 0 to i. In wufflz's version, the inner loop loops j from 0 to n-1. What this means is that whatever swaps occur will be exactly the same in the same order. wufflz's version just does extra unnecessary comparison of items that have already been sorted.

Consequently, it looks like these two sorts are the same kind of sort, whatever it is.

Originally Posted by laserlight

This definitely looks like a better candidate for a bubble sort, and it looks like it was taken directly (with expansion of the swap function/macro) from your "Bubble sort misconceptions" link under the introduction of "Actual bubble sort looks like this:".

Let's compare this to wufflz's code from post #1, with variable renaming, reformatting, etc for easier equivalence checking:

Code:

void arraySortieren(int a[], size_t n)
{
    size_t i, j;
    for (int i = n; i > 1; --i) {
        for (int j = 0; j < n - 1; ++j) {
            if (a[j] < a[j + 1]) {
                int t = a[j];
                a[j] = a[j + 1];
                a[j + 1] = t;
            }
        }
    }
}

In your version, the outer loop starts i from n-1 and loops down until it reaches 0, whereas in wufflz's version, i starts from n and loops down until it reaches 1. Because wufflz's code is extra inefficient in that it doesn't use i in the inner loop, this makes the outer loop effectively identical to yours: its only function is to loop n-1 times, so we could just as well have changed it to your version.

In your version, the inner loop loops j from 0 to i. In wufflz's version, the inner loop loops j from 0 to n-1. What this means is that whatever swaps occur will be exactly the same in the same order. wufflz's version just does extra unnecessary comparison of items that have already been sorted.

Consequently, it looks like these two sorts are the same kind of sort, whatever it is.

I agree. Wufflz's version is more like a bubble sort without the "early exit". Since reading your comments and various books and web discussions I've decided that you are correct and that a bubble sort does not have to terminate when no exchanges/swaps occur (although Knuth does define it this way). The more important difference is how the two loops step, as mentioned in a previous post. So, I now think that Wufflz's original post is just a sub-optimal bubble sort, despite my earlier assertion. I also now think that if both the inner and outer loop increment (instead of one increment and the other decrement) then it's an insertion sort. I do read what you and others say and appreciate it. I've learned something over the last few days only because you and some others have spoken up. I was wrong at the start of this thread, but correct in the other thread. It was not until you questioned whether or not "terminating after no exchanges occur" that I even contemplated looking at these two algorithms more closely. So, that's a good thing, right? But after drawing them on paper and looking at the descriptions I am convinced that they really are different. Does it matter? If one was to poorly implement the in-place insertion sort then it doesn't matter at all because a poorly implemented insertion sort (which my code does) and a poorly implemented bubble sort end up being almost the same thing... except maybe for CPU pipelining etc but I'm not concerned about that.

At the start of this thread I was confused because I still had the other thread from the other day in my head. I was still confused until I got home from work and drew all this stuff on paper. I actually think that when I was taught bubble sort I was actually taught insertion sort! I guess I don't think about this much because it's very rare these days that I'd do either, but from memory I was probably taught insertion sort (but being told it was bubble sort). Ugh

Edit: They're both in-place exchange sorts, of course and I guess that's why if you don't implement them properly they kind of end up being very similar (in terms of time complexity if ignoring CPU pipelining stuff), but the order of exchanges is certainly different

Edit 2: Personally I think that what @Zeus_ wrote is more intuitive and if I was asked to write a bubble sort that's kinda similar to how I'd do it. I'm just not convinced that it's a bubble sort now because of what I've read about insertion sort

Originally Posted by Hodor

Edit 2: Personally I think that what @Zeus_ wrote is more intuitive and if I was asked to write a bubble sort that's kinda similar to how I'd do it. I'm just not convinced that it's a bubble sort now because of what I've read about insertion sort

As in Zeus_'s post #10? That's a bubble sort. It is equivalent to the Wikipedia bubble sort article's "Optimizing bubble sort" first example pseudocode, except that instead of just decrementing Size after each iteration of the inner loop, Zeus_ went to extra lengths to compute the inner loop limit for j from Size minus an incrementing outer loop counter, but it is still equivalent.

Oh, I missed this:

Originally Posted by Zeus_

The other post of mine was written in a hurry so I didn't bother optimising it. I think this is the most optimal it gets but don't know for sure.

It isn't because the inner loop always loops in successively smaller iterations, whereas you can terminate the inner loop at the point of the last swap in the previous iteration.

That said, optimising bubble sort is like upgrading your bicycle to compete in a Formula One race.

Originally Posted by Zeus_

Also, @laserlight, are XOR swaps faster?

Don't bother with them in the first place. If you must, then measure, but even if it were faster, no reasonable programmer would optimise bubble sort by using XOR swap when they can switch to a faster sorting algorithm.

Originally Posted by Hodor

All I know is that this afternoon I drew the two versions ([a] inner and outer loops both incrementing vs. [b] inner loop incrementing and outer loop decrementing) and they're different, with the latter [b] being bubble sort). Different because the former doesn't "bubble" the values.

You probably tested with an inner loop condition of j < i, whereas Zeus_'s version has the inner loop condition of j < n - i - 1. That subtraction means that an increasing outer loop is like a decreasing outer loop with j < i for the inner loop.