You are here: irt.org | FAQ | JavaScript | Object | Q341 [ previous next ]
Try this, which will allow you to specify which element to sort on:
<SCRIPT LANGUAGE="JavaScript"><!--
function showObjectArray(object,length,element) {
var output = '';
for (var i=0; i<length; i++) {
for (var j=0; j<element; j++) {
output += object[i][j] + ' ';
}
output += '<BR>';
}
document.write(output + '<BR>');
}
function myObjectBubbleSort(arrayName,length,element) {
for (var i=0; i<(length-1); i++)
for (var j=i+1; j<length; j++)
if (arrayName[j][element] < arrayName[i][element]) {
var dummy = arrayName[i];
arrayName[i] = arrayName[j];
arrayName[j] = dummy;
}
}
var Munros = new Array();
Munros[0] = new Array("Ben Nevis", 1, 1344, 4409, "NN 123 456" );
Munros[1] = new Array("Cairn Toul", 4, 1293, 4242, "XX 987 654" );
Munros[2] = new Array("Ben Macdui", 2, 1309, 4294, "AA 333 444" );
Munros[3] = new Array("Braeriach", 3, 1296, 4252, "BB 222 111" );
var objectArrayIndex = 4;
myObjectBubbleSort(Munros,4,0);
showObjectArray(Munros,4,5);
myObjectBubbleSort(Munros,4,1);
showObjectArray(Munros,4,5);
myObjectBubbleSort(Munros,4,2);
showObjectArray(Munros,4,5);
myObjectBubbleSort(Munros,4,3);
showObjectArray(Munros,4,5);
//--></SCRIPT>The above bubble sort attracted some feedback from Fredrik Ramsberg:
I'm attaching a file including two algorithms implemented in JavaScript, Insertion Sort and Shell Sort. Shell Sort is pretty much a fancy Insertion Sort, but much more efficient.
Typical # of comparisons made while sorting 200 items:
Bubble Sort: 20 000 Insertion Sort: 10 000 Shell Sort: 1 900
Typical # of comparisons made while sorting 500 items:
Bubble Sort: 125 000 Insertion Sort: 62 000 Shell Sort: 6 000
When looking at these figures, also keep in mind that the differences will increase drastically when increasing the number of items to sort. Doubling the number of items for a Bubble Sort routine makes it run four times slower. The same goes for Insertion Sort. Shell Sort, on the other hand, runs only 2.4 times slower. For ten times the original amount this means 100 times slower for Bubble Sort, and 18 times slower for Shell Sort.
Considering the difference between Shell Sort and Insertion Sort, I think it's well worth a little extra work implementing Shell Sort. Shell Sort isn't stable, but that's usually not important.
When looking at the code, you will probably see things that could be written in some clearer way. I've just made it work and tried to keep it short. Another noteworthy detail is the constant 's' in the Shell Sort routine. I've given it the value 3. There has been a debate of whether it should be 2 or 3, but my experiments indicate that 3 is better, so I'll use that. No one has this far been able to prove the properties of the algorithm, or even determine the best value of 's' through scientific methods - the algorithm has an element that makes it extremely difficult to analyze. However, it does work, it is efficient, and it isn't overly difficult to understand.
If you're interested, I would also recommend you to look at Quick Sort, which is very good on its own, but extremely powerful together with Insertion Sort. Quick Sort can sort the data until it is almost in order, then Insertion Sort can finish it off, putting everything in exactly its right place.
I've found what seems to be a good tutorial about search algorithms: http://www.toolsofcomputing.com/SortAlgorithms.htm
<script language="JavaScript"><!--
function showArray(text,object,length) {
document.write(text + ': ');
for (var i=0; i<length; i++)
document.write(object[i]+' ');
document.write('<BR>');
}
function makeArray() {
for (i = 0; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
}
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 myInsSort(arrayName,length) {
var j, i, v;
for (i=1, j=i; i<length; i++, j=i) {
v=arrayName[i];
while(true)
if (j-- >= 0 && arrayName[j] > v)
arrayName[j+1]=arrayName[j];
else
break;
arrayName[j+1]=v;
}
}
function myShellSort(arrayName,length) {
var j, i, v, h=1, s=3, k;
while(h < length)
h=s*h+1;
while(h > 1) {
h=(h-1)/s;
for (k=0; k<h; k++)
for (i=k+h, j=i; i<length; i+=h, j=i) {
v=arrayName[i];
while(true)
if ((j-=h) >= 0 && arrayName[j] > v)
arrayName[j+h]=arrayName[j];
else
break;
arrayName[j+h]=v;
}
}
}
var randArrayLength=100;
var randArray = new Array;
for(i=0; i<randArrayLength; i++)
randArray[i]=Math.floor((Math.random())*10000);
var myArray = new makeArray("z","l","t","a","r","q","b","j","c","y");
var myArrayLength = 10;
document.write('<br>myShellSort:<BR>');
showArray('<br>Unsorted',myArray,myArrayLength);
myShellSort(myArray,myArrayLength);
showArray('<br>Sorted',myArray,myArrayLength);
document.write('<br>myShellSort:<BR>');
showArray('<br>Unsorted',randArray,randArrayLength);
myInsSort(randArray,randArrayLength);
showArray('<br>Sorted',randArray,randArrayLength);
//--></script>I've also include a commented version of the QuickSort/InsertionSort combination. I've tried to optimize it, but making the code more compact makes it run slower. The rather big part of the code that is finding the pivot value actually does a part of the sorting as well, so it doesn't matter that it has a few instructions to execute. You could of course remove the comments, which may speed it up a little.
There is also a demonstration that examines the differencies in time consumption, which can be useful if you want to compare them or try to tweak the values of the parameters for the functions:
<html>
<head>
<script language="JavaScript">
function showArray(text,object,length) {
document.write(text + ': ');
for (var i=0; i<length; i++)
document.write(object[i]+' ');
document.write('<BR>');
}
function makeArray() {
for (i = 0; i<makeArray.arguments.length; i++)
this[i] = makeArray.arguments[i];
}
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 myInsSort(arr,length) {
var j, i, v;
for (i=1, j=i, v=arr[i]; i<length; arr[j+1]=v, i++, j=i, v=arr[i])
while(j-- >= 0 && arr[j] > v)
arr[j+1]=arr[j];
}
function myShellSort(arr,length) {
var j, i, v, h, k, s=3;
for (h=1; h < length; h=s*h+1);
while (h=(h-1)/s)
for (k=0; k<h; k++)
for (i=k+h, j=i, v=arr[i]; i<length; arr[j+h]=v, i+=h, j=i, v=arr[i])
while((j-=h) >= 0 && arr[j] > v)
arr[j+h]=arr[j];
}
function myQuickSortSub(arr, first, last) {
// The value of lim in the following line determines the minimum length of sequences to be sorted.
// Shorter sequences are left for Insertion Sort to deal with later. This speeds up sorting.
var i, j, m, p, temp, lim=8, lim1=lim + 1;
while(first>=0) {
i=first - 1; j=last;
// This block finds the median of the first, last and middle value, and uses it as a pivot value (p)
m=Math.floor(first + (last-first)/2);
if( arr[m] < arr[first]) {
temp=arr[m]; arr[m]=arr[first]; arr[first]=temp;
}
if( arr[last] < arr[m]) {
temp=arr[m]; arr[m]=arr[last]; arr[last]=temp;
}
if( arr[m] < arr[first]) {
temp=arr[m]; arr[m]=arr[first]; arr[first]=temp;
}
p=arr[m];
// Do the actual sorting
while ( ++i < j)
if ( arr[i] > p) {
while(arr[j] > p && --j > i);
if( j > i) {
temp=arr[j]; arr[j]=arr[i]; arr[i]=temp;
}
}
// The sorting has divided the array into two parts, where all the elements in the first part
// are smaller than the elements in the second part. Now, sort the shortest part of the array
// with a recursive call to this routine, and the longest part with another iteration. If we
// would use recursion for both parts, the worst case stack depth is O(n), now it's O(log n).
// If a part is shorter than lim, just leave it unsorted -- Insertion Sort will take care of
// it after Quick Sort has completed.
if( --i - first > last - i - 1) {
if( last > i + lim1)
myQuickSortSub(arr, i + 1, last);
if( i > first + lim)
last=i;
else
first=-1; // Signal to end function
} else {
if( i > first + lim)
myQuickSortSub(arr, first, i);
if( last > i + lim1)
first=i+1;
else
first=-1; // Signal to end function
}
}
}
function myQuickSort(arr, length) {
myQuickSortSub( arr, 0, length - 1);
myInsSort(arr, length);
}
var iterations=20;
var randArrayLength=500;
var randArray = new Array;
var timeDifference;
var timeA, timeB;
document.writeln('Iterations: ' + iterations + '<BR>');
document.writeln('Array lenght: ' + randArrayLength + '<BR><BR>');
timeDifference=0;
for(var i=0; i < iterations; i++) {
for(j=0; j<randArrayLength; j++)
randArray[j]='x' + Math.floor((Math.random())*9000 + 1000);
timeA = new Date();
myQuickSort(randArray,randArrayLength);
timeB = new Date();
timeDifference += (timeB - timeA);
}
// showArray('<br>Sorted',randArray,randArrayLength);
document.writeln('QuickSort Time: ' + Math.floor(timeDifference/iterations) + ' ms<BR><BR>');
timeDifference=0;
for(var i=0; i < iterations; i++) {
for(j=0; j<randArrayLength; j++)
randArray[j]='x' + Math.floor((Math.random())*9000 + 1000);
timeA = new Date();
myShellSort(randArray,randArrayLength);
timeB = new Date();
timeDifference += (timeB - timeA);
}
// showArray('<br>Sorted',randArray,randArrayLength);
document.writeln('ShellSort Time: ' + Math.floor(timeDifference/iterations) + ' ms<BR><BR>');
timeDifference=0;
for(var i=0; i < iterations; i++) {
for(j=0; j<randArrayLength; j++)
randArray[j]='x' + Math.floor((Math.random())*9000 + 1000);
timeA = new Date();
myInsSort(randArray,randArrayLength);
timeB = new Date();
timeDifference += (timeB - timeA);
}
// showArray('<br>Sorted',randArray,randArrayLength);
document.writeln('InsertionSort Time: ' + Math.floor(timeDifference/iterations) + ' ms<BR><BR>');
</script>
</head>
<body>
</body>
</html>