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