A community for students.

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

anonymous

  • one year ago

Given the following numbers 10,4,7,1,8,2,6,5,3,9 describe how these numbers will be sorted in ascending order using bubble sort algorithms

  • This Question is Open
  1. mathmate
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  2. theEric
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    @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.

  3. mathmate
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  4. theEric
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Right! I thought that the 0 vs 1 is just an arbitrary choice - the important thing is to stick with it.

  5. mathmate
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    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.

  6. theEric
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    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.

  7. theEric
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    I don't get on OpenStudy too much, but I'm sure you can help @ubah with questions :) Take care!

  8. mathmate
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Well, come visit whenever you have a chance! and nice talking to you @theEric :)

  9. theEric
    • one year ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Same to you! :)

  10. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.