Re: [Flashcoders] sort 2d array
I think its wise to be careful how you approach this as although quicksort is 'quick' you could actually be using it inefficiently (or rather in a situation that isnt appropriate) If your list is almost sorted then quicksort can be inefficient, (depending on how you choose your pivot, apparently choosing a random pivot can be a good idea) Also this highlights how you should be careful when benchmarking any sorting algorithms as the order of the data before the sort greatly affects performance. If its possible you might be better off storing your data already sorted. How is the data generated? If you have to sort then you might want to do some reading first : http://www.cs.sunysb.edu/~algorith/lectures-good/node5.html 'the worst case time for Quicksort is worse than Heapsort or Mergesort.' http://linux.wku.edu/~lamonml/algor/sort/quick.html 'the quick sort has horrible efficiency when operating on lists that are mostly sorted in either forward or reverse order - avoid it in those situations' youre lucky though because this topic is very well covered :) Martin ___ [email protected] To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] sort 2d array
Sorry, had a 1 instead of SortIndex in there earlier
/**
* @param myArray, sortIndex, left, right
*
* @usage where myArray is the 2d array you want to sort, sortIndex is
*the index of the second array on which you wish to sort,
*left is the lower bound of myArray and right is the upper
*bound of myArray
*
*/
function quickSort(myArray : Array, sortIndex : Number, left : Number,
right : Number) : Array
{
var arrayLen : Number= myArray.length;
var lHold: Number= left;
var rHold: Number= right;
var pivot: Number= myArray[left][sortIndex];
while(left < right)
{
while( (myArray[right][sortIndex] >= pivot) && (left < right) )
right--;
if(left != right)
{
myArray[left][sortIndex] = myArray[right][sortIndex];
left++;
}
while( (myArray[left][sortIndex] <= pivot) && (left < right)
left++;
if(left != right)
{
myArray[right][sortIndex] = myArray[left][sortIndex];
right--;
}
}
myArray[left][sortIndex]= pivot;
pivot = left;
left= lHold;
right = rHold;
if( left < pivot)
{
qSort(myArray, sortIndex, left, pivot - 1);
}
if( right > pivot)
{
qSort(myArray, sortIndex, pivot + 1, right);
}
return myArray;
}
- Original Message -
From: "Thomas Fowler" <[EMAIL PROTECTED]>
To: "Flashcoders mailing list"
Sent: Thursday, February 01, 2007 12:35 PM
Subject: Re: [Flashcoders] sort 2d array
/**
* @param myArray, sortIndex, left, right
*
* @usage where myArray is the 2d array you want to sort, sortIndex is
*the index of the second array on which you wish to sort,
*left is the lower bound of myArray and right is the upper
*bound of myArray
*
*/
function quickSort(myArray : Array, sortIndex : Number, left : Number,
right : Number) : Array
{
var arrayLen : Number= myArray.length;
var lHold: Number= left;
var rHold: Number= right;
var pivot: Number= myArray[left][sortIndex];
while(left < right)
{
while( (myArray[right][sortIndex] >= pivot) && (left < right) )
right--;
if(left != right)
{
myArray[left][sortIndex] = myArray[right][sortIndex];
left++;
}
while( (myArray[left][sortIndex] <= pivot) && (left < right)
left++;
if(left != right)
{
myArray[right][sortIndex] = myArray[left][sortIndex];
right--;
}
}
myArray[left][sortIndex]= pivot;
pivot = left;
left= lHold;
right = rHold;
if( left < pivot)
{
qSort(myArray, sortIndex, left, pivot - 1);
}
if( right > pivot)
{
qSort(myArray, sortIndex, pivot + 1, right);
}
return myArray;
}
- Original Message -
From: <[EMAIL PROTECTED]>
To:
Sent: Thursday, February 01, 2007 11:08 AM
Subject: [Flashcoders] sort 2d array
Hello,
Can anybody tell me how to sort the following array based upon the second
value
within each array item
myArray:Array = [ [20,40],[20,10],[30,15],[30,35],[40,100],[1000,1]];
this should be something like
[[1000,1], [20,10], .
Faster the better cos its for a game and gets called a lot of times.
regards
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
RE: [Flashcoders] sort 2d array
Consider:
myArray.sortOn( "1", Array.NUMERIC );
>From a quick test this is 2-3 times faster than the callback "compare" way.
10K entries sorted in:
sortOn(1) : 5ms
sort(compare) : 13ms
This works because array indices are considered as keys just like normal
objects.
cheers
~neo
-Original Message-
From: eka [mailto:[EMAIL PROTECTED]
Sent: 01 February 2007 07:25 PM
To: Flashcoders mailing list
Subject: Re: [Flashcoders] sort 2d array
Hello :)
you must creates benchs to test all solutions but the first is the sort()
method with a custom method
var myArray:Array = [
[20,40],
[20,10],
[30,15],
[30,35],
[40,100],
[1000,1]
];
var compare:Function = function ( a , b ) {
if ( a[1] < b[1] )
{
return -1 ;
}
else if (a[1] > b[1] )
{
return 1 ;
}
else
{
return 0 ;
}
}
trace(myArray) ;
myArray.sort( compare ) ;
trace(myArray) ;
I think the Actionscript in FP8 or FP9 really speed !
EKA+ :)
2007/2/1, [EMAIL PROTECTED] <[EMAIL PROTECTED]>:
>
>
>
> Hello,
>
> Can anybody tell me how to sort the following array based upon the
> second value within each array item
>
> myArray:Array = [ [20,40],[20,10],[30,15],[30,35],[40,100],[1000,1]];
>
> this should be something like
>
> [[1000,1], [20,10], .
>
> Faster the better cos its for a game and gets called a lot of times.
>
>
> regards
>
> ___
> [email protected]
> To change your subscription options or search the archive:
> http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
>
> Brought to you by Fig Leaf Software
> Premier Authorized Adobe Consulting and Training
> http://www.figleaf.com http://training.figleaf.com
>
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training http://www.figleaf.com
http://training.figleaf.com
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] sort 2d array
Just as a fun thing to do on the side, I'd try researching priority queues, which were designed for exactly this sort of problem. They get used a lot in pathfinding algorithms for games, which probably makes them doubly relevant. --- [EMAIL PROTECTED] wrote: > > > Hello, > > Can anybody tell me how to sort the following array > based upon the second > value > within each array item > > myArray:Array = [ > [20,40],[20,10],[30,15],[30,35],[40,100],[1000,1]]; > > this should be something like > > [[1000,1], [20,10], . > > Faster the better cos its for a game and gets called > a lot of times. > > > regards > > ___ > [email protected] > To change your subscription options or search the > archive: > http://chattyfig.figleaf.com/mailman/listinfo/flashcoders > > Brought to you by Fig Leaf Software > Premier Authorized Adobe Consulting and Training > http://www.figleaf.com > http://training.figleaf.com > Don't pick lemons. See all the new 2007 cars at Yahoo! Autos. http://autos.yahoo.com/new_cars.html ___ [email protected] To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] sort 2d array
/**
* @param myArray, sortIndex, left, right
*
* @usage where myArray is the 2d array you want to sort, sortIndex is
*the index of the second array on which you wish to sort,
*left is the lower bound of myArray and right is the upper
*bound of myArray
*
*/
function quickSort(myArray : Array, sortIndex : Number, left : Number, right
: Number) : Array
{
var arrayLen : Number= myArray.length;
var lHold: Number= left;
var rHold: Number= right;
var pivot: Number= myArray[left][sortIndex];
while(left < right)
{
while( (myArray[right][1] >= pivot) && (left < right) )
right--;
if(left != right)
{
myArray[left][sortIndex] = myArray[right][sortIndex];
left++;
}
while( (myArray[left][sortIndex] <= pivot) && (left < right)
left++;
if(left != right)
{
myArray[right][sortIndex] = myArray[left][sortIndex];
right--;
}
}
myArray[left][sortIndex]= pivot;
pivot = left;
left= lHold;
right = rHold;
if( left < pivot)
{
qSort(myArray, sortIndex, left, pivot - 1);
}
if( right > pivot)
{
qSort(myArray, sortIndex, pivot + 1, right);
}
return myArray;
}
- Original Message -
From: <[EMAIL PROTECTED]>
To:
Sent: Thursday, February 01, 2007 11:08 AM
Subject: [Flashcoders] sort 2d array
Hello,
Can anybody tell me how to sort the following array based upon the second
value
within each array item
myArray:Array = [ [20,40],[20,10],[30,15],[30,35],[40,100],[1000,1]];
this should be something like
[[1000,1], [20,10], .
Faster the better cos its for a game and gets called a lot of times.
regards
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
Re: [Flashcoders] sort 2d array
Hello :)
you must creates benchs to test all solutions but the first is the sort()
method with a custom method
var myArray:Array = [
[20,40],
[20,10],
[30,15],
[30,35],
[40,100],
[1000,1]
];
var compare:Function = function ( a , b )
{
if ( a[1] < b[1] )
{
return -1 ;
}
else if (a[1] > b[1] )
{
return 1 ;
}
else
{
return 0 ;
}
}
trace(myArray) ;
myArray.sort( compare ) ;
trace(myArray) ;
I think the Actionscript in FP8 or FP9 really speed !
EKA+ :)
2007/2/1, [EMAIL PROTECTED] <[EMAIL PROTECTED]>:
Hello,
Can anybody tell me how to sort the following array based upon the second
value
within each array item
myArray:Array = [ [20,40],[20,10],[30,15],[30,35],[40,100],[1000,1]];
this should be something like
[[1000,1], [20,10], .
Faster the better cos its for a game and gets called a lot of times.
regards
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
___
[email protected]
To change your subscription options or search the archive:
http://chattyfig.figleaf.com/mailman/listinfo/flashcoders
Brought to you by Fig Leaf Software
Premier Authorized Adobe Consulting and Training
http://www.figleaf.com
http://training.figleaf.com
