Computer Science Canada

Recursive selection sort in Actionscript

Author:  Insectoid [ Thu Nov 05, 2009 2:48 pm ]
Post subject:  Recursive selection sort in Actionscript

So, I'm working on a program that compares the speeds of different sorting algorithms. However, I ran into an issue with the selection sort, which I decided to implement recursively. It appears that values in my array are becoming undefined, though I have not changed it at all where I perform the check. Details of the problem are commented in the code.

In case you didn't know, 'trace()' outputs to the standard output window.

Anyway, my code:

code:

//Selection sort function. Parameters are Starting index and Array to sort.
function selectionSort (in1:int, in2:Array):Array{
        //trace (in2[0]); //Here, in2[0] is what it should be
        if (in1 >= in2.length-1) {//exit function if the starting element is the last element of the array
                return in2;
        }
        //trace ("Begin: "+in1+" Length: "+(in2.length-1))
        var begin = in1; //set instance variables to avoid pass-by-reference issues
        var toSort:Array = in2;
        //trace (in2[0]+ " " +toSort[0])//Checks is in2 and toSort are equal like they should be; they are
        var smallestID:int;
        var smallest:int = 999999; //set smallest to really big. Smallest is the smallest element in the array
        var temp:int; //a temporary variable used during swapping
        for (var i = begin; i < toSort.length; i++);{ //finds smallest element in array
                //trace (toSort[i]) //at this point, toSort[i] is undefined. Don't know why. It has not been changed it at all yet.
               
                //Somehow, this statement NEVER evaluates to true
                if (smallest > toSort[i]){//check if currently tested element is smaller then smallest
                        smallest = toSort[i];//set smallest equal to current element
                        smallestID = i;
                        //trace (smallest);
                        //trace (1); //trace to find out if the block ever runs; it doesn't. Prolly because toSort[i] is undefined
                       
                }
        }
        //trace (smallestID);
        //These 3 lines swap the smallest element and the element at [begin]
       
        temp = toSort[begin]; //this part works
        toSort[begin] = smallest;
        toSort[smallestID] = temp;
        //return the partially sorted array into the function to sort the next element in the array.
        return selectionSort (begin + 1, toSort);
}


The initial call of the function:
code:

selectionSort (0, array);


'array' is an Array.

The array is filled with random integers, which I have displayed in the order they were created in an output window. This part works fine. The array is filled before the function is called.

So, if anyone can find the issue, that'd be great, because neither myself, not my friend nor an equally good (or potentially better) programming student in my class can figure this out.

Author:  Brightguy [ Fri Nov 06, 2009 1:23 am ]
Post subject:  Re: Recursive selection sort in Actionscript

Posted Image, might have been reduced in size. Click Image to view fullscreen.

Or to make a long story short, your for loop block is being executed once, with i=toShort.length.

And the "pass-by-reference issues" part seems pointless, I would guess that toSort and in2 refer to the same array (I've never used Actionscript though).

Author:  Prabhakar Ragde [ Fri Nov 06, 2009 8:38 am ]
Post subject:  RE:Recursive selection sort in Actionscript

Here is a recursive selection sort. Studying it may help you.

http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-16.html#node_sec_12.2

Author:  Insectoid [ Fri Nov 06, 2009 2:08 pm ]
Post subject:  RE:Recursive selection sort in Actionscript

Brightguy, I don't see a problem with my for loop. It sets i to begin (which is initially 0) and increments by 1 while i is less than the length of the array. The array is greater than 0 (5 elements in all my tests), so it should run 5 times, i being 0, 1, 2, 3, 4 and then quitting. Even if it only runs once, it should not return toSort[i] as undefined for the first iteration of the first recurse. Which is does.

EDIT: With an extra trace statement, I can confirm that the for loop DOES run more than once. In fact, it runs 5 times the first time to function is run, just as it is supposed to (with an array length of 5)

Author:  DemonWasp [ Fri Nov 06, 2009 2:17 pm ]
Post subject:  RE:Recursive selection sort in Actionscript

If you have for ( init; condition; increment ); then the semicolon at the end is considered an end-of-statement-block and the curly brace following just denotes an unnamed block of statements. Your for loop executes the correct number of times but runs this code:

code:

;


Assuming that the condition you MEANT to have in your for() loop doesn't evaluate to true (which will probably be the case because you're accessing the array past its end, which may well void all comparisons made or be garbage or 0, depending on language...), then smallestID will be undefined and smallest will be 999999. I suspect that if you index an array with [undefined], it will either access the first element or fail (I don't know the language well enough to say).

Author:  Insectoid [ Fri Nov 06, 2009 2:23 pm ]
Post subject:  RE:Recursive selection sort in Actionscript

Well, I did some more testing, and I slapped myself in the face. I actually SLAPPED MYSELF in the FACE to show myself how pissed off I was at myself. I can't believe I didn't see that. GAH. I had 3 people looking at it. Gah.


: