Symmetrical Sorting Function 1 and Side Subroutines
|
|
One function plus the side routines and how to pass them their arguments
|
I feature here two main functions (plus a handful of ancillary and not particularly striking ones), both concerned with the same goal.
The purpose is: performing a multisorting, namely given a set of arrays, the first (say the leading) of such list of arrays is sorted in (arguably alphabetical) order by using the built in javascript method sort.
Then all the other arrays that were in the set with it, are rearranged so that what was the entry-to-entry coincidence of all of them with the leading array before the latter was sorted, can be reproduced and found again in all of them: so (this is the point) such original correspondence entry-by-entry gets restored also if the leading array has undergone the changes that every sorting process necessarily imposes upon it.
Achieving this goal is exactly the task of a multisort algorithm.
In javascript (and in nearly all other programming languages actually), sorting takes avail of two user crafted subroutines - in our case named highestFirst() and highestLast() - that instruct the sorting process (which applies to number or letter both) on whether to sort in decreasing order (higherFirst) or increasing order (higherLast). In fact the task of the main functions is to sort an array either in increasing or decreasing order using highestFirst() and highestLast() as, say, path delimiters, and then the functions must reshape any other array in such a fashion that it maintains symmetry with the first one. Example:
var testArray1=new Array("one","five","seventy","thirtytwo","two","five") var testArray2=new Array(1,5,70,32,2,5)
As you see in the literal array (testArray1) each word is the literal match of the numeral version in testArray2. What happens if you sort either in ascending or descending order the numeral array? The symmetry of the first array won't exist any longer. Whenever you face this problem and you need an array to keep mirroring the original symmetry it had with another array that underwent a sorting process, in those cases the subroutines featured here are exactly what you were in need of. A thorny subject, as you can see. But first the side subroutines that will help you to make a proper sorting: they must be included in the script:
A Joan Miro painting |
function highestFirst(a,b){ if(a>b){ return -1} else if (a==b){ return 0} else if(a<b){ return 1} } function highestLast(a,b){ if(a<b){ return -1} else if (a==b){ return 0} else if(a>b){ return 1} }
function highestFirstCI(a,b){ if(a. toLowerCase() > b. toLowerCase()){ return -1} else if (a. toLowerCase() == b. toLowerCase()){ return 0} else if(a. toLowerCase() < b. toLowerCase()){ return 1} } function highestLastCI(a,b){ if(a. toLowerCase() < b. toLowerCase()){ return -1} else if (a. toLowerCase() == b. toLowerCase()){ return 0} else if(a. toLowerCase() > b. toLowerCase()){ return 1} }
The subroutines above will help your sorting process to be performed in the right way, and should be passed as an argument without brackets in within the sort() method, such as:
myArray.sort(highestFirst) or
myArray.sort(highestLast)
- The first will put the highest value as entry [0], and on from there.
- The second will put the highest value at the last position.
- The third would behave as the first, but being case-insensitive, would also avoid that the capitalized letters would be listed as first (which would be the default behaviour of the sorting processes, such as that, for instance, a word starting with a capital Z would appear listed... before a word starting with a lowercase a).
- The fourth is the case insensitive version of #2.
A John Everett Millais painting
|
If you do not use any of them, the sorting process would not be complete, since, for instance, number 20 would appear under number 2 since both start with number 2, but you do not want this: you want number 3 after number 2 and number 20 after number 19!
Just pick the minor (ancillary) subroutine that best suits your need.
Now let's move to the main functions: they are two versions for the same task.
This file deals with symmetrical sorting, which is a way of ordering a data structure (in this case, an Array): if you need a function that can produce a multisort but not on an ordering process but on a random process such as a shuffling of an array, check the symmetrical shufflings file.
Here (below) is now the first function. It is the weaker one, and I would suggest to you to use rather the second one, but since it has a couple of interesting ideas in it so I keep it at your disposal. It sorts only couples of arrays: that is, accepts at most two arrays the one to be sorted the other to be rearranged accordingly after the former has been sorted out.
Keep in mind that the argument "array1" passed to symmetricalSorting() must be the array that is meant to be sorted while the argument "array2" is the array whose symmetry you want to preserve/rebuild. Failing remembering this might cause you to sort the wrong array! The first argument is the array meant to undergo the sorting, the second argument is the array whose symmetry must not be fooled by the sorting of the first one. The third argument affects the type of sorting function used and may be:
- none or zero: means: use highestLast()
- 1 : means: use highestFirst()
- 2 : means: use highestLastCI()
- 3 : means: use highestFirstCI()
- other (say 4) : means: use nothing.
A few technicalities on its internal workings, if non interested skip to the next section with the better function.
We first initialized a few argument values:
- Our function will yield ultimately an array of two entries:
- FIRST ENTRY [0] will return the (by now sorted) array1 argument
- SECOND ENTRY [1] will return the array2 argument redrawn to exhibit the original symmetry with array1
- Now I make copies of the arrays: you can afford it as long as you're dealing with arrays not beyond the scope of a few hundred entries, which is fully reasonable for client side scripting.
The fact I yield copies will grant you that in case you want to leave unaffected the originals you can do that.
- We sort the array1 argument (that is: the first array)
- We execute calculations on the sorted array (copy1) to see when identical to array1 argument (which is left unaffected since we copied it, so it still exhibits the original symmetry with array2!).
- When identical, we pick the corresponding index entry from array2 and assign it to copy2: this is the trick which keeps the symmetry!
- In order to avoid to be fooled by possible copies (that is: an array might have two entries with the same name) we devised a way to mark each entry once found its collocation, that is what the smartDouble array is for.
- I suggest to you to use only arrays whose entries you're already sure, through some validation, are never undefined (empty) or carrying values like false or zero which might be interpreted as undefined. Especially Netscape might be induced to read a number like 0 as an undefined entry (workaround smart hint: a parseFloat() on the entry...)
- Keep in mind that the return is an array of 2 entries so you'd add the index (either or to the invoking statement; below are two possible syntaxes (both invoking index [1], but you could invoke [0] as well) to invoke these subroutines; the first assuming you want to sort array1 with the lowest value as first, the second assuming you need a sorting process with the highest value first and thus passing also the 3rd argument how.
If you put them in within an alert() (for instance providing the two testArrays at top of page as we do in the example below) you will see it works perfectly:
symmetricalSorting(testArray2,testArray1)
//or:
symmetricalSorting(testArray2,testArray1,1)
The Second Function
|
|
The function that relies on quicksort support more intensively
|
This is a more powerful function for multisorting, is named exactly multisort(), but its power goes with a few caveats:
- Accepts only one argument: an Array.
Each entry of such array, must be an array itself: the first of such listed arrays is the one that will undergo the sorting process.
multisort( new Array(array1, array2, array3 /*etc...*/) );
The sorting process is in increasing order: A towards Z. If you want to change that locate in the script the lines:
(copyA.toLowerCase()<copyB.toLowerCase())?-1:
(copyA.toLowerCase()>copyB.toLowerCase())?1:0;
and change them into:
(copyA.toLowerCase()<copyB.toLowerCase())?1:
(copyA.toLowerCase()>copyB.toLowerCase())?-1:0;
- All these arrays must be of the same size (length). If they are not, errors would occur. Thus it is your responsibility to check first that their sizes coincide.
You can append opportunistic (say "parasitic"?) entries to those that could be shorter, arguably all these artificially added entries would be carrying some simple value to which you will assign the meaning of flagging these spurious added entries, such as perhaps the keyword null, which I tested and caused no problems.
Please note that, to some degree (though not in absolute), seeking for a multisort makes sense only if the correspondences between your arrays were actually complete, not partials. This at least as an ideally rational idea, which I know not necessarily or always matches with data reality.
- The function affects the originals.
|