Sorting Strings

[Didier Lachieze]

Here is a first version doing this natural string sorting. It is based on the CAS sort function with a custom string comparison function as described in English here, and with more details in French here.

Note: this version is limited to integer numbers without any period or comma which are considered as strings. For example "12.6" will be sorted before "12.49".

Code:

// Alphanum: sort a list of strings_containing 
// a mix of letters and numbers. Given strings 
// of mixed characters and numbers, it sorts 
// the numbers in value order, while sorting 
// the non-numbers in ASCII order. 
// The end result is a natural sorting order.

Chunk();
Comp();

EXPORT Alphanum(List)
BEGIN
  LOCAL s:=SIZE(List);
  IF s==1 OR ΣLIST(MAKELIST(TYPE(List(I))≠2,I,1,s)) THEN 
    RETURN List; 
  ELSE
    RETURN CAS("sort(List,(x,y)→Comp(x,y))");
  END;
END;

// Compare two strings
// returns 0 if s1≥s2
// returns 1 if s1<s2

Comp(s1,s2)
BEGIN
  LOCAL l1,l2,s,j;
  l1:=Chunk(s1);
  l2:=Chunk(s2);
  s:=MIN(SIZE(l1),SIZE(l2));
  j:=1;
  WHILE IFTE(TYPE(l1(j))==TYPE(l2(j)),l1(j)==l2(j),0) AND j<s DO
    j:=j+1;
  END;
  IF TYPE(l1(j))==0 AND TYPE(l2(j))==2 THEN
    RETURN 1;
  END;
  IF TYPE(l1(j))==2 AND TYPE(l2(j))==0 THEN
    RETURN 0;
  END;
  IF l1(j)>l2(j) THEN
    RETURN 0;
  ELSE
    IF l1(j)==l2(j) AND j==s AND s<SIZE(l1) THEN
      RETURN 0;
    END;
    RETURN 1;
  END;
END;

// Breaks strings into chunks, where a chunk contains 
// either all alphabetic characters, or all numeric characters.

Chunk(s)
BEGIN
  LOCAL n:=DIM(s),j,t,m;
  t:=48≤s(1)≤57;
  IF n>1 THEN
    FOR j FROM 2 TO n DO
      IF (48≤s(j)≤57)≠t THEN 
        m:=IFTE(t,EXPR(LEFT(s,j-1)),LEFT(s,j-1));
        RETURN CONCAT(m,Chunk(RIGHT(s,n-j+1))); 
      END;
    END;
  END;
  RETURN IFTE(t,{EXPR(s)},{s});
END;

With the following test program it generates the expected sorted list:

Code:

EXPORT TEST()
BEGIN
LOCAL l1,l2,j;

l1:={"1000X Radonius Maximus","10X Radonius",
"200X Radonius","20X Radonius","20X Radonius Prime",
"30X Radonius","40X Radonius","Allegia 50 Clasteron",
"Allegia 500 Clasteron","Allegia 51 Clasteron",
"Allegia 51B Clasteron","Allegia 52 Clasteron",
"Allegia 60 Clasteron","Alpha 100","Alpha 2",
"Alpha 200","Alpha 2A","Alpha 2A-8000","Alpha 2A-900",
"Callisto Morphamax","Callisto Morphamax 500",
"Callisto Morphamax 5000","Callisto Morphamax 600",
"Callisto Morphamax 700","Callisto Morphamax 7000",
"Callisto Morphamax 7000 SE","Callisto Morphamax 7000 SE2",
"QRS-60 Intrinsia Machine","QRS-60F Intrinsia Machine",
"QRS-62 Intrinsia Machine","QRS-62F Intrinsia Machine",
"Xiph Xlater 10000","Xiph Xlater 2000","Xiph Xlater 300",
"Xiph Xlater 40","Xiph Xlater 5","Xiph Xlater 50",
"Xiph Xlater 500","Xiph Xlater 5000","Xiph Xlater 58",
"Allegia 6R Clasteron"};

l2:=Alphanum(l1);
PRINT();
FOR j FROM 1 TO  SIZE(l2) DO
  PRINT(l2(j));
END;
END;

Code:

10X Radonius
20X Radonius
20X Radonius Prime
30X Radonius
40X Radonius
200X Radonius
1000X Radonius Maximus
Allegia 6R Clasteron
Allegia 50 Clasteron
Allegia 51 Clasteron
Allegia 51B Clasteron
Allegia 52 Clasteron
Allegia 60 Clasteron
Allegia 500 Clasteron
Alpha 2
Alpha 2A
Alpha 2A-900
Alpha 2A-8000
Alpha 100
Alpha 200
Callisto Morphamax
Callisto Morphamax 500
Callisto Morphamax 600
Callisto Morphamax 700
Callisto Morphamax 5000
Callisto Morphamax 7000 SE
Callisto Morphamax 7000 SE2
Callisto Morphamax 7000
QRS-60 Intrinsia Machine
QRS-60F Intrinsia Machine
QRS-62 Intrinsia Machine
QRS-62F Intrinsia Machine
Xiph Xlater 5
Xiph Xlater 40
Xiph Xlater 50
Xiph Xlater 58
Xiph Xlater 300
Xiph Xlater 500
Xiph Xlater 2000
Xiph Xlater 5000
Xiph Xlater 10000