4 ms·

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 abs

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)
- SomeoneFromCA 3y ago
  Your original claim that is more complex or slower is unsubstantiated. Yes, it is trivially more complex to add a flag, but it does not actually make it any more difficult to understand or error prone. Your argument is way too pedantic. Claim about the performance is equally unsubstantiated. To make a proper proof you need to show that on average, we still have all N outer passes executed, before we face no swaps situation. Which almost certainly is never true, especially with non-random data. Although I certainly agree that Bubble Sort is almost always a bad choice, it still is used in computer graphics, or other situations when you have only one or two misplaced pairs of elements. In this case it will outperform the other algorithms, in average case while maintainig functionally in the less than ideal situation. Besides it is entirely irrelevant what are the purposes the algorithm is used today, didactic, deliberate or poor judgement, the de facto standard way of doing it today is to check for the early exit. Your argument about poor performance on the already sorted data is a straw man argument, your are stubbornly defending. Well ok, if you believe so...
  - kragen 3y ago
    if you aren't convinced that adding the early exit generally hurts performance, well, it's not surprising; measuring performance is difficult and tricky, and you're faced here with claims you don't really have the knowledge to evaluate properly, so it's entirely proper that you are dubious about them, even if you're confused about what a proper proof would consist of it might help your intuition to think of it this way: 1. with random input, the first ten positions of output are pretty likely (65%) to have an item that was originally in the last 10% of the input, and almost certain (97%) to have an item that was originally in the last 30% of the input. so those ten items alone account for needing 95% of the passes you'd need without an early exit, minus about five, in 65% of cases. 2. the first 20 positions are pretty likely (64%) to have an item that was originally in the last 5% of the input, and almost certain (96%) to have an item that was originally in the last 15% of the input. so those 20 items account for needing 97% of the passes you'd need without an early exit, minus about ten, in 64% of cases. 3. the first 30 positions are pretty likely (64%) to have an item that was originally in the last 3.3% of the input, and almost certain (96%) to have an item that was originally in the last 10% of the input. so those 30 items account for needing 98.5% of the passes you'd need without an early exit, minus about 15, in 64% of cases. of course, if you're only sorting 30 items, the first ten positions of output are actually a third of all the positions, so "minus five" is pretty significant. and probably if you're sorting more than about 30 items at a time you ought to use a linearithmic sort or a linear-time radix sort instead of a quadratic sort similarly, it's reasonable to argue that complexity (in the sense of containing many parts, not in the sense of asymptotic computational work required) is subjective, and to disagree about it but i think these are sort of moot points insertion sort still beats bubble sort in the situations where you have only one or two misplaced pairs of elements, and generally replaces it as soon as somebody notices as for 'the de facto standard way of doing it today', i suggest you argue with clrs, not with me

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)

SomeoneFromCA 3y ago
Your original claim that is more complex or slower is unsubstantiated. Yes, it is trivially more complex to add a flag, but it does not actually make it any more difficult to understand or error prone. Your argument is way too pedantic. Claim about the performance is equally unsubstantiated. To make a proper proof you need to show that on average, we still have all N outer passes executed, before we face no swaps situation. Which almost certainly is never true, especially with non-random data. Although I certainly agree that Bubble Sort is almost always a bad choice, it still is used in computer graphics, or other situations when you have only one or two misplaced pairs of elements. In this case it will outperform the other algorithms, in average case while maintainig functionally in the less than ideal situation. Besides it is entirely irrelevant what are the purposes the algorithm is used today, didactic, deliberate or poor judgement, the de facto standard way of doing it today is to check for the early exit. Your argument about poor performance on the already sorted data is a straw man argument, your are stubbornly defending. Well ok, if you believe so...
- kragen 3y ago
  if you aren't convinced that adding the early exit generally hurts performance, well, it's not surprising; measuring performance is difficult and tricky, and you're faced here with claims you don't really have the knowledge to evaluate properly, so it's entirely proper that you are dubious about them, even if you're confused about what a proper proof would consist of it might help your intuition to think of it this way: 1. with random input, the first ten positions of output are pretty likely (65%) to have an item that was originally in the last 10% of the input, and almost certain (97%) to have an item that was originally in the last 30% of the input. so those ten items alone account for needing 95% of the passes you'd need without an early exit, minus about five, in 65% of cases. 2. the first 20 positions are pretty likely (64%) to have an item that was originally in the last 5% of the input, and almost certain (96%) to have an item that was originally in the last 15% of the input. so those 20 items account for needing 97% of the passes you'd need without an early exit, minus about ten, in 64% of cases. 3. the first 30 positions are pretty likely (64%) to have an item that was originally in the last 3.3% of the input, and almost certain (96%) to have an item that was originally in the last 10% of the input. so those 30 items account for needing 98.5% of the passes you'd need without an early exit, minus about 15, in 64% of cases. of course, if you're only sorting 30 items, the first ten positions of output are actually a third of all the positions, so "minus five" is pretty significant. and probably if you're sorting more than about 30 items at a time you ought to use a linearithmic sort or a linear-time radix sort instead of a quadratic sort similarly, it's reasonable to argue that complexity (in the sense of containing many parts, not in the sense of asymptotic computational work required) is subjective, and to disagree about it but i think these are sort of moot points insertion sort still beats bubble sort in the situations where you have only one or two misplaced pairs of elements, and generally replaces it as soon as somebody notices as for 'the de facto standard way of doing it today', i suggest you argue with clrs, not with me