Well this is my first post at codewerks, so let’s go…
Introduction
During the development of version 3.4 ( coming soon! ) of TTIW, I needed a simple function for sorting an array whose length was dynamic. Meaning that it starts with 0 elements and it grows to a maximum number of elements. The array needed to be sorted as elements where added. Once the maximum number of elements was reached, the function should behave as it would for a fixed length array.
Now, there is a very simple way to acomplish this in Javascript by using the JavaScript Array sort() Method. However due to some particulars of the case involved ( more below ), this method was of no use, so I had to develop my own little function. Truth is, I think it’s quite a nice algorithm for the task and though I doubt it will get into Knuth’s Bible Vol.3 ( BTW, I have not read this volume, though, I only have volume one. So, who knows, maybe some variation of this is already there.. ), I thought it was nice to write a post about this. So here we go..
The first version. Sorting the array while it is being created.
Now the first version can be accessed here. The function is the following ( It’s ultra commented, so that it’s inner workings are made clear. ):
function dynamicArraySort(val, arr, maxarrlen) {
//Check if arr already has some value.
if(arr.length==0) return [val]; //It doesn’t return an arr with val as it’s only element
//Determine how big the next loop will be. If array’s Maximum length has not been reached, then add one more,
//so that if there is nothing filled it will be filled by this value ( or the ones that come after it ).
var till = maxarrlen;
if(arr.length<maxarrlen) till = arr.length+1;
//Iterate through the elements on the array
for(var i=0; i<till; i++) {
//evaluate value against the array in that position.
if(val>= arr[i]) {
//It is bigger or the same.. swap every element after this one with the following one.
for(var j=(till-1); j>=i; j–) {
arr[j]=arr[j-1];
}
//change this element to val
arr[i]=val;
//Done for this value, stop execution, (since we have found an element smaller than value and we have changed it and all the subsequent elements)
return arr;
}
//Test if there is allready an element filled on this position.
if(!arr[i]) {
//There is not, add this value to this position, stop execution and return array
arr[i] = val;
return arr;
}
}
//Return array (will only happen if the array allready had a length of maxarrlen and val was not bigger than any element on the array)
return arr;
}
You can test the function here, and it will show execution by a very helpfull ( but annoying ) alert() window on every new value added and evaluated into the array.
Another test of the function can be accessed here, this one feeds the function a set of random values ( and it doesn´t have the annoying alert ).
Now, I’m pretty sure that there are plenty of other different algorithms to do the same thing.. but this one seems fairly well suited for this particular task. Now let’s get a little more into my actual problem.
The second version. Do the same on an array of arrays, and sort by the value of the first element in the array.
Actually part of my problem was that I needed to sort an array of arrays by the value of one of the elements in the array. So I had to modify the function to do the evaluation based on this. The new version was:
function dynamicArraySort(narr, arr, maxarrlen) {
//Check if arr has allready some value.
if(arr.length==0) return [narr]; //It doesn’t return an arr with val as it’s only element
//Determine how big the next loop will be. If array’s Maximum length has not been reached, then add one more,
//so that if there is nothing filled it will be filled by this value ( or the ones that come after it ).
var till = maxarrlen;
if(arr.length<maxarrlen) till = arr.length+1;
//Iterate through the elements on the array
for(var i=0; i < till; i++) {
//Test if there is allready an element filled on this position.
if(!arr[i]) {
//There is not, add this value to this position, stop execution and return array
arr[i] = narr;
return arr;
}
//evaluate value against the array in that position.
if(narr[0] >= arr[i][0]) {
//It is bigger or the same.. swap every element after this one with it’s following one
for(var j=(till-1); j > =i; j–) {
arr[j]=arr[j-1];
}
//change this element to val
arr[i]=narr;
//Done for this value, stop execution, (since we have found an element smaller than value and we have changed it and all the subsequent elements)
return arr;
}
}
//Return array (will only happen if the array allready had a length of maxarrlen and val was not bigger than any element on the array)
return arr;
}
There is no real variations bettween this function and the other, except that we are dealing with an array of arrays. The evaluation is done against the element in postion [0] of the array. ( I had to move the test of wether an element has a value to the top of the loop, since javascript will throw an error if you try to access the elements of an array that does not exist. )
You can test it here and here.
Now, notice how when using the examples above, the second element of the array has a number on the left ( something like a-24 ). This was done just for testing purposes, but, and this is the interesting part and the problem I actually had to solve. The number represents the actual step in which the new array was evaluated into the function. As you can see in the second test, the last added element of the same value will be stored before the ones that came before it. Now this was my problem. I needed to sort the array by the value of the first element in the array, but if an element with the same value was added, it needed to be placed after and not before the elements with this same value. So it’s on to version 3…
Version 3, Recursiveness…
Well to solve this problem I had to use recursion. Here is the new version:
function dynamicArraySort(narr, arr, maxarrlen, start) {
//Check if arr has allready some value.
if(arr.length==0) return [narr]; //It doesn’t return an arr with val as it’s only element
//Determine how big the next loop will be. If array’s Maximum length has not been reached, then add one more,
//so that if there is nothing filled it will be filled by this value ( or the ones that come after it ).
var till = maxarrlen;
if(arr.length<maxarrlen) till = arr.length+1;
//Iterate through the elements on the array
for(var i=start; i<till; i++) {
//Test if there is allready an element filled on this position.
if(!arr[i]) {
//There is not, add this value to this position, stop execution and return array
arr[i] = narr;
return arr;
}
//evaluate value against the array in that position.
if(narr[0]== arr[i][0]) {
//It is the same.. do a recursive call to this same function starting on the next element.
return dynamicArraySort(narr, arr, maxarrlen, i+1);
} else if(narr[0] > arr[i][0]) {
//It is bigger swap every element after this one with it’s following one
for(var j=(till-1); j>=i; j–) {
arr[j]=arr[j-1];
}
//change this element to val
arr[i]=narr;
//Done for this value, stop execution, (since we have found an element smaller than value and we have changed it and all the subsequent elements)
return arr;
}
}
//Return array (will only happen if the array allready had a length of maxarrlen and val was not bigger than any element on the array)
return arr;
}
Now, the big difference here is that if an element is of the same value as one before, the function calls itself but starting the loop on the next element of the array (of arrays). That’s the reason of the start paramenter on this new version. Neat!!!
Well, that solved the problem, you can test the final version here and here
Prologue
The function is pretty sweet, the only thing that I would like to add is that I needed to do this on an array that will store a maximum of 5 values out of something from 3 to 120 different values. For solving this, the algorithm is very good, of course if the array had to store a bigger amount of values, the algorithm can ( and should ) be refined.. but I’m leaving that for another time.
