You are here: irt.org | Articles | JavaScript | Object | Arrays, Object Arrays and Sorting [ previous next ]
Published on: Sunday 21st December 1997 By: Martin Webb
This article will show how to sort arrays using the JavaScript 1.1 array sort method. We'll also describe the different options available during sorting, and how to sort arrays for browsers that don't support the sort method, or where the sort method does not work correctly.
For JavaScript 1.1 browsers we'll also describe how to implement a bubble sort in JavaScript, which will be used to sort object arrays.
An array can be created using the JavaScript 1.1 Array object, or by constructing an array manually using a makeArray() function.
JavaScript 1.1 Array object:
myArray = new Array("one","two","three","four");JavaScript 1.0 makeArray() function:
function makeArray() {
for (i = 0; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
}
var myArray = new makeArray("one","two","three","four");For simplicity, I always use a derivative of the JavaScript 1.0 makeArray.
The difference between arrays in JavaScript 1.1 and JavaScript 1.0 are that, in JavaScript 1.1 you can refer to the arrays elements either by their index number or their name, whereas in JavaScript 1.0 you can only refer to them by their index number.
In the previous myArray example the first element in JavaScript 1.1 be reffered to as either myArray[0] or myArray["one"], whereas in JavaScript 1.0 it can only be reffered to as myArray[0].
In JavaScript 1.1, an array has a length property that indicates the number of elements in the array. So for the previous definition of myArray[], myArray.length would return 3. Whereas in JavaScript 1.0 this would cause a JavaScript error.
There are at least three ways around this problem.
1. By the inclusion of an array length variable, e.g. myArrayLength:
function makeArray() {
for (i = 0; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
}
var myArray = new makeArray("one","two","three","four");
var myArrayLength = 4;2. By including the length of the array as the first item of the array, i.e. myArray[0], although this then breaks the principles of OO by including information about the object within the object:
function makeArray() {
this[0] = makeArray.arguments.length;
for (i = 1; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
}
var myArray = new makeArray("one","two","three","four");3. By creating a length property whilst manually creating the array (although this may not work in JavaScript 1.0):
function makeArray() {
for (i = 0; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
this.length = makeArray.arguments.length;
}
var myArray = new makeArray("one","two","three","four");The remainder of this article will use the first makeArray() version, where a variable holds the length of the array.
It isn't necessary to create the whole of the array in one go. It is possible to populate the array as we progress through the script, by first creating an empty array. By maintaining the value of the myArrayLength variable uptodate, we can tell at any one moment the length of myArray[]:
var myArray = new Array(); myArray[myArrayLength] = "one"; var myArrayLength = 1; myArray[myArrayLength] = "two"; var myArrayLength = 2; myArray[myArrayLength] = "three"; var myArrayLength = 3; myArray[myArrayLength] = "four"; var myArrayLength = 4;
Object arrays have already been described in several previous articles.
However, the following is a simple object array containing a date (day, month and year) and a text item. The myObjectArray[] contains four (i.e. objectArrayIndex) Objects:
function Object(day,month,year,text) {
this.day = day;
this.month = month;
this.year = year;
this.text = text;
}
function setObject(day,month,year,text) {
myObjectArray[objectArrayIndex++] = new Object(day,month,year,text);
}
var objectArrayIndex = 0;
var myObjectArray = new Array();
setObject(4,11,97,"abc");
setObject(3,10,1996,"123");
setObject(2,9,1995,"122");
setObject(1,12,1998,"124");Note the following will cause errors on JavaScript 1.0. Therefore, to avoid these errors, the results have been hardcoded into the document.
As already mentioned JavaScript 1.1 has an array sort method, which can be used in two different ways:
Which sorts lexicographically (in dictionary order) according to the string conversion of each element, i.e. the JavaScript 1.1 sort method will first convert the elements to strings, therefore 4 becomes "4" and 33 becomes "33", when sorted the 33 will always come before 3.
or
Where compareFunction specifies a function that defines the sort order.
A typical compare function looks like this:
function myCompare(a,b) {
/*
add your own logic here
*/
return x;
}Where x can have three values:
The inbuilt JavaScript 1.1 sort method will pass in turn two elements of the required array to the specified compare function, and will accept the return value as an indication of the sort order of the two elements.
As can be seen, you are required to write your own logic to compare the two elements.
A simple compare function to compare numbers would look like this:
function compareNumbers(a,b) { return a - b; }To demonstrate this we can sort the strings "one", "two", "three" and "four" and show the results before and after with the showArray() function:
function showArray(text,object,length) {
document.write(text + ': ');
for (var i=0; i<length; i++)
document.write(object[i]+' ');
document.write('<BR>');
}
var myArray = new Array("one","two","three","four");
var myArrayLength = 4;
showArray('Unsorted',myArray,myArrayLength);
myArray.sort();
showArray('Sorted',myArray,myArrayLength);Which when run produces the following:
Unsorted: one two three four
Sorted: four one three two
However if we did this with the numbers 333, 5, 44, 2222 and 11111:
var myArray = new Array(5,44,333,2222,11111);
var myArrayLength = 5;
showArray('Unsorted',myArray,myArrayLength);
myArray.sort();
showArray('Sorted',myArray,myArrayLength);Then it would produce the following:
Unsorted: 5 44 333 2222 11111
Sorted: 11111 2222 333 44 5
Whereas, if we included the compareNumber() function:
function compareNumbers(a,b) { return a - b; }
var myArray = new Array(333,5,44,2222,11111);
var myArrayLength = 5;
showArray('Unsorted',myArray,myArrayLength);
myArray.sort(compareNumbers);
showArray('Sorted',myArray,myArrayLength);Then it would produce the following:
Unsorted: 11111 2222 333 44 5
Sorted: 5 44 333 2222 11111
As mentioned previously, the above will not work in JavaScript 1.0, as the sort method was not introduced until the JavaScript 1.1.
When attempting to sort an array created using a typical makeArray() function then it will not work, as the object created is not an inbuilt JavaScript Array object but a user defined object which doesn't have a sort method.
The next section will attempt to describe how we can sort in JavaScript 1.0, and how to sort user defined arrays and arrays of objects.
A Bubble Sort, for those who are unfamiliar with the expression, is one of the most simplist, if not efficient, means of sorting a list. Basically, you start at the beginning of the list and compare the first entry with all the others one after another. If at any stage you find that the first entry is greater than the other entry being compared, you swap them over and continue. Once you've compared the first entry with all the others you repeat the process, but this time comparing the second entry with all those entries that follow it in the list, and so on until you've compared all the entries in turn against all those that follow.
If you do this - then at the end you'll have a sorted list.
The following script introduces the myBubbleSort() function that when passed an array will sort the array using the Bubble Sort method:
function myBubbleSort(arrayName,length) {
for (var i=0; i<(length-1); i++)
for (var j=i+1; j<length; j++)
if (arrayName[j] < arrayName[i]) {
var dummy = arrayName[i];
arrayName[i] = arrayName[j];
arrayName[j] = dummy;
}
}
var myArray = new makeArray("one","two","three","four");
var myArrayLength = 4;
showArray('Unsorted',myArray,myArrayLength);
myBubbleSort(myArray,myArrayLength);
showArray('Sorted',myArray,myArrayLength);
var myArray = new makeArray(333,5,44,2222,11111);
var myArrayLength = 5;
showArray('Unsorted',myArray,myArrayLength);
myBubbleSort(myArray,myArrayLength);
showArray('Sorted',myArray,myArrayLength);Which when run produces:
Unsorted: one two three four
Sorted: four one three two
Unsorted: 333 5 44 2222 11111
Sorted: 5 44 333 2222 11111
When trying to sort an array of objects we can use the exact same approach as when sorting arrays, all we have to be more subtle when comparing one object with another. For example, we can sort the object array described earlier:
showArray('Unsorted',myObjectArray,objectArrayIndex);
myBubbleSort(myObjectArray,objectArrayIndex);
showArray('Sorted',myObjectArray,objectArrayIndex);If we were to sort them using the previous definition of the myBubbleSort() function, then it would produce the following:
Unsorted: [object Object] [object Object] [object Object] [object Object]
Sorted: [object Object] [object Object] [object Object] [object Object]
There is a major problem here, the value of each Object appears to be '[object Object]'.
What is required is a simple facility to covert the value of each Object to a suitable string before comparing them. Which is exactly what was covered within a previous article Text Strings and String Objects.
By introducing a toString prototype for Object, we can control the conversion of the string value of each Object:
function myObjectToString() {
return '' + this.day + this.month + this.year + this.text;
}
Object.prototype.toString = myObjectToString;
showArray('Unsorted',myObjectArray,objectArrayIndex);
myBubbleSort(myObjectArray,objectArrayIndex);
showArray('Sorted',myObjectArray,objectArrayIndex);The myObjectToString() function returns a string made up of the required Objects day, month, year and text properties concatenated together.
Which when run produces the following:
Unsorted: 41197abc 3101996123 291995122 1121998124
Sorted: 1121998124 291995122 3101996123 41197abc
However, the result is not the desired result.
By adjusting the contents of the myObjectToString() we can alter the string value of each Object which will then effect the sort routine:
function padout(number) { return (number < 10) ? '0' + number : number; }
function y2k(number) { return (number < 1000) ? number + 1900 : number; }
function myObjectToString() {
return '' + y2k(this.year) + '/' + padout(this.month) + '/' + padout(this.day) + ' ' + this.text;
}
Object.prototype.toString = myObjectToString;
showArray('Unsorted',myObjectArray,objectArrayIndex);
myBubbleSort(myObjectArray,objectArrayIndex);
showArray('Sorted',myObjectArray,objectArrayIndex);The myObjectToString() function now returns a formatted string made up of the required Objects year, month, day and text properties concatenated together.
Which when run produces the following:
Unsorted: 1997/11/04 abc 1996/10/03 123 1995/09/02 122 1998/12/01 124
Sorted: 1995/09/02 122 1996/10/03 123 1997/11/04 abc 1998/12/01 124
Which are all correctly sorted into date order.
Unfortunately, the prototype method is not supported in JavaScript 1.0, so some other approach needs to be found.
To correctly sort object arrays, will require converting the value of each object to a string before comparing it with another object. Displaying an object will also require converting the value of each object to a string.
As we cannot rely on the prototype method of adapting the toString method, we will have to manually convert the value of the object each and every time it is sorted and displayed. It would also require an specific version of the sort and display functions for each and every type of user defined object.
This could be a bit time consuming, so we'll cheat. When we create each object we'll generate a new property, called value, which will hold the string value of the rest of the object.
When we come to sort or display the object, we'll use the value property. However, you must be aware that if you amend one of the objects other properties, then the value property will also need to be amended, or it'll not be a true reflection on the objects string value.
Although its possible to include an extra value property to object arrays, it is not possible to add it to normal arrays, unless you make them object arrays too, therefore we'll need two versions of the sort and display functions, one for normal arrays and another for object arrays:
function makeArray() {
for (i = 0; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
}
function padout(number) { return (number < 10) ? '0' + number : number; }
function y2k(number) { return (number < 1000) ? number + 1900 : number; }
function ownObject(day,month,year,text) {
this.value = '' + y2k(year) + '/' + padout(month) + '/' + padout(day) + ' ' + text;
this.day = day;
this.month = month;
this.year = year;
this.text = text;
}
function setObject(day,month,year,text) {
myObjectArray[objectArrayIndex++] = new ownObject(day,month,year,text);
}
var objectArrayIndex = 0;
var myObjectArray = new Array();
setObject(4,11,97,"abc");
setObject(3,10,1996,"123");
setObject(2,9,1995,"122");
setObject(1,12,1998,"124");
function showArray(text,object,length) {
document.write(text + ': ');
for (var i=0; i<length; i++)
document.write(object[i]+' ');
document.write('<BR>');
}
function myBubbleSort(arrayName,length) {
for (var i=0; i<(length-1); i++)
for (var j=i+1; j<length; j++)
if (arrayName[j] < arrayName[i]) {
var dummy = arrayName[i];
arrayName[i] = arrayName[j];
arrayName[j] = dummy;
}
}
function showObjectArray(text,object,length) {
document.write(text + ': ');
for (var i=0; i<length; i++)
document.write(object[i].value+' ');
document.write('<BR>');
}
function myObjectBubbleSort(arrayName,length) {
for (var i=0; i<(length-1); i++)
for (var j=i+1; j<length; j++)
if (arrayName[j].value < arrayName[i].value) {
var dummy = arrayName[i];
arrayName[i] = arrayName[j];
arrayName[j] = dummy;
}
}
showObjectArray('Unsorted',myObjectArray,objectArrayIndex);
myObjectBubbleSort(myObjectArray,objectArrayIndex);
showObjectArray('Sorted',myObjectArray,objectArrayIndex);
var myArray = new makeArray("one","two","three","four");
var myArrayLength = 4;
showArray('Unsorted',myArray,myArrayLength);
myBubbleSort(myArray,myArrayLength);
showArray('Sorted',myArray,myArrayLength);
var myArray = new makeArray(333,5,44,2222,11111);
var myArrayLength = 5;
showArray('Unsorted',myArray,myArrayLength);
myBubbleSort(myArray,myArrayLength);
showArray('Sorted',myArray,myArrayLength);Which run produces the following:
Text Strings and String Objects