At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
The simplest pseudocode could be: do i=1,n-1 do j=i+1,n if m(i)>m(j) then tmp=m(i); m(i)=m(j); m(j)=tmp; endif end j end i There are other versions where we don't do the exchange right away for better efficiency, or take the array element m(i) outside of the j loop, etc.
@mathmate has the right idea - look at the algorithm! Wikipedia offers an alogorithm here: https://en.wikipedia.org/wiki/Bubble_sort#Implementation " The algorithm can be expressed as (0-based array): ``` procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false for i = 1 to n-1 inclusive do /* if this pair is out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap( A[i-1], A[i] ) swapped = true end if end for until not swapped end procedure ``` " A 0-based array means that the first element is labeled "0". That's why `i` uses the inclusive range [0, n-1]; the last element is labeled `n-1`. Draw a picture if you need to understand that. @mathmate, Does that algorithm repeatedly compare each "j" with the "i-th" element for each i? I learned to compare adjacent numbers, and this would not do that. It would work, still, since it assures that the number in the left-most position is the smallest. That is proven by the fact that if it was not the smallest, then it would be moved out of that spot. But I'm not sure that it allows it to be called a bubble sort. Unless I'm mistaken -- and it's been quite a day, so I might be -- this looks like a sort that I don't have a name for. Almost like a selection sort, in that it iterates through one less element each time, putting the smallest element at the beginning of the section you currently look at. I assume this is a 1-based array - so that you begin comparing with the first element.
yeah, the classical bubble sort would compare only adjacent numbers, hence the name bubble sort. The way I do it has the same complexity, and it's much easier to program, so I use it all the time in place of the bubble sort. So, yes, you're right, it probably should not be called the bubble sort. For the 0-based and 1 based, I just used natural numbers, not knowing what language was to be used. I know that almost all current languages are all 0-based.
Right! I thought that the 0 vs 1 is just an arbitrary choice - the important thing is to stick with it.
Oh, also because there are more ways to optimize than comparing adjacent members (like taking m(i) outside of the j-loop, use pointers to point at the smallest element, and swap only at the end of the j-loop, etc. I used to work with Fortran and slow computers, so code optimization is what I always consider. On the contrary, we don't use bubble (or equivalent) sort if we want it done fast, lol.
Yeah, all those optimizations are helpful. And, haha, right! Those optimizations still don't do the trick. It's a learning tool, or a linear sort for sorted lists.
I don't get on OpenStudy too much, but I'm sure you can help @ubah with questions :) Take care!
Well, come visit whenever you have a chance! and nice talking to you @theEric :)
Same to you! :)