JS Natural Sort Order


Published: 2015-10-13
Updated: 2016-10-14
Web: http://fritzthecat-blog.blogspot.com/2015/10/js-natural-sort-order.html


Here is a port of the natural-sort-order to JavaScript (as an example that JS implementations can also result in readable code :-)
It is directly derived from the Java code of my latest Blog article.

Test Area

The area below is for trying out the natural sort order. Enter names in the text-area, each in a single line, then press "Sort" to see the sorted result. I've already provided an example list.

Case Sensitive
Ignore Spaces

You find the JS code working here in the following.

JS Sorting

JavaScript provides a sort() function on arrays. This sorts alphabetically, no matter whether it is an array of numbers or an array of strings. But as optional argument you can pass a compare-function, this is a function that receives two parameters and is expected to return an integer being ...

Here is an example:

    var array = [ 4, 2, 6, 5, 3, 12, 9 ];
var comparator = function(a, b) {
return a - b;
};
array.sort(comparator);
// yields [ 2, 3, 4, 5, 6, 9, 12 ]

JS NaturalSortComparator

Using the JS sort() implementation I just need to provide the comparator function. For a discussion how natural sorting works please refer to my latest Java Blogs. Wherever it was possible I tried to keep identifiers and objects like they were in the Java code.

By passing one or two booleans to function newNaturalSortComparator()you could determine whether the comparator ignores upper/lower case or spaces.

  1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
"use strict";

/**
* Implements a natural sort order where numbers within names
* are detected and evaluated as numbers, not strings.
* Thus "a1", "a10", "a2" would be sorted as "a1", "a2", "a10".
*/
var newNaturalSortComparator = function(caseSensitive, ignoreSpaces)
{
// parameter default definition
ignoreSpaces = (ignoreSpaces === undefined) ? true : ignoreSpaces;


/** Inner class Part implements Comparator. */
var newPart = function(isNumber, content) {
var i = 0;
if (isNumber) // remove and count leading zeros when number
while (content.charAt(i) == '0')
i++;

content = (i == 0) ? content : content.substring(i);
content = caseSensitive ? content : content.toLowerCase();

var part = {
content: content,
leadingZeros: i,
number: isNumber ? parseInt(content) : undefined,

compareTo: function(other) {
var a, b;
if (part.number !== undefined && other.number !== undefined) {
a = part.number;
b = other.number;
}
else {
a = part.content;
b = other.content;
}
return (a < b) ? -1 : (a > b) ? +1 : 0;
}
};

return part;
};

var compare = function(string1, string2) {
var iterator1 = iterator(split(string1));
var iterator2 = iterator(split(string2));

while (iterator1.hasNext() || iterator2.hasNext()) {
// first has no more parts -> comes first
if ( ! iterator1.hasNext() && iterator2.hasNext())
return -1;

// second has no more parts -> comes first
if (iterator1.hasNext() && ! iterator2.hasNext())
return 1;

// compare next parts
var result = iterator1.next().compareTo(iterator2.next());
if (result !== 0) // found difference
return result;
}

return 0;
};


var cache = {};
var sb = ""; // string buffer

var split = function(string) {
var cachedList = cache[string];
if (cachedList) // cache results to be fast
return cachedList;

var list = [];
var digits = false;

for (var i = 0; i < string.length; i++) {
var c = string.charAt(i);
var ignore = (ignoreSpaces && (c === ' ' || c === '\t' || c === '\r' || c === '\n'));
var isDigit = ( ! ignore && c >= '0' && c <= '9' );

if (isDigit !== digits) { // state change
closeCurrentPart(list, digits);
digits = isDigit;
}

if ( ! ignore )
sb += c;
}
closeCurrentPart(list, digits);

cache[string] = list;
return list;
};

var closeCurrentPart = function(list, digits) {
if (sb.length > 0) { // close current string part
list.push(newPart(digits, sb));
sb = "";
}
}

var iterator = function(list) {
var index = 0;

return {
hasNext: function() {
return index < list.length;
},
next: function() {
var i = index;
index++;
return list[i];
}
};
};


return compare;
};

Use this like the following:

array.sort(newNaturalSortComparator());

Unit Test

Here is another usage example, actually representing a test.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
(function() {

var test = function(array, sortedArray, comparator) {
array.sort(comparator);

if (array.length !== sortedArray.length)
throw "Array has length "+array.length+", sorted array has length "+sortedArray.length;

for (var i = 0; i < array.length; i++)
if (array[i] !== sortedArray[i])
throw "Element at index "+i+", expected "+sortedArray[i]+" but was "+array[i];
};

(function() {
var array = [
"a15 b",
"a21",
"12b",
"11b",
"2b",
"1b",
"a11b",
"a2b",
"a 14 b",
"a22",
"3 4",
"a11",
"a1",
"3 3",
"a2",
"a 13b",
"a1b",
"a12b",
"a12",
"a21"
];
var sortedArray = [
"1b",
"2b",
"3 3",
"3 4",
"11b",
"12b",
"a1",
"a1b",
"a2",
"a2b",
"a11",
"a11b",
"a12",
"a12b",
"a 13b",
"a 14 b",
"a15 b",
"a21",
"a21",
"a22"
];
test(array, sortedArray, newNaturalSortComparator());
})();

})();





ɔ⃝ Fritz Ritzberger, 2015-10-13