dcsimg
Results 1 to 6 of 6

Thread: Question about Bubble Sort algorithm Pseudocode

  1. #1

    Thread Starter
    Junior Member tushardevi's Avatar
    Join Date
    Dec 2017
    Location
    Wales
    Posts
    17

    Post Question about Bubble Sort algorithm Pseudocode

    Hi everyone, its good to be back!

    Today I will try to write a bubble sort algorithm on VB, however, before I start I have question about its pseudocode.

    The following its a pseducode for a bubble sort algorithm (from my Computer Science book):

    FUNCTION bubblesort(list)

    REPEAT
    swapped = false
    FOR n =1 TO LEN(list)-1
    IF list[n-1] > list[n] THEN
    temp = list[n-1]
    list[n-1] = list[n]
    list[n] = temp
    swapped = true
    END IF
    NEXT n
    UNTIL NOT swapped
    RETURN list
    END FUCTION

    The bit I dont understand is that what if list[n-1] is less than list[n] then what happens? Because inside the IF statement there is no ELSE. Like you not telling the computer what to do IF list[n-1] < list[n].

    For example if we have the following list:

    x1 , x2 , x3

    if we use this code than we will compare the x1 with x2 and if x1 is bigger than x2 than we will swap the two numbers. However, what if x1 is less than x2? There is no ELSE statement below the IF statement that will tell you what to if x1<x2. I am so confused on why there is no ELSE in this code!

    Thank You

  2. #2
    Hyperactive Member
    Join Date
    Nov 2017
    Posts
    375

    Re: Question about Bubble Sort algorithm Pseudocode

    The If statement checks two elements to see if they are out of the proper order. The Else case would be what to do if the two elements are in the proper order. Well, since the point of a sort algorithm is to place things in the proper order, then if two elements are already in the proper order, then nothing needs to be done with them, hence no Else statement.

  3. #3
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    32,253

    Re: Question about Bubble Sort algorithm Pseudocode

    Since there is no Else clause, then if the condition in the If clause is not met, then NOTHING will happen. In this case, what it means is that if list[n-1] is less than or equal to list[n], then don't take any action at all, and go on to the next n.

    Essentially, what it is doing is saying, "If this is out of order compared to the next item, then swap them. If they are already in the right order, then don't do anything."

    EDIT: Too slow, but perhaps it adds value anyways.
    My usual boring signature: Nothing

  4. #4

    Thread Starter
    Junior Member tushardevi's Avatar
    Join Date
    Dec 2017
    Location
    Wales
    Posts
    17

    Re: Question about Bubble Sort algorithm Pseudocode

    Thank you for your replies. One last question. Why is swapped = false and swapped = true necessary ?? What do they do? What if they were not in the code? What would happen?

  5. #5
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    32,253

    Re: Question about Bubble Sort algorithm Pseudocode

    If they were not in the code, the loop would never end.

    What that flag does is says, "I made at least one change." Therefore, if you don't have the flag, then you'd keep going forever. Eventually, the list would be sorted and you wouldn't be swapping anything after that, but there would be nothing to tell the code that the list has been sorted, so it would keep on checking for the rest of time.
    My usual boring signature: Nothing

  6. #6
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    4,541

    Re: Question about Bubble Sort algorithm Pseudocode

    Quote Originally Posted by tushardevi View Post
    Thank you for your replies. One last question. Why is swapped = false and swapped = true necessary ?? What do they do? What if they were not in the code? What would happen?
    When you loop through all the items, you are comparing two, and swapping the larger of the two if necessary, so it will be then compared to the next one. Since the larger item is swapped up, and then compared to the next when you've gone through the loop once, you are guaranteed that the largest item has "bubbled" up to the top, which is why it is called a bubble sort.

    But just because the largest item in the list has bubbled to the top, doesn't mean the list is sorted, only the largest made it to the top. So, you have to loop again so that the next largest will bubble up toward the top until it reaches its place.
    You continue repeating the loop through all the items until no more items need to bubble up.

    The swapped flag is set whenever an item starts "bubbling" up.
    If you make it through the whole loop without setting the flag, then all the items are in the proper place and there is no more bubbling going on, so you're done.

    A simple improvement on the bubble sort is to reduce how far you go through the loop each pass so you do less comparisons.
    After the first loop is completed you know the largest item is in the last position so you don't need to compare that item again, so your second loop can loop one less time. After the second loop is done, the next highest value should be in the second from the last position, so you don't have to compare that again in the next loop.

    So, you loop one less position with each pass through the loop.
    If you use that method, then you could have the logic quit repeating the loop as soon as your top loop value equals the beginning position.
    But in many cases you don't have to loop all the way down to the last two items, because the lower items may be in order before you get there. That is why the swapped flag is set. It allows the program to stop looping early if there were no items to swap in the current pass. If no items were swapped in the current pass, then there will be no items swapped in any of the shorter loops.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Featured


Click Here to Expand Forum to Full Width