4 ms·

> Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? Wha

> Bubble sort is usually operates on data in place. I don't know how to do an efficent in-place selection sort for mostly sorted data, maybe it's possible? What about insertion sort? Which always performs fewer comparisons and swaps than bubble sort for any array, by the way.

harry8 9y ago
So I made the case with evidence that it doesn't always perform fewer comparisons and it it doesn't always perform fewer swaps. While it probably does, depending on implementation details use more memory. Do feel free to actually make your case with evidence, that I would be interested in reading. What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.
- openasocket 9y ago
  > While it probably does, depending on implementation details use more memory Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort. Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
  - harry8 9y ago
    1,2,3,4,6,5,7 6 comparisons, 1 swap with bubble and it stops. I make it 7 memory reads and 2 memory writes. Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.
    - openasocket 9y ago
      Bubble sort performs 11 comparisons and 13 memory reads in this case, actually. Because on the first pass through the array it performed a swap, it has to loop through the array a second time to verify the array is completely sorted. To avoid confusion, here's the bubble sort algorithm: procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap(A[i-1], A[i]) swapped = true end if end for n = n - 1 until not swapped end procedure As you can see, after performing a swap during the first pass through the array it has to go through again (though it can skip the last element because we know the last element must contain the largest element in the array) Insertion sort will perform 7 comparisons, 1 swap, 7 memory reads and 2 writes.
      - harry8 9y ago
        You can avoid the second pass...
        openasocket 9y ago
        No, you can't, because at the end of the first pass you have no way to know that it is in sorted order. Go ahead and try to write the pseudocode for your bubble sort implementation that avoids the second pass.
        somecontext 9y ago
        To be concrete, the array in order 1235647 has the first six comparisons go the same way as in 1234657, but it doesn't end up sorted in one pass. Perhaps harry8 was thinking of the bubble sort implementation in the OP, which would indeed stop after one pass in these cases.
        harry8 9y ago
        you look back and see if you will need a second swap and set your "need another pass" boolean that you named "swapped" accordingly.

harry8 9y ago

So I made the case with evidence that it doesn't always perform fewer comparisons and it it doesn't always perform fewer swaps. While it probably does, depending on implementation details use more memory. Do feel free to actually make your case with evidence, that I would be interested in reading. What is it with this thread and "nyer, you're wrong" responses? It's not helpful, not clever, not useful and not pleasant to read for anybody. Finding out you're wrong is great, I learn stuff.

openasocket 9y ago
> While it probably does, depending on implementation details use more memory Have you actually looked at the insertion sort algorithm? It doesn't allocate any additional memory. Neither does bubble sort or selection sort. Knuth does some analysis of Bubble Sort in Volume 3 of the Art of Computer Programming, which proves bubble sort performs more comparisons and more swap operations than insertion sort. To quote the conclusion: "[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!"
- harry8 9y ago
  1,2,3,4,6,5,7 6 comparisons, 1 swap with bubble and it stops. I make it 7 memory reads and 2 memory writes. Insertion and selection sorts are going to run in half that time? I'd really like to see that! I think Knuth might be talking about a general case of any data rather than the topic being discussed here, but no, I haven't read Knuth on bubble sort so I can't be sure. I may do so now so thank you for the pointer. Arguments from authority really can be informative and useful despite their other shortcomings.
  - openasocket 9y ago
    Bubble sort performs 11 comparisons and 13 memory reads in this case, actually. Because on the first pass through the array it performed a swap, it has to loop through the array a second time to verify the array is completely sorted. To avoid confusion, here's the bubble sort algorithm: procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap(A[i-1], A[i]) swapped = true end if end for n = n - 1 until not swapped end procedure As you can see, after performing a swap during the first pass through the array it has to go through again (though it can skip the last element because we know the last element must contain the largest element in the array) Insertion sort will perform 7 comparisons, 1 swap, 7 memory reads and 2 writes.
    - harry8 9y ago
      You can avoid the second pass...
      - openasocket 9y ago
        No, you can't, because at the end of the first pass you have no way to know that it is in sorted order. Go ahead and try to write the pseudocode for your bubble sort implementation that avoids the second pass.
        somecontext 9y ago
        To be concrete, the array in order 1235647 has the first six comparisons go the same way as in 1234657, but it doesn't end up sorted in one pass. Perhaps harry8 was thinking of the bubble sort implementation in the OP, which would indeed stop after one pass in these cases.
        harry8 9y ago
        you look back and see if you will need a second swap and set your "need another pass" boolean that you named "swapped" accordingly.