Recursive selection sort in Actionscript

[Insectoid]

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.

[Brightguy]

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).

[Prabhakar Ragde]

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

[Insectoid]

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)

[DemonWasp]

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).

[Insectoid]

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.