Section Widget
The structure of the array is as follows:
Code:
row | col. 1 | col. 2 --------------------- 0 | 3 | Kevin 1 | 3 | Alice 2 | 2 | Steve 3 | 1 | Adam 4 | 2 | Sammy
Code:
var array = new Array(); array[0] = new Array ( 3, "Kevin" ); array[1] = new Array ( 3, "Alice" ); array[2] = new Array ( 2, "Steve" ); array[3] = new Array ( 1, "Adam" ); array[4] = new Array ( 2, "Sammy" );
1,Adam
2,Sammy
2,Steve
3,Alice
3,Kevin
As you can see, the array should be sorted by considering the 1st column values, and when two values are equal those two rows should be sorted considering the 2nd column.
I elected the quicksort algorithm to sort the array. Like its name says, the quicksort algorithm is usually the fastest. Its only downside is that when the array was already sorted it will waste more time than other, otherwise slower, algos. Here is the code I used. This version was improved from the version I posted in the original thread, as explained below. The main function, qsort is an adapted version of the classic quicksort. It was ported to JavaScript and modified to use a compare function instead of directly comparing elements with "<" and ">".
Code:
function compare ( array, left, right ) {
var depth = 0;
while ( depth < array[left].length && depth < array[right].length ) {
if ( array[left][depth] < array[right][depth] )
return 1;
else if ( array[left][depth] > array[right][depth] )
return -1;
depth++;
}
return 0;
}
function qsort ( array, lo, hi ) {
var low = lo;
var high = hi;
mid = Math.floor( (low+high)/2 );
do {
while ( compare(array, low, mid) > 0 )
low++;
while ( compare(array, high, mid) < 0 )
high--;
if ( low <= high ) {
swap( array, low, high );
low++;
high--;
}
} while ( low <= high );
if ( high > lo )
qsort( array, lo, high );
if ( low < hi )
qsort( array, low, hi );
}
function swap ( a, i, j ) {
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
var array = new Array();
array[0] = new Array ( 3, "Kevin" );
array[1] = new Array ( 3, "Alice" );
array[2] = new Array ( 2, "Steve" );
array[3] = new Array ( 1, "Adam" );
array[4] = new Array ( 2, "Sammy" );
qsort ( array, 0, array.length-1 );
We need not understand fully the quicksort algorithm here to understand how the sorting works for our bidimensional array. The trick is that it uses the compare function to determine if a given row is above or underneath another given row in the array. The compare function compares the 1st elements in the 2 given rows, and returns 1 or -1 depending on which is greater. If the two are equal, it moves to the second column. It will continue that way until it reaches the end of the rows, in which case it concludes that the two rows are equal. This is an improvement from the original version, in which only the first two columns were compared.
Note that the above script can only compare two arguments which can be compared with the "<" and ">" operators. In JavaScript, both numbers and strings can be compared that way, but not your own objects, so be careful.
That's pretty much it for my explanations, please give me feedback or post any questions you might have as I know I am not very good at giving explanations.
ciao,
Scum
I have corrected an error in the above code, in the compare function...
Here are a few simplified instructions for anyone who would want to use this code but who's not interested in how it works:
1/ Copy the three functions and put them at the top of your script.
2/ Build your array of arrays, in any way you wish (see example above)
3/ Call qsort(array, 0, array.length-1);
that's it!
Please report any errors and/or bugs!
Recent Articles
vBulletin Message