Bubble Sort

[implosion]

So i have a working bubble sort, but my problem is i need to output how many movements were done, and how many comparisons were done example. best case scenario (1,2,3,4,5).. there are 4 comparisons, no movement (but it says 16).. and in worst case (5,4,3,2,1) it outputs that there were only 16 comparisons and i don't think thats right...

Thanks.

Turing:

var choice : int put "How many intergers would you like to be sorted ?" get choice var arraylist : array 1 .. choice of int for a : 1 .. choice     put "Number  ", a, " : " ..     get arraylist (a) end for var temp : int var movement, compare : int := 0 for b : 1 .. choice - 1     for c : 1 .. choice - 1         if arraylist (c) > arraylist (c + 1) then             temp := arraylist (c)             arraylist (c) := arraylist (c + 1)             arraylist (c + 1) := temp             movement += 1         end if         put arraylist (c), " : ", arraylist (c + 1)         delay (10)         compare += 1     end for end for put "" put "Number of movements: ", movement put "Number of comparisons: ", compare for d : 1 .. choice     put arraylist (d), ", " .. end for

[/code]

[DemonWasp]

The counting is correct; your implementation of bubblesort is not. Bubblesort can exit as soon as it makes a single pass with no movements / swaps, but your algorithm doesn't.

[implosion]

hmm... should i first have an if condition ?

code:

for i : 1...choice-1 if arraylist (i) < arraylist (i+1) then put "already sorted" else ... other code written for bubble sort below

i'm just quickly roughly writing this down since i have to go for work in 10 mins, haha.. but am i on the right track? or do i have to implement a loop instead of a forloop ? i just checked the pseudocode on wikipedia for bubble sort but its not helping. a little push in the right direction would be appreciated, haha.

thanks.

[DemonWasp]

You need to keep track of whether you've made any swaps on this pass through the array. The correct choice for this is a boolean variable - set it to false before you start checking each combination; if you have to switch each combination, set it to true. If you get past all the comparisons and it's still false, you can exit early.

[Tallguy]

bubble sorting is an annoying, but easy concept

Turing:

var yes : array 1 .. amount of int var random : boolean := true for last : 1 .. amount %loops for the number of times the user specified     for i : 1 .. amount - 1 %loops one less then user defined because its comaring #1 and #1+1, so it has to end at one less then usder defined because the program adds 1         if yes (i) > yes (i + 1) then %compares the first mark to the second mark             random := false %if the above statement is true the whole eqiuation is 'false' so it has to do it again, and again until it is 'true' so it ends             const temp := yes (i) %here the two numbers are swamped so that #1 becomes #2, #2 becomes #1, using a tempoary variable to store the first number so itrs not overwrittem             yes (i) := yes (i + 1) %see above             yes (i + 1) := temp %see above         end if     end for     exit when random %exit when this statement is true end for

all this does is compare two variables and if one is larger then two, then one becomes a temp var, two becomes one, and temp becomes two, this is basically the basic bubble sort , for a visual idea i have attached a program that shows bubble sort as well as different kinids

you must havea boolean operator, to check if all yoursorting is done correctly

dunno if this will help any, but i hope it does

[implosion]

thanks tall guy, but instead of giving me the answers, a small nudge in the right direction would have been better.
so i wrote 2 versions of bubble sort, the normal one and then an optimized one... would these be right ?

Turing:

%BUBBLE SORT var choice : int var swap : boolean := true var compare, movement : int := 0 put "how many integers would you like to be sorted " .. get choice var arraylist : array 1 .. choice of int for i : 1 .. choice     put "Number ", i, ": " ..     get arraylist (i) end for var temp : int for c : 1 .. choice     for a : 1 .. choice - 1         if arraylist (a) > arraylist (a + 1) then             swap := false             temp := arraylist (a)             arraylist (a) := arraylist (a + 1)             arraylist (a + 1) := temp             movement += 1         end if         compare += 1     end for     exit when swap end for put "Comparison: ", compare put "Movement: ", movement for c : 1 .. choice     put arraylist (c), " " .. end for

i think this is right, since on the first pass of the bubble sort the highest element would be already at the bottom it wouldn't have to check it.

Turing:

% optimized bubble sort var choice : int var swap : boolean := true var compare, movement, pass : int := 0 put "how many integers would you like to be sorted " .. get choice var arraylist : array 1 .. choice of int for i : 1 .. choice     put "Number ", i, ": " ..     get arraylist (i) end for var temp : int for c : 1 .. choice     pass += 1     for a : 1 .. choice - pass         if arraylist (a) > arraylist (a + 1) then             swap := false             temp := arraylist (a)             arraylist (a) := arraylist (a + 1)             arraylist (a + 1) := temp             movement += 1         end if         compare += 1     end for     exit when swap end for put "Comparison: ", compare put "Movement: ", movement for c : 1 .. choice     put arraylist (c), " " .. end for

[Tallguy]

yeah, srry bout that, i only gave it because i find it hard to explain

ps. my name is one word 'tallguy' lol

[implosion]

sorry Tallguy

okay so my code is above, and my question now is my movement, compare counters in the right spot ?... i was looking at an example online of bubble sort and it was 10 elements in worse case situation, and the # of comparisons = # of movements (swaps)... and mine doesn't do that.