P
ROTOTYPE
I'm Not Only The Prototype, I'm Also A Member.
home
▪
stats
▪
search
▪
linkback
▪
about
▪
FAQ
| user: guest,
login
,
register
Array
:
three numeric sorts: positive integer, postive number (float), number (float) sort
author:
doug
[+]
,
Submitted: 01.31.03 12p
// Description :: Positive Integer Sort // Returns :: Sorted Array // Restriction :: only works for positive integers // The idea for this came from David Yang's (I think) post on chatty fig. His was a sortOn method. // Author :: Doug Marttila - David Yang(?) unbeknownst to him Array.prototype.sortPInt = function() { var m = 0 var L = this.length; var i = L; while (i--) { var s = String(this[i]); if (s.length>m){ m = s.length; } } var z = ""; var i = m; while (--i) { z += "0"; } var i = L; while (i--) { this[i] = (z+this[i]).slice(-m); } this.sort(); var i = L; while (i--) { this[i] = parseInt(this[i], 10); } }; ASSetPropFlags(Array.prototype, "sortPInt", 1); // Description :: Numeric (float) Sorts // Return :: Sorted Array // Restriction :: sortPNum is faster than sortNum, but, sortPNum only works for positive numbers. // for fastest positive integer sort, use sortPInt // sortNum requires sortPNum. If you're only using sortPNum, you can remove the sortNum method from the include. // Author :: Doug Marttila Number.prototype.findDigits = function() { var t = 10; var d = 1; var n = Math.floor(this); while (t-1<n) { t *= 10; d++; } return d; }; //returns the largest number in an array Array.prototype.findLargest = function() { var L =this[0]; var p for (p in this) { if (this[p]>L) { L = this[p]; } } return L; }; ASSetPropFlags(Array.prototype, "findLargest", 1); Array.prototype.sortPNum = function() { //get the number of non-decimal digits in the largest number in the array var digits = this.findLargest().findDigits(); //turn the array into an array of strings that sorts like numbers //if largest num is 9873 - turns 8 into '0008' //zeroes:string, digits to add, prop var z, d, p; for (p in this) { d = digits-this[p].findDigits(); z = ""; while (d--) { z += '0'; } this[p] = String(z+this[p]); } //sort as strings - fast this.sort(); //turn the strings back into numbers for (p in this) { this[p] = parseFloat(this[p]); } }; ASSetPropFlags(Array.prototype, "sortPNum", 1); Array.prototype.sortNum = function() { //split array into 3 arrays - positive, negative, zeroes var pos = new Array(); var neg = new Array(); var zer = new Array(); var p, n for (p in this) { n = this[p]; if (n>0) { pos.push(n); } else if (n==0) { zer.push(0); } else { neg.push(n*-1); } } pos.sortPNum(); neg.sortPNum(); for (p in neg) { neg[p] *= -1; } neg.reverse(); var s = neg.concat(zer, pos); for (p in this) { this[p] = s[p]; } }; ASSetPropFlags(Array.prototype, "sortNum", 1);
usage
Above contains the code for 3 numeric sorts - positive integer, positive number, and number. I use the integer sort the most - and it's the fastest. But, they are all faster than using the built in sort with a numeric compare function (sometimes only slightly faster). The speed difference is greatest when the array is already sorted (or nearly sorted or reversed). I've only tested these in MX on the PC. The sortPNum and sortNum sorts require the number.findDigits prototype and the array.findLargest prototype. (both included above) sortNum requires sortPNum arr=[2,3,1,5,6]; arr.sortPInt(); trace(arr)//1,2,3,5,6 arr=[2.1,2.4,1.2,3]; arr.sortPNum(); trace(arr)//1.2,2.1,2.4,3 arr=[2.1,-4,3.2,-5.4]; arr.sortNum(); trace(arr)//-5.4,-4,2.1,3.2 [b]One sample benchmark:[/b] arr = []; for (i=0; i<1000; i++) { arr[i] = 1000-i; } start = getTimer(); arr.sortPInt(); function numSort(a, b) { return (a-b); } //arr.sort(numSort); trace(getTimer()-start); //time sort(numSort) : 14584 //time sortPInt : 3736 Obviously, the reverse() method would be best choice for the above benchmark. But, you get the idea.
Add Comment
[+]
›opyleft 2001-2010. Layer51 is: Jaime Prado.
@