// ====================================================================================================================
// Copyright (c) 2003,2004 Henk Reints, http://henk-reints.nl
// -----------------------------------------------------------
//
// Usage: first read this as a text file in order to learn about sorting. (with line wrapping DISabled!)
// then run it as follows to see it in action:
// - open a Command Prompt in the directory where you saved this file
// - type "cscript hr$arraysortdemo.wsf"
// - press [Enter]
//
// About sorting
// -------------
// How can Array elements be sorted?
// Well, suppose we do the following (where A represents the Array containing the elements to be sorted):
//
// // Step 1: find the smallest element in A (k will eventually point to the smallest element of A):
//
// for (var k = 0, i = k + 1; i < A.length; i++) {if (A[i] < A[k]) k = i}
//
// // Step 2: exchange the elements 0 and k:
//
// var x = A[0]; A[0] = A[k]; A[k] = x
//
// Then A will now have its smallest element at its first position and the rest is random.
// This process could be repeated for the part of A behind this position,
// then we would get the second smallest element at the second position.
// And that could be repeated throughout the entire Array, giving the following sorting algorithm:
// --------------------------------------------------------------------------------------------------------------------
Array.prototype.simpleSort = function simpleSort ()
{
for (var j = 0; j < this.length; j++)
{ for (var k = j, i = j + 1; i < this.length; i++) {if (this[i] < this[k]) k = i}
if (k != j) {var x = this[j]; this[j] = this[k]; this[k] = x}
}
}
// --------------------------------------------------------------------------------------------------------------------
// This is a correct sorting algorithm, but it is not very efficient.
// The number of compares it does will be (assuming N is the number of elements in A):
//
// for the first search: N-1 (i.e. the first time that the inner 'for' loop is executed)
// then N-2 (i.e. the second time that the inner 'for' loop is executed)
// then N-3
// etc. :
// finally 3
// then 2 (i.e. the second last time that the inner 'for' loop is executed)
// then 1 (i.e. the very last time that the inner 'for' loop is executed)
//
// All these counts must be added together, so 1 + 2 + 3 + ... + (N-3) + N-2) + (N-1)
// and the result is:
// N * (N-1) / 2
//
// This is practically equal to square(N)/2 [square(N) means N*N, of course].
//
// Now suppose we have to sort 100 elements. That will take 100*99/2 = 4950 compares.
// Could we do something smarter? Yes!
//
// For sorting 50 elements we would need only 50*49/2 = 1225 compares.
// And for sorting 2 sets of 50 elements it would need 2*1225 = 2450 compares.
// Now let's simply split the original 100 elements into 2 sets of 50 elements each and sort them.
// Then we'll get 2 sorted sets of 50 elements, which has taken 2450 compares.
// But then these 2 sorted sets must still be merged into 1 single sorted set.
// And that appears to be easy AND efficient.
// Suppose the elements are numbers written on cards.
// Then we have 2 stacks of 50 numbered cards which HAVE ALREADY BEEN SORTED.
// Put those 2 stacks of cards on the table face up (assuming the sorting is such that the smallest
// number of each set is now on top).
// You'll see 2 numbers.
// Take the card with the smallest number and put that face down on a new stack.
// Then repeat this until one of the input stacks is empty.
// Put the remaining other stack face down on the new stack.
// Ready.
// You now have 1 set of cards, sorted by the numbers written on them.
// And how many compares have you done? At least 50 and at most 99. Let's assume the worst case, so 99.
// The total number of compares we have done to sort 100 elements is now: 2450 + 99 = 2549.
// That's just a little bit more than half of the 4950 compares needed to sort them with the first algorithm!
//
// So sorting a set can be done more efficiently by dividing the set into two halves, sorting those halves,
// and then merging them together. It will take just a bit more than half the time of the elementary sorting
// method.
//
// Now let's be really smart: why not do the very same for sorting those 2 halves?
// We'd gain another factor 2.
// For sorting 25 elements we need only 25*24/2 = 300 compares.
// Sorting 50 elements would then take 2*300+49 = 649 compares instead of 1225.
//
// We'll now repeat this process until the set can no longer be divided in 2 halves.
// That's the smart way of sorting.
// The total number of compares will become practically equal to N * Log2(N) [where Log2 means the base-2 logarithm].
// For large values of N that's a VERY significant improvement!
//
// When programming in a modern language like JavaScript, we can implement this by RECURSIVE programming.
// That means a functions that can invoke itself.
// Look:
// --------------------------------------------------------------------------------------------------------------------
Array.prototype.getSortedCopyRecursive = function getSortedCopyRecursive()
{
function merge (A1, A2) // assumes that A1 and A2 are both already sorted in the correct order
{ var A = new Array (A1.length + A2.length) // new Array for result
for (var i = 0, i1 = 0, i2 = 0; i1 < A1.length && i2 < A2.length; ) // loop until either A1 or A2 is done
{ if (A1[i1] <= A2[i2]) A[i++] = A1[i1++] // take the "left card" if that's the smallest
else A[i++] = A2[i2++] // else take the "right card"
} // now either A1 or A2 is not yet done
for (; i1 < A1.length; A[i++] = A1[i1++] ); // one of these 2 loops will actually
for (; i2 < A2.length; A[i++] = A2[i2++] ); // copy the remainder of either A1 or A2 to A
return A // ready, return the result
}
function sort (A)
{ if (A.length < 2) return A.slice(0) // nothing to sort, leave with a copy of A
var A1 = sort (A.slice (0, A.length/2) ) // sort the first half
var A2 = sort (A.slice (A.length/2) ) // and the second half
return merge (A1, A2) // and return them merged together
}
return sort (this)
}
// --------------------------------------------------------------------------------------------------------------------
// This method will return a sorted COPY of the Array.
// Isn't it nice?
//
// There's another way to increase the speed of sorting.
// As you can see, we are constantly copying or moving the actual Array elements to other places.
// If the elements themselves are large (e.g. long Strings or so) then that takes a lot of time.
// It's much better to build another Array which contains pointers to the elements that must be sorted,
// and then manipulate only those pointers:
// --------------------------------------------------------------------------------------------------------------------
Array.prototype.getSortedIndexRecursive = function getSortedIndexRecursive()
{
var A = this
function merge (X1, X2)
{ var X = new Array (X1.length + X2.length)
for (var i = 0, i1 = 0, i2 = 0; i1 < X1.length && i2 < X2.length; )
{ if (A[X1[i1]] <= A[X2[i2]]) X[i++] = X1[i1++]
else X[i++] = X2[i2++]
}
for (; i1 < X1.length; X[i++] = X1[i1++] );
for (; i2 < X2.length; X[i++] = X2[i2++] );
return X
}
function sort (X)
{ if (X.length < 2) return X
var X1 = sort (X.slice (0, X.length/2) ) // get sorted index of the first half
var X2 = sort (X.slice (X.length/2) ) // and of the second half
return merge (X1, X2) // and return them merged together
}
for (var i = 0, X = []; i < this.length; X[i] = i++); // build an index
return sort (X) // and return it sorted
}
// --------------------------------------------------------------------------------------------------------------------
// There is however a price to pay for recursive programming.
// The code looks very easy, but internally the computer has to do lots of memory management,
// causing overhead that is consuming resources you'd better use for what you're up to, which is sorting.
// The createIndex method defined in the file hr$arraysort.js is a non-recursive variant of the
// last method described here.
//
// for seeing these algorithms in action you can start the script hr$arraysortdemo.wsf
// ====================================================================================================================
// End of file -- Copyright (c) 2003,2004 Henk Reints, http://henk-reints.nl