Clever Geek Handbook

Why does this standard ML bubblesort loop only run once?

So, I tried to implement bubblesort using ML reference types. I have compiled the code in Poly / ML and it seems that the while (! Flag) loop only executes once for any input.

For example: [2,3,1] gets "sorted" to [2,1,3], i.e. the first loop worked, but the second never started.

"Flag up" is printed once.

What happened?

Thank.

fun bubbleSort l =        (* l being a list of references *)
let
    val it = ref 0        (* iterator variable *)
    val len = length l
    val flag = ref true   (* to be set to true when a swap is made *)
in
    while (!flag) do
    (
        flag := false;
        while ((!it) < (len-1)) do
        (
            if (get l (!it)) > (get l ((!it)+1))
            then (swap_next l (!it); flag := true; TextIO.print "Flag up\n")
            else ();
            it := (!it) + 1
        )
    )
end;

The complete module code I wrote, if needed, can be found here .

+3


source to share


1 answer


Bubblesort iterates over the same array. Your inner loop only checks it once, but never resets the counter it

. Before the line

while ((!it) < (len-1)) do


You have to put the line

it := 0;
+4


source






More articles:


All Articles