Computer Science Canada

Bubble Sort

Author:

implosion [ Thu Mar 05, 2009 9:32 am ]

Post subject:

Bubble Sort

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]

Author:	DemonWasp [ Thu Mar 05, 2009 11:45 am ]
Post subject:	RE:Bubble Sort
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.

Author:

implosion [ Thu Mar 05, 2009 5:35 pm ]

Post subject:

Re: Bubble Sort

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.

Author:	DemonWasp [ Thu Mar 05, 2009 10:22 pm ]
Post subject:	RE:Bubble Sort
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.

Author:

Tallguy [ Fri Mar 06, 2009 8:37 am ]

Post subject:

Re: Bubble Sort

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

Author:

implosion [ Sat Mar 07, 2009 2:10 pm ]

Post subject:

Re: Bubble Sort

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

Author:	Tallguy [ Sat Mar 07, 2009 2:26 pm ]
Post subject:	RE:Bubble Sort
yeah, srry bout that, i only gave it because i find it hard to explain ps. my name is one word 'tallguy' lol

Author:	implosion [ Wed Mar 11, 2009 10:38 pm ]
Post subject:	RE:Bubble Sort
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.

You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy