News for hackers. Stuff that matters.
Re:“It is never a compiler error” by openasocket on Wednesday November 15, 2017 @12:48AM (#15701719)
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.

Re:“It is never a compiler error” by harry8 on Wednesday November 15, 2017 @01:12AM (#15701788)
You can avoid the second pass...
Re:“It is never a compiler error” by openasocket on Wednesday November 15, 2017 @01:20AM (#15701812)
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.
Re:“It is never a compiler error” by somecontext on Wednesday November 15, 2017 @07:45AM (#15703342)
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.

Re:“It is never a compiler error” by harry8 on Friday November 17, 2017 @08:17PM (#15727258)
you look back and see if you will need a second swap and set your "need another pass" boolean that you named "swapped" accordingly.