4 ms·

Because it misses a crucial step, early exit if there were no swaps. This way it would be extremely efficient in case of already sorted data. You should probab

Because it misses a crucial step, early exit if there were no swaps. This way it would be extremely efficient in case of already sorted data. You should probably check wikipedia page. Here: https://en.wikipedia.org/wiki/Bubble_sort https://en.wikipedia.org/wiki/Bubble_sort.

jazzyjackson 3y ago
meh, an optimization, hardly "not working"
- SomeoneFromCA 3y ago
  It is not "an optimization", it is in the definition of Bubble Sort. What you have written is not a bubble sort, and therefore, by the fact of being not a bubble sort, is not a working bubble sort.
  - thaumasiotes 3y ago
    That's not part of the definition of bubble sort. It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.) The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.
    - SomeoneFromCA 3y ago
      It is in the definition in Wikipedia and most other sources I have checked. All the implementations I have seen so far, check if any swaps have happened, and stop if they have not.
      - kragen 3y ago
        not clrs
- SomeoneFromCA 3y ago
  In any case, you should retract you claim that Bubble Sort is slower on already sorted case. It is CS101, that bubble sort is one of the fastest in this case.
  - kragen 3y ago
    after i posted the below comment to say 'oh yeah, you're right, thanks' someonefromca, perhaps inadvertently, edited the parent to say something completely different from what i was agreeing with. it previously said that there was a bug in the insertion sort code because it would swap things repeatedly, which is true and is a bug. my reply to their original comment is below oh yeah, you're right, thanks, it does do useless extra work if there are equal values in the list it should say if (tmp >= a[j-1]) break; however, this doesn't make it fail to terminate, which is a possible reading of your bug report
kragen 3y ago
i think i wrote that page originally 22 years ago, before the switch from usemodwiki to mediawiki; while i've often been referred to wikipedia to correct my errors, i think this is the first time i've been referred to a wikipedia page that i wrote in the first place :) it's true that, if your data is exactly sorted, or has a small number of items that are far too early (e.g., 43 3 4 5 6 7 8 9 10), you can modify bubble sort to notice this and exit early, at the expense of making it more complicated and even slower in the average case however, this doesn't help if instead you have a small number of items that are far too late (e.g., 4 5 6 7 8 9 10 43 3), in which case bubble sort takes the same number of passes as it normally would, while insertion sort takes linear time. of course you can complicate bubble sort further into "shaker sort" to handle this, which makes it even more complicated but at least doesn't slow it down any further but all of this is sort of futile because it's still half as fast as insertion sort in the case of unsorted input, and even without the tweaks, no simpler
- SomeoneFromCA 3y ago
  I do not have access to the historic definition of bubble sort, but all the modern implentation i've seen so far, all have a check if there were no swaps. I absolutely cannot wrap my mind how exactly it would make it slower in the average case, I almost certain it won't, how exactly this would make code sgnificantly more complex to any meaningful extent.
  - kragen 3y ago
    we're talking about six lines of code if we don't count the curly braces (which can be omitted) bubble sort with early exit is for (size_t i = 0; i < n; i++) { bool sorted = 1; for (size_t j = 1; j < n - i; j++) { if (a[j-1] > a[j]) { item_t tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; sorted = 0; } } if (sorted) break; } which is three more lines of code, which is in some crude sense a complexity increase of 50% over both the simple bubble sort in my earlier comment and over insertion sort if you compile it https://godbolt.org/z/jdzov8cPn https://godbolt.org/z/jdzov8cPn you can see that the inner loop goes from 10 instructions to 11. that doesn't guarantee that it's 9% slower (that depends a lot on the platform, and in particular on a big superscalar cpu it probably just uses a little more power but the same number of clocks) but it does tend in that direction. of course occasionally it will save you a pass or two over the array, which will tend to compensate, but it won't usually save you 9% of the passes if some item is in position n and needs to be in position m, where m < n, it will require n - m passes of bubble sort to get there. a little thought suffices to show that, for randomly shuffled input, where m = 0 the item has to move about half the size of the array, where m = 1 it has to move about half the size of the array minus one half, where m = 2 it has to move about half the size of the array minus one; but it's the maximum of these three numbers which determines the number of passes after which all three of those positions will have the correct item, and that maximum is heavily skewed to be almost the entire size of the array. the chance that none of those three items is in the last 25% of the array originally is only .75*3 = 42%. and as the value of three increases, it gets worse. so in general early exit doesn't buy you much as for modern implementations of bubble sort, they're all either didactic classroom exercises like this one or careless mistakes like the original freebsd code; because insertion sort always beats it, there aren't like a community of bubble sort implementors who have annual bubble sort conferences. so you can expect some variation in precise terminology and shouldn't worry about it (fwiw clrs 3ed. gives bubblesort without an early termination test, as i did; their definition is in exercise 2-2 on p. 40. but they're counting in the opposite direction, so everything i said above about items moving forward quickly and backward slowly is reversed for the clrs version of bubblesort)
openasocket 3y ago
If you look at the actual change in FreeBSD (https://cgit.freebsd.org/src/commit/?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d https://cgit.freebsd.org/src/commit/?id=9a7add6d01f3c5f7eba8... ) you'll see that the implementation of bubble sort used in the FreeBSD kernel was not doing early exits. /* * * Perform a bubble sort of the system initialization objects by * their subsystem (primary key) and order (secondary key). */ TSENTER2("bubblesort"); for (sipp = sysinit; sipp < sysinit_end; sipp++) { for (xipp = sipp + 1; xipp < sysinit_end; xipp++) { if ((*sipp)->subsystem < (*xipp)->subsystem || ((*sipp)->subsystem == (*xipp)->subsystem && (*sipp)->order <= (*xipp)->order)) continue; /* skip*/ save = *sipp; *sipp = *xipp; *xipp = save; } } TSEXIT2("bubblesort");
- kragen 3y ago
  i very much appreciate you and erk posting this because we can also now see that it wasn't actually bubble sort but selection sort

jazzyjackson 3y ago

meh, an optimization, hardly "not working"

SomeoneFromCA 3y ago
It is not "an optimization", it is in the definition of Bubble Sort. What you have written is not a bubble sort, and therefore, by the fact of being not a bubble sort, is not a working bubble sort.
- thaumasiotes 3y ago
  That's not part of the definition of bubble sort. It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.) The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.
  - SomeoneFromCA 3y ago
    It is in the definition in Wikipedia and most other sources I have checked. All the implementations I have seen so far, check if any swaps have happened, and stop if they have not.
    - kragen 3y ago
      not clrs
SomeoneFromCA 3y ago
In any case, you should retract you claim that Bubble Sort is slower on already sorted case. It is CS101, that bubble sort is one of the fastest in this case.
- kragen 3y ago
  after i posted the below comment to say 'oh yeah, you're right, thanks' someonefromca, perhaps inadvertently, edited the parent to say something completely different from what i was agreeing with. it previously said that there was a bug in the insertion sort code because it would swap things repeatedly, which is true and is a bug. my reply to their original comment is below oh yeah, you're right, thanks, it does do useless extra work if there are equal values in the list it should say if (tmp >= a[j-1]) break; however, this doesn't make it fail to terminate, which is a possible reading of your bug report

kragen 3y ago

i think i wrote that page originally 22 years ago, before the switch from usemodwiki to mediawiki; while i've often been referred to wikipedia to correct my errors, i think this is the first time i've been referred to a wikipedia page that i wrote in the first place :) it's true that, if your data is exactly sorted, or has a small number of items that are far too early (e.g., 43 3 4 5 6 7 8 9 10), you can modify bubble sort to notice this and exit early, at the expense of making it more complicated and even slower in the average case however, this doesn't help if instead you have a small number of items that are far too late (e.g., 4 5 6 7 8 9 10 43 3), in which case bubble sort takes the same number of passes as it normally would, while insertion sort takes linear time. of course you can complicate bubble sort further into "shaker sort" to handle this, which makes it even more complicated but at least doesn't slow it down any further but all of this is sort of futile because it's still half as fast as insertion sort in the case of unsorted input, and even without the tweaks, no simpler

SomeoneFromCA 3y ago
I do not have access to the historic definition of bubble sort, but all the modern implentation i've seen so far, all have a check if there were no swaps. I absolutely cannot wrap my mind how exactly it would make it slower in the average case, I almost certain it won't, how exactly this would make code sgnificantly more complex to any meaningful extent.
- kragen 3y ago
  we're talking about six lines of code if we don't count the curly braces (which can be omitted) bubble sort with early exit is for (size_t i = 0; i < n; i++) { bool sorted = 1; for (size_t j = 1; j < n - i; j++) { if (a[j-1] > a[j]) { item_t tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; sorted = 0; } } if (sorted) break; } which is three more lines of code, which is in some crude sense a complexity increase of 50% over both the simple bubble sort in my earlier comment and over insertion sort if you compile it https://godbolt.org/z/jdzov8cPn https://godbolt.org/z/jdzov8cPn you can see that the inner loop goes from 10 instructions to 11. that doesn't guarantee that it's 9% slower (that depends a lot on the platform, and in particular on a big superscalar cpu it probably just uses a little more power but the same number of clocks) but it does tend in that direction. of course occasionally it will save you a pass or two over the array, which will tend to compensate, but it won't usually save you 9% of the passes if some item is in position n and needs to be in position m, where m < n, it will require n - m passes of bubble sort to get there. a little thought suffices to show that, for randomly shuffled input, where m = 0 the item has to move about half the size of the array, where m = 1 it has to move about half the size of the array minus one half, where m = 2 it has to move about half the size of the array minus one; but it's the maximum of these three numbers which determines the number of passes after which all three of those positions will have the correct item, and that maximum is heavily skewed to be almost the entire size of the array. the chance that none of those three items is in the last 25% of the array originally is only .75*3 = 42%. and as the value of three increases, it gets worse. so in general early exit doesn't buy you much as for modern implementations of bubble sort, they're all either didactic classroom exercises like this one or careless mistakes like the original freebsd code; because insertion sort always beats it, there aren't like a community of bubble sort implementors who have annual bubble sort conferences. so you can expect some variation in precise terminology and shouldn't worry about it (fwiw clrs 3ed. gives bubblesort without an early termination test, as i did; their definition is in exercise 2-2 on p. 40. but they're counting in the opposite direction, so everything i said above about items moving forward quickly and backward slowly is reversed for the clrs version of bubblesort)

openasocket 3y ago

If you look at the actual change in FreeBSD (https://cgit.freebsd.org/src/commit/?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d https://cgit.freebsd.org/src/commit/?id=9a7add6d01f3c5f7eba8... ) you'll see that the implementation of bubble sort used in the FreeBSD kernel was not doing early exits. /* * * Perform a bubble sort of the system initialization objects by * their subsystem (primary key) and order (secondary key). */ TSENTER2("bubblesort"); for (sipp = sysinit; sipp < sysinit_end; sipp++) { for (xipp = sipp + 1; xipp < sysinit_end; xipp++) { if ((*sipp)->subsystem < (*xipp)->subsystem || ((*sipp)->subsystem == (*xipp)->subsystem && (*sipp)->order <= (*xipp)->order)) continue; /* skip*/ save = *sipp; *sipp = *xipp; *xipp = save; } } TSEXIT2("bubblesort");

kragen 3y ago
i very much appreciate you and erk posting this because we can also now see that it wasn't actually bubble sort but selection sort