To Foot

JavaScript Sorting and Order.

See "About This JavaScript Site" in JavaScript Index and Introduction.

Material on this new page is in part collected from elsewhere on the site.

Sorting

General

In any language, for any process such as sorting or shuffling, where data are repeatedly repositioned, one should avoid repeatedly moving large items. It is quicker to move indexes or adjust pointers instead.

Note that sorting is not always guaranteed stable; the order of equally-valued items may be changed.

The simple "Bubble" sort, comparing adjacent items, takes time O(N²) for sorting N items. Better methods take time O(N×ln(N)) or O(N^k) for k around 1.3; but only for special cases can time O(N) be achieved.

See also my JavaScript Random, and in Wikipedia.

JavaScript

JavaScript uses Objects throughout, so "moving" operations basically only change pointers and do not actually move large stored data.

Array Objects already have an efficient .sort method. With no parameter, the elements are converted to Strings for comparison. For numbers of varying length or mixed sign, that does not give numerical order. Otherwise, the parameter is a comparison function.

ECMA-262 does not require stable sorting, but some implementations may give it (in stable sorting, items that compare equal retain their order).

Comparison Functions

To obtain the required order, it is often necessary to provide a comparison function, for example when sorting into numerical order or sorting an array of objects using a specific field as a key. The parameter for .sort() is a reference to a function Fn(a, b) returning negative for a<b, zero for a=b and positive for a>b.

For numeric comparison, use function NumCmp below. It should work for any type which has a suitable default conversion to Number.

Function GenCmp may be the shortest comparison function working on all types that allow the "<" operator.

Demonstration

Function RandArry generates an array apparently of random integer numbers in the range from 0 to 20 inclusive, but necessarily including three particular values.

Some possible comparison functions :-

function compareNum(a, b) { return a - b } // for Numbers

function compareStrnum(a, b) {	// compare numeric part of string
  return a.replace(/[^.0-9]/g, "") - b.replace(/[^.0-9]/g, "") }

function compareStr1(a, b) {	// compare string
  return a>b ? 1 : a<b ? -1 : 0 }

function compareStr2(a, b) {	// compare string
  if (a<b) return -1
  if (a>b) return +1
  return 0 }

function compareStr3(a, b) {	// compare string
  return a<b - a>b }

Work matching function compareStrnum really calls for the use of keys
Functions compareStr1 compareStr2 are substantially equivalent
Function compareStr3 always performs both comparisons

Comparison Efficiency

If the comparison function is not simple, it will generally be representable as a transformation of each variable (preferably by a function) followed by a comparison of transforms. Frequently it will be better to precompute keys for the items, and sort by key comparison.

Note that a sort function will be called >O(N) times when sorting an N-element array. For large arrays, therefore, it is worth doing O(N) pre/post-processing to simplify the sort function or to render one unnecessary.

Demonstration

The first three items are preset.

• The first timed result is with the default sort. Note that it does not give a numerical sort.
• The second timed result is with a simple comparison function.
• The third timed result is with the default sort, including pre- and post- adjustment of the array.
• The fourth timed result has large overheads, but is elegant.
• The fifth is a little faster.

On my PII/300 Win 98 IE4 system, pre-processing to allow use of the default .sort method showed an improvement at about 25 items and above, in this case. For 5000 items, the gain exceeded a factor of 3. On my P4/3G WinXP IE6 system, 7 items and a factor of 6.

Sorting by Date/Time

Arrays of strings starting with date/time in an ISO 8601 format such as YYYY-MM-DD or hhmmss can be sorted directly, since alphabetical order is chronological order. Just use the .sort() / .sort().reverse() methods.

If an Array of Date Objects is processed with .sort() the dates will be put into alphabetical order of toString(). Instead, use .sort(NumCmp) where NumCmp is a comparison function as above, where the subtraction forces conversion to Number (which is trivial, as that's what a Date Object actually contains).

Build on NumCmp to sort an Array of something-including-dates.

Date Objects in the year range 2002-2285 can be converted to fixed-length strings by S = String(+D) and, after sorting, converted back by D = new Date(+S). Alternatively, use S as a key.

UK Postcode Sorting

How can valid UK postcodes be processed so that the result behaves well (though not geographically) in a string sort?

The formats considered are X# #XX, X## #XX, X#X #XX, XX# #XX, XX## #XX, XX#X #XX ; are any others in use? Later ... I have been told that XXX #XX and XXX XX# exist; ... TDCU 1ZZ is Tristan da Cunha (Risks 24.66).

Tested only with the above good code formats; code not optimised.

I have chosen to sort 1-letter regions before 2-letter ones.

A subset of the above should suffice for pattern validation.

Order

The actual order of items in an Object is not guaranteed. It is likely to be related to the order of creation. Probably, for (J in Obj) reflects the actual order of items in the Object.

The above applies to all Objects, including Arrays; Arrays are not ordered, but can be addressed in order.

Disorder

See JavaScript Random.