Natural sorting: Difference between revisions

{{Sorting Algorithm}}

 

order of individual characters codes to make the finding of

individual strings easier for a ''human'' reader.

:2. Make all whitespace characters equivalent.

:3. Sorting without regard to case.

:: foo9.txt before foo10.txt

:: As well as ... x9y99 before x9y100, before x10y0

:7. Sort ligatures as separate letters.

:8. Replacements:

 

;Task Description

* '''Implement the first four''' of the eight given features in a natural sorting routine/function/method...

* Print and display your output.

* '''For extra credit''' implement more than the first four.

 

 

;Sample input:

<pre>

 

 

 

 

 

 

 

 

 

 

 

 

AppleScript doesn't have a built-in sort facility, but its string comparisons are normalised and several attributes can be specifically either considered or ignored, making it fairly simple for a sort coded in the language to produce the results required here.

 

use framework "Foundation"

 

on naturalSort(listOfText)

script o

end script

set regex to current application's NSRegularExpressionSearch

end repeat

considering numeric strings, white space and hyphens but ignoring diacriticals, punctuation and case

tell sorter to sort(o's doctored, 1, -1, {slave:{listOfText}})

end considering

end naturalSort

 

 

 

 

 

 

 

 

 

=={{header|C}}==

 

Besides the numeric part, everything else was done in a uniform way by transforming input strings into some normalized format and comparing those instead. All sort options flags can be freely mixed together. C source is written in UTF-8 for easier reading here: don't do this for serious code.

#include <stdlib.h>

#include <wchar.h>

 

return 0;

0000098 nina

100 NINA

99 Ninja

100 NINA

 

=={{header|D}}==

Implements requests 1-5.

std.ascii, std.range;

 

}

}

{{out}}

<pre>Test strings:

=={{header|Elixir}}==

Implements requests 1-5.

def sorting(texts) do

Enum.sort_by(texts, fn text -> compare_value(text) end)

["The Wind in the Willows", "The 40th step more", "The 39 steps", "Wanda"]}

]

 

{{out}}

 

Objectives six to eight are attainable, except that the character encodements available are not portable. Code page 850 doesn't offer the same accented character codes as for other systems, such as code page 437. But the auxiliary sort key approach easily accommodates substitute characters (and could also swap + and -, for example!), and could recognise ligatures as well. One might be prodded into escalating to 16-bit or even 32-bit character codes to maintain the same ease of manipulation.

MODULE STASHTEXTS !Using COMMON is rather more tedious.

INTEGER MSG,KBD !I/O unit numbers.

END DO !On to the next.

END !A handy hint from Mr. Natural: "At home or at work, get the right tool for the job!"

Example output, in two columns:

Entry|Text Character Order Entry|Text 'Natural' Order

When (if) a scan reaches the end of its text, the TAIL will be considered for the extraction of further characters.

 

MODULE ASSISTANCE

INTEGER MSG,KBD !I/O unit numbers.

END DO !On to the next.

END !A handy hint from Mr. Natural: "At home or at work, get the right tool for the job!"

This time, because the texts are no longer being parsed into pieces, the book titles are not ordered together though they are in the required sequence disregarding the other entries. "The 39" and "The 40" have the "The " part converted into a TAIL, and so their first comparison characters are their digits, and in ASCII, digits precede letters. This is revealed in the third column, where the comparison characters are revealed, in an ad-hoc manner: what appears are the characters placed by every comparison so there may be contention.

Output:

 

First four rules, no extra credit:

 

import (

}

return false

{{out}}

<pre>

 

Implements requests 1-5.

import Data.List

import Data.Char

commonWords = ["the","a","an","of"]

 

 

{{out}}

The natural way of approaching this task in J is to normalize the text based on the rules desired for sorting. Here, we limit ourselves to ascii, for portability, and decide that our domain shall be terminated strings (where each string ends with the same character - typically a newline):

 

lines=: <;.2

norm=: [: split (32 9 12 13 14 15{a.) -.~ [: titleFix tolower

 

Example data:

 

ignore leading spaces: 2-2

ignore leading spaces: 2-1

The 39 steps

Wanda

 

Note that the required example which contains equivalent whitespace characters includes a '\n' in the data. So, for that example, we use a backslash as our terminator.

Example use:

 

ignore leading spaces: 2+0

ignore leading spaces: 2+1

The Wind in the Willows

 

 

=={{header|JavaScript}}==

Implements the first four rules. Rule 4 works for digits up to 20 characters.

 

var nsort = function(input) {

var e = function(s) {

]));

// -> ['\nfile9.txt', 'file10.txt', 'File11.TXT', 'file12.txt']

 

=={{header|jq}}==

matter therefore comes down to the filter named "splitup", which for

clarity, we define here as a top-level function, as follows:

def tidy: if .[0] == "" then .[1:] else . end | if .[length-1] == "" then .[0:length-1] else . end ;

 

| splitup # embedded integers

;

'''Testing'''

For brevity, we use the input as given above, but modified slightly so that it can be read

in as valid JSON. For example, the comments have been quoted. With these adjustments, the test driver can be written as a one-liner:

{{out}} (scrollable)

<div style="overflow:scroll; height:400px;">

 

# Ignoring leading spaces

"Wanda",

"The Wind in the Willows"

</div>

 

=={{header|Julia}}==

The functional programming principle used was to customize the "lt" comparison option of Julia's basic sort() to the "natural" sort features required.

natural1(x, y) = strip(x) < strip(y)

 

println("Testing sorting mod number $i. Sorted is: $(sort(testarrays[i], lt=ltfunction)).")

end

Testing sorting mod number 1. Sorted is: [" ignore leading spaces: 2+0", " ignore leading spaces: 2+1", " ignore leading spaces: 2-1", "ignore leading spaces: 2-2"].

Testing sorting mod number 2. Sorted is: ["ignore m.a.s spaces: 2+0", "ignore m.a.s spaces: 2+1", "ignore m.a.s spaces: 2-1", "ignore m.a.s spaces: 2-2"].

 

=={{header|Kotlin}}==

 

val r2 = Regex("""[ ]{2,}""")

s9.sortBy(::selector9)

println(s9.map { "'$it'" }.joinToString("\n"))

 

{{out}}

'Start with an ʒ: 2-2'

'Start with an ß: 2+0'

</pre>

 

 

The "structured" features of Pascal do not facilitate escape from loops, so, ... some <code>goto</code> atavisms appear in what follows...

Program Natural; Uses DOS, crt; {Simple selection.}

{Demonstrates a "natural" order of sorting text with nameish parts.}

 

END.

Output, with "!" instead of a backslash to prevent context confusions here:

Text order Natural order

This implements all 8 requirements^*:

 

use feature 'fc';

use Unicode::Normalize;

} @items;

}

 

: ^*) Note that decomposing the strings to the NFKD normalization form and subsequently stripping off all code points of the <code>Nonspacing_Mark</code> category, removes differences caused by accents / ligatures / alternate character forms / etc. in a standards-compliant way. This coincides with all the examples given in the task description, with the exception that it does ''not'' replace "ʒ" with "s" &mdash; one could add <pre style="display:inline;padding:0.3em">$str =~ tr/ʒ/s/;</pre> for that but it seems a bit [[wp:International_Phonetic_Alphabet_chart_for_English_dialects#Chart|whimsical]].)

'''Testing:'''

 

use utf8; # interpret this script's source code as UTF8

use Test::More; # for plan(), is_deeply()

print "\n";

}

 

{{out}}

As per C, common words anywhere in the string are omitted. All eight features. <br>

Needs chcp 65001 (or 28591) to get this to work on Windows, be sure to save as utf8.

 

 

{{Out}}

<pre>

=={{header|PicoLisp}}==

This parser takes care of features 1,2,3,4,5 and 8:

(clip

(make

"ß" "ss" "ſ" "s" "ʒ" "s" ) )

(unless (member Word '(the it to))

Test:

Sorting is trivial then:

Test:

"# Ignoring leading spaces"

("ignore leading spaces: 2-2" " ignore leading spaces: 2-1" " ignore leading spaces: 2+0" " ignore leading spaces: 2+1")

(pythonOut "Normally sorted :" (sort (copy X)))

(pythonOut "Naturally sorted:" (naturalSort X))

Output:

<pre># Ignoring leading spaces

 

=={{header|PowerShell}}==

# six sorting

$Discard = '^a ', '^an ', '^the '

)

}

{{Out}}

<pre>

=={{header|Python}}==

All eight features:

# Not Python 3.x (Can't compare str and int)

 

print 'Text strings:'; pp(txt)

print 'Normally sorted :'; print '\n'.join(sorted(txt))

 

===Sample Python output===

beginning/end, easy to implement, but sounds wrong).

 

#lang racket

(define (natural-sort l)

(shuffle '("foo9.txt" "foo10.txt" "x9y99" "x9y100" "x10y0" "x z" "x y")))

;; => '("foo9.txt" "foo10.txt" "x9y99" "x9y100" "x10y0" "x y" "x z")

 

=={{header|Raku}}==

different results depending on the order they are applied.

 

sub naturally ($a) { $a.lc.subst(/(\d+)/, ->$/ {0~$0.chars.chr~$0},:g) ~"\x0"~$a }

 

 

say "\n" ~ '*' x 40 ~ "\n";

 

Sample output:

=={{header|Ruby}}==

Requirements 1,2,3 and 5 are met in one line of code:

Almost all of the code below is handling requirement 4. The problem is that Ruby will happily sort ["a",1] against ["a",2] or even ["b"], but it does not know how to handle [1, "a"] against ["a", 2] and raises an ArgumentError. The code below does not define a new sort method, it defines a new class which is sortable by the existing method (falling back on string comparison).

include Comparable

attr_reader :scrubbed, :ints_and_strings, :i_s_pattern

 

end

Demo:

{"Ignoring leading spaces" =>

[ "ignore leading spaces: 2-2 ", " ignore leading spaces: 2-1 ", " ignore leading spaces: 2+0 ", " ignore leading spaces: 2+1 "],

puts [title,"--input--", ar, "--normal sort--", ar.sort, "--natural sort--", nat_sorts.sort, "\n"]

end

{{out}}

<pre>

=={{header|Scala}}==

All 8:

implicit object ArrayOrdering extends Ordering[Array[String]] { // 4

val INT = "([0-9]+)".r

okay

})

Output:

<pre>PASS: 1 IGNORING LEADING SPACES

Tasks 1-5 are completed.

 

(import (scheme base)

(scheme char)

("foo1bar99baz4.txt" "foo2bar99baz3.txt" "foo4bar99baz1.txt" "foo3bar99baz2.txt")

("The Wind in the Willows" "The 40th step more" "The 39 steps" "Wanda")))

 

{{out}}

=={{header|Sidef}}==

{{trans|Raku}}

# Sort groups of digits in number order. Sort by order of magnitude then lexically.

-> naturally { self.lc.gsub(/(\d+)/, {|s1| "0" + s1.len.chr + s1 }) + "\x0" + self };

self.gsub(re, {|s1| tr{s1} });

}

 

Tests:

[

"Task 1a\nSort while ignoring leading spaces.",

 

say "\n#{'*' * 40}\n";

 

{{out}}

 

Note also that Tcl supports case-insensitive sorting and “treat digit sequences as numbers” as native sorting options. (The latter is particularly useful for handling filenames.)

 

proc sortWithCollationKey {keyBuilder list} {

foo100bar10baz0.txt

foo1000bar99baz10.txt

Output:

<pre>

foo1000bar99baz9.txt

foo1000bar99baz10.txt

</pre>

 

 

First, a tag-mangled-fields sort, use tags to pull from the original list in sorted order function:

x.enumerate().sort(fcn([(_,a)],[(_,b)]){a<b})

.apply('wrap([(n,_)]){orig[n]});

Now, mangle a copy of the original list to "normalize" it to the task requirements and sort.

ts1:=T("ignore leading spaces: 2-2", " ignore leading spaces: 2-1",

" ignore leading spaces: 2+0", " ignore leading spaces: 2+1");

{{out}}

<pre>

</pre>

 

ts2:=T("ignore m.a.s spaces: 2-2", "ignore m.a.s spaces: 2-1",

"ignore m.a.s spaces: 2+0", "ignore m.a.s spaces: 2+1");

{{out}}

<pre>

</pre>

 

ts3:=T("Equiv. spaces: 3-3", "Equiv.\rspaces: 3-2", "Equiv.\x0cspaces: 3-1",

"Equiv.\x0bspaces: 3+0", "Equiv.\nspaces: 3+1", "Equiv.\tspaces: 3+2");

{{out}}

<pre>

</pre>

 

ts4:=T("cASE INDEPENENT: 3-2", "caSE INDEPENENT: 3-1",

"casE INDEPENENT: 3+0", "case INDEPENENT: 3+1");

{{out}}

<pre>

 

And the nasty one: multiple numeric fields. Each key is blown apart into a list of ints, where each int is consecutive numeric characters. To compare a pair of fields (ie two lists of ints), walk the two in parallel, stopping when a difference is found. Ugly but it works. Another tactic would be to normalize each field to the same length, concat the fields and use that as the mangled key. But that might have issues if the number of fields differ, the former doesn't care.

fcn fieldize(s){

s.apply(fcn(c){"1234567890".holds(c) and c or "."}).split(".")

list.apply(fieldize).enumerate().sort(fcmp)

.apply('wrap([(n,_)]){list[n]});

"foo1000bar99baz9.txt");

fsort(ts5).println();

 

x:=T("x9y99","foo10.txt","x10y0","foo9.txt","x9y100");

{{out}}

<pre>