Keeping associations in a multi-column sort...

[krycek]

Right, I have two arrays, which are associated. One array stores some string data, and the other stores the frequency of the strings.

Now, what I want to do is sort the arrays by frequency, so to do that I sort the second array, and whatever I do to the second, I do to the first, yeah?

Now this is easy using a bubble sort, because the whole thing relies on comparisons and swaps. Hence, if I am doing one swap, I can simply tell it to do two.

However, a bubble sort is painfully slow when dealing with large amount of data (I am currently testing this on a 160Kb string). Threfore, I am changing my method to use a radix sort, which is the quickest method I know for sorting numbers in this scenario. (Compared to bubble sort, quick sort, and merge sort, which are the other algorithms I have available.)

My problem is that, although I can sort my second array (or the first!) with ease, I cannot keep the association between arrays!

Here is my standard radix sort function:


//----- Radix Sort Array (base 2) --------------------------------------------------------------------------------------
Array.prototype.rsort = function(bits) {
if (!bits) bits = 32
var tempArray = this.copy() // Copy the current array
var b0 = new Array() // Bin for 0 digits
var b1 = new Array() // Bin for 1 digits
for (var i = 0; i < bits; i++) {
var mask = 1 << i // Digit (2^i)
var biggest = 2 << i // If all of tempArray is smaller, we're done
var zeros = 0 // Number of elements in b0, b1
var ones = 0
var found = 0 // Any digits past i?
for (var j = 0; j < tempArray.length; j++) { // Sort into bins b0, b1
if ((tempArray[j] & mask) == 0) {
b0[zeros++] = tempArray[j]
} else {
b1[ones++] = tempArray[j]
}
if (tempArray[j] >= biggest) // Any more digits to sort on?
found = 1
}
for (j = 0; j < zeros; j++) {
tempArray[j] = b0[j] // Concatenate b0, b1 back to tempArray
}
for (j = 0; j < ones; j++) {
tempArray[j + zeros] = b1[j]
}
if (!found) break
}
return tempArray
}


...any ideas how I can change this so that the order of the data array reflects the sorted order of the numbers array? i.e. keeps the association.

::] krycek [::

[chrismiceli]

i know there is a method like this
arrayname.sort(), don't know how to use it, mabey that will help.

[beetle]

Sorry, I'm not with all the bit manipulation stuff, although I know how to do user-defined sorts with associative arrays. Can I see your arrays?

[krycek]

chris... I can't use the built-in sort array because it only sorts one array, no association. Also, I use my own sort functions because that allows me to optimise the sorting method according to the data.

beetle... my arrays are very simply, two arrays.

1...............2................

werg.........4.................
gjkl............8................
jsry............1...............
rewt...........36.............

see, the first array simply stores strings, which in this case are all x chars long. The second array stores the number of time that the string at the corresponding index in the first array appears in my main string.

e.g. if I look at werg, above, I can say, array1[0] and get werg, and then array2[0] is 4, meaning werg appears 4 times in my original string.

however, if I sort the second array, I get, 1, 4, 8, 36, and the items in the first array should move too, to get jsry, werg, gjkl, rewt. That way, the association is kept. However, how can I do this? Using my unmodified sort functions (designed to sort a single array) only one array gets sorted. And although I can easily modify my bubble sort so that both arrays get sorted, I am not sure how to do this with a radix sort.

Any ideas? I am not sure if there is a better way of keeping the association...

::] krycek [::

[beetle]

Well, this method will work for sorting a 2D array based on the contents of a value in the 2nd dimension. Yes, it uses a 1 global function and 1 global variable, but it works :D

Lemme know whatcha think....function Array.prototype.usort(i){
window.sortIndex = i;
this.sort(sortHandler);
}

function Array.prototype.dump() {
var a = "";
for (var i in this)
if (typeof this[i] != 'function') a+= i + " : " + this[i] + "\n";
alert(a);
}

function sortHandler(a, b) {
var aa = a[window.sortIndex];
var bb = b[window.sortIndex];
if (aa == bb) return 0;
return (aa < bb) ? -1 : 1;
}

var myData = [
['werg',4],
['gikl',8],
['jsry',1],
['rewt',1]
];

myData.dump();
myData.usort(1);
myData.dump();Note: PHP has a syntax to keep the sort-handling function in the class. I tried porting it over but it doesn't work....

[krycek]

Hmmm... the only trouble is, that is basically a bubble sort... i.e. you are comparing two items, and according to a condition, swapping them. This is fine in principle, but the optimised radix sort function I posted is roughly 4000 times quicker when used for what I want.

So you can see why I want to change my existing bubble sort method and use the radix sort instead...

Don't worry, I'll keep at it :)

Thanks for the ideas all the same :)

::] krycek [::