Re: FLASH: Array.sort() performance?

[Helen Triolo]

Daryn,


You're right, the built-in sort sure isn't the quickest thing around.  I

made a custom quickSort function a few months ago and then

damnitalltohell, Branden Hall made an even faster one  ;-)  Here is his

function, followed by a statement that makes this function an accessible

method of any array:


function Array_quickSort(){

        //Figure out if any arguments were passed in

        //If there weren't set bot and top to default values

        if (arguments[0]==null){

                var bot = 0;

        }else{

                var bot = arguments[0];

        }

        if (arguments[1]==null){

                var top = this.length-1;

        }else{

                var top = arguments[1];

        }

        if (top-bot == 1){

                if (this[top] < this[bot]){

                        temp = this[top];

                        this[top] = this[bot];

                        this[bot] = temp;

                }

        }else{

                //Set up loop for tail recursion        

                while (bot<top){

                        var i = bot;

                        var j = top;            


                        //Pick the pivot

                        pivot = this[bot];

        

                        //Partition the array around the pivot

                        while(i<j){

                                while(this[j]>pivot){

                                        --j;

                                }

                                this[i] = this[j];

                                while (i<j && (this[i]<=pivot)){

                                        ++i;

                                }

                                this[j]=this[i];

                        }

                        

                        //Replace the pivot

                        this[i]=pivot;

                        

                        //Sort the left sub array

                        this.quickSort(bot,i-1);


                        //Sort the right sub array via tail recursion

                        bot = i+1;

                }

        }

}

Array.prototype.quickSort = Array_quickSort;


Regards,

Helen 

-----------------------------------------------------

i-Technica  �  http://i-technica.com  �  301.424.6037

developer resources: http://i-technica.com/whitestuff


Daryn Nakhuda wrote:

> 

> I'm using the built-in sort method to sort an array. I'm using a helper

> function to make it case-insensitive, something like (i'm paraphrasing so

> don't worry about my syntax/typos here)

> 

> function helper(a,b) {

>         if (a.toLowerCase() < b.toLowerCase()) {

>                 return -1;

>         }

>         else if (a.toLowerCase() > b.toLowerCase()) {

>                 return 1;

>         }

>         else {

>                 return 0;

>         }

> }

> 

> myarray.sort(helper);

> 

> ANYHOW, performance seems to really dog when the array gets large (more

> than a few hundred items)..

> 

> has anyone else seen this? It's possibly that I'm running up against

> limitations in flash, and of course the performance will vary based on the

> client machine, but I'm also guessing that the built-in implementation of

> the sort algorithm may be sub-optimal...

> 

> When I put trace lines in the sort helper, you can watch the comparisions,

> and it looks like it's either bubbling or something similar, definitly

> looks O(n^2).

> 

> Have any of you implemented better sort algorithms in flash5 that you'd be

> willing to share?

> 

> Thanks,

> 

> Daryn


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

flasher is generously supported by...

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

   flashforward2000 and the Flash(tm) Film Festival

 November 27-29, 2000, LONDON, National Film Theatre


   Produced by United Digital Artists and lynda.com

-Sponsored by Macromedia, Adobe Systems and Apple Computer

-http://www.flashforward2000.com  or UK tel. +44 (0870) 751 1526

       Register before November 10 and save �200

            http:// www.flashforward2000.com

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

  To unsubscribe or change your list settings go to

http://www.chinwag.com/flasher or email

helpchinwag [dot] com