Computer Science Canada

Bubble Sort Problem

Author:  gitoxa [ Fri May 23, 2008 4:26 pm ]
Post subject:  Bubble Sort Problem

I came up with an idea to make a bubble sorter go faster. I read "comb sort" on wikipedia, and this came ot my head, even though comb sort is something else... heh.
Anyway, it's a bubble sort that goes both ways, up the array, then down, to lessen the time it takes to move small numbers from high indices to low ones. It works fine, until I try around 300 numbers. At some point, it just stops even though the numbers are not in order.

I've been staring at it for a while, with no solution becoming apparent. You guys see something I'm missing?

code:
%Swaps two numbers in an array.
procedure Swap_Nums (var NumList : array 1 .. * of int, Temp1, Temp2 : int)
    var Temp : int
    Temp := NumList (Temp1)
    NumList (Temp1) := NumList (Temp2)
    NumList (Temp2) := Temp
end Swap_Nums

%Sorts an array of numbers, using the bubble sort method.
procedure Bubble_Sort2_Nums (var NumList : array 1 .. * of int, NumNums : nat1)
    var Done : boolean
    var Temp : int
    loop
        Done := true
        for Forward : 1 .. NumNums - 1
            if NumList (Forward) > NumList (Forward + 1) then
                Swap_Nums (NumList, Forward, Forward + 1)
                Done := false
            end if
        end for
        if ~Done then
            Done := true
            for decreasing Backward : NumNums .. 2
                if NumList (Backward) < NumList (Backward - 1) then
                    Swap_Nums (NumList, Backward, Backward - 1)
                    Done := false
                end if
            end for
        end if
        exit when Done
    end loop
end Bubble_Sort2_Nums


code:
%Main
const MAXNUMS := 300
var Numbers : array 1 .. MAXNUMS of int
for Create : 1 .. MAXNUMS
    randint (Numbers (Create), 1, 1000)
end for
Bubble_Sort2_Nums (Numbers, MAXNUMS)
for Output : 1 .. MAXNUMS - 1
    if Numbers(Output) > Numbers(Output+1) then
        put "Fail"..
    end if
end for

Author:  richcash [ Fri May 23, 2008 6:20 pm ]
Post subject:  Re: Bubble Sort Problem

Your NumNums parameter is declared as nat1.

nat1 is 1-byte so its range is 0-255. If you pass an argument that is greater than that it will basically be modulo-ed by 256 so your for loops will be incorrect. You should change the type of your parameter to support more bytes.

Author:  gitoxa [ Fri May 23, 2008 6:42 pm ]
Post subject:  RE:Bubble Sort Problem

Oh, okay, thanks. Thought I'd gotten all the variables fixed.


: