Sort an array of composite structures

From Rosetta Code
Revision as of 18:16, 12 January 2012 by 79.37.202.200 (talk) (Updated D code)
Task
Sort an array of composite structures
You are encouraged to solve this task according to the task description, using any language you may know.

Sort an array of composite structures by a key. For example, if you define a composite structure that presents a name-value pair (in pseudocode): 

Define structure pair such that: 
   name as a string
   value as a string

and an array of such pairs: 

x: array of pairs

then define a sort routine that sorts the array x by the key name.

This task can always be accomplished with Sorting Using a Custom Comparator. If your language is not listed here, please see the other article.

Ada

Ada 2005 defines 2 standard subprograms for sorting arrays - 1 for constrained arrays and 1 for unconstrained arrays. Below is a example of using the unconstrained version. <lang ada>with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Text_IO; use Ada.Text_IO;

with Ada.Containers.Generic_Array_Sort;

procedure Demo_Array_Sort is 

  function "+" (S : String) return Unbounded_String renames To_Unbounded_String;

  type A_Composite is
     record
        Name  : Unbounded_String;
        Value : Unbounded_String;
     end record;

  function "<" (L, R : A_Composite) return Boolean is
  begin
     return L.Name < R.Name;
  end "<";

  procedure Put_Line (C : A_Composite) is
  begin
     Put_Line (To_String (C.Name) & " " & To_String (C.Value));
  end Put_Line;

  type An_Array is array (Natural range <>) of A_Composite;

  procedure Sort is new Ada.Containers.Generic_Array_Sort (Natural, A_Composite, An_Array);

  Data : An_Array := (1 => (Name => +"Joe",    Value => +"5531"),
                      2 => (Name => +"Adam",   Value => +"2341"),
                      3 => (Name => +"Bernie", Value => +"122"),
                      4 => (Name => +"Walter", Value => +"1234"),
                      5 => (Name => +"David",  Value => +"19"));

begin 

  Sort (Data);
  for I in Data'Range loop
     Put_Line (Data (I));
  end loop;

end Demo_Array_Sort;</lang> Result: 

  C:\Ada\sort_composites\lib\demo_array_sort
  Adam 2341
  Bernie 122
  David 19
  Joe 5531
  Walter 1234

Ada 2005 also provides ordered containers, so no explicit call is required. Here is an example of an ordered set: <lang ada>with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Text_IO; use Ada.Text_IO;

with Ada.Containers.Ordered_Sets;

procedure Sort_Composites is 

  function "+" (S : String) return Unbounded_String renames To_Unbounded_String;

  type A_Composite is
     record
        Name  : Unbounded_String;
        Value : Unbounded_String;
     end record;

  function "<" (L, R : A_Composite) return Boolean is
  begin
     return L.Name < R.Name;
  end "<";

  procedure Put_Line (C : A_Composite) is
  begin
     Put_Line (To_String (C.Name) & " " & To_String (C.Value));
  end Put_Line;

  package Composite_Sets is new Ada.Containers.Ordered_Sets (A_Composite);

  procedure Put_Line (C : Composite_Sets.Cursor) is
  begin
     Put_Line (Composite_Sets.Element (C));
  end Put_Line;

  Data : Composite_Sets.Set;

begin 

  Data.Insert (New_Item => (Name => +"Joe",    Value => +"5531"));
  Data.Insert (New_Item => (Name => +"Adam",   Value => +"2341"));
  Data.Insert (New_Item => (Name => +"Bernie", Value => +"122"));
  Data.Insert (New_Item => (Name => +"Walter", Value => +"1234"));
  Data.Insert (New_Item => (Name => +"David",  Value => +"19"));
  Data.Iterate (Put_Line'Access);

end Sort_Composites;</lang> Result: 

  C:\Ada\sort_composites\lib\sort_composites
  Adam 2341
  Bernie 122
  David 19
  Joe 5531
  Walter 1234

There is no standard sort function for Ada 95. The example below implements a simple bubble sort. <lang ada>with Ada.Text_Io; with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

procedure Sort_Composite is 

  type Composite_Record is record
     Name : Unbounded_String;
     Value : Unbounded_String;
  end record;
  
  type Pairs_Array is array(Positive range <>) of Composite_Record;
  
  procedure Swap(Left, Right : in out Composite_Record) is
     Temp : Composite_Record := Left;
  begin
     Left := Right;
     Right := Temp;
  end Swap; 
  
  -- Sort_Names uses a bubble sort
  
  procedure Sort_Name(Pairs : in out Pairs_Array) is
     Swap_Performed : Boolean := True;
  begin
     while Swap_Performed loop
        Swap_Performed := False;
        for I in Pairs'First..(Pairs'Last - 1) loop
           if Pairs(I).Name > Pairs(I + 1).Name then
              Swap (Pairs(I), Pairs(I + 1));
              Swap_Performed := True;
           end if;
        end loop;
     end loop;
  end Sort_Name;
  
  procedure Print(Item : Pairs_Array) is
  begin
     for I in Item'range loop
        Ada.Text_Io.Put_Line(To_String(Item(I).Name) & ", " & 
           to_String(Item(I).Value));
     end loop;
  end Print;
  type Names is (Fred, Barney, Wilma, Betty, Pebbles);
  type Values is (Home, Work, Cook, Eat, Bowl);
  My_Pairs : Pairs_Array(1..5);

begin 

  for I in My_Pairs'range loop
     My_Pairs(I).Name := To_Unbounded_String(Names'Image(Names'Val(Integer(I - 1))));
     My_Pairs(I).Value := To_Unbounded_String(Values'Image(Values'Val(Integer(I - 1))));
  end loop;
  Print(My_Pairs);
  Ada.Text_Io.Put_Line("=========================");
  Sort_Name(My_Pairs);
  Print(My_Pairs);

end Sort_Composite;</lang>

ALGOL 68

Translation of: python
Works with: ALGOL 68 version Standard - with prelude inserted manually
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386

<lang algol68>MODE SORTSTRUCT = PERSON; OP < = (PERSON a,b)BOOL: age OF a < age OF b; PR READ "prelude/sort.a68" PR;

MODE PERSON = STRUCT (STRING name, INT age); FORMAT person repr = $"Name: "g", Age: "g(0)l$;

[]SORTSTRUCT person = (("joe", 120), ("foo", 31), ("bar", 51)); printf((person repr, shell sort(person), $l$))</lang> Output: 

Name: foo, Age: 31
Name: bar, Age: 51
Name: joe, Age: 120

AutoHotkey

built ListView Gui, contains a table sorting function which can be used for this. <lang AutoHotkey>start: Gui, Add, ListView, r20 w200, 1|2 data = ( foo,53 joe,34 bar,23 )

Loop, parse, data, `n { 

 stringsplit, row, A_LoopField, `,
 LV_Add(row, row1, row2)

} LV_ModifyCol()  ; Auto-size columns Gui, Show msgbox, sorting by column1 LV_ModifyCol(1, "sort") ; sort by first column msgbox, sorting by column2 LV_ModifyCol(2, "sort Integer") ; sort by second column numerically return

GuiClose: ExitApp</lang>

C

Using qsort, from the standard library. <lang c>

  1. include <stdio.h>
  2. include <stdlib.h>
  3. include <ctype.h>

typedef struct twoStringsStruct { 

   char * key, *value;

} sTwoStrings;

int ord( char v ) { 

   static char *dgts = "012345679";
   char *cp;
   for (cp=dgts; v != *cp; cp++);
   return (cp-dgts);

}

int cmprStrgs(const sTwoStrings *s1,const sTwoStrings *s2) { 

   char *p1 = s1->key; 
   char *p2 = s2->key;
   char *mrk1, *mrk2;
   while ((tolower(*p1) == tolower(*p2)) && *p1) { p1++; p2++;}
   if (isdigit(*p1) && isdigit(*p2)) {
       long v1, v2;
       if ((*p1 == '0') ||(*p2 == '0')) {
           while (p1 > s1->key) {
               p1--; p2--;
               if (*p1 != '0') break;
           }
           if (!isdigit(*p1)) {
               p1++; p2++;
           }
       }
       mrk1 = p1; mrk2 = p2;
       v1 = 0;
       while(isdigit(*p1)) {
           v1 = 10*v1+ord(*p1);
           p1++;
       }
       v2 = 0;
       while(isdigit(*p2)) {
           v2 = 10*v2+ord(*p2);
           p2++;
       }
       if (v1 == v2) 
          return(p2-mrk2)-(p1-mrk1);
       return v1 - v2;
   }
   if (tolower(*p1) != tolower(*p2))
      return (tolower(*p1) - tolower(*p2));
   for(p1=s1->key, p2=s2->key; (*p1 == *p2) && *p1; p1++, p2++);
   return (*p1 -*p2);

}

int maxstrlen( char *a, char *b) { int la = strlen(a); int lb = strlen(b); return (la>lb)? la : lb; }

int main() { 

   sTwoStrings toBsorted[] = {
       { "Beta11a", "many" },
       { "alpha1", "This" },
       { "Betamax", "sorted." },
       { "beta3", "order" },
       { "beta11a", "strings" },
       { "beta001", "is" },
       { "beta11", "which" },
       { "beta041", "be" },
       { "beta05", "in" },
       { "beta1", "the" },
       { "beta40", "should" },
   };
  1. define ASIZE (sizeof(toBsorted)/sizeof(sTwoStrings))
   int k, maxlens[ASIZE];
   char format[12];
   sTwoStrings *cp;

   qsort( (void*)toBsorted, ASIZE, sizeof(sTwoStrings),cmprStrgs); 

   for (k=0,cp=toBsorted; k < ASIZE; k++,cp++) {
       maxlens[k] = maxstrlen(cp->key, cp->value);   
       sprintf(format," %%-%ds", maxlens[k]);
       printf(format, toBsorted[k].value);

} 

   printf("\n");
   for (k=0; k < ASIZE; k++) {
       sprintf(format," %%-%ds", maxlens[k]);
       printf(format, toBsorted[k].key);

} 

   printf("\n");

 return 0;

}</lang> Output: 

   This      is   the order     in  which    many strings should      be sorted.
 alpha1 beta001 beta1 beta3 beta05 beta11 Beta11a beta11a beta40 beta041 Betamax

C++

Works with: g++ version 4.1.2

<lang cpp>#include <iterator>

  1. include <algorithm>
  2. include <iostream>

template<typename Struct, typename MemberType> class less_member { public: 

 less_member(MemberType Struct::*m):
   member(m)
 {
 }
 bool operator()(Struct const& s1, Struct const& s2) const
 {
   return s1.*member < s2.*member;
 }

private: 

 MemberType Struct::*const member;

};

template<typename Struct, typename MemberType> 

less_member<Struct, MemberType> make_less_member(MemberType Struct::* m)

{ 

 return m;

}

template<typename FwdIter, typename MemberPtrType> 

void sort_for_member(FwdIter first, FwdIter last, MemberPtrType m)

{ 

 std::sort(first, last, make_less_member(m));

}

struct entry { 

 std::string name;
 std::string value;

};

int main() { 

 entry array[] = { { "grass",  "green" },
                   { "snow",   "white" },
                   { "sky",    "blue"  },
                   { "cherry", "red"   } };
 std::cout << "before sorting:\n\n";
 for (int i = 0; i < 4; ++i)
   std::cout << "index: " << i << ", name: " << array[i].name
             << ", value: " << array[i].value << "\n";

 sort_for_member(array, array+4, &entry::name);

 std::cout << "\nafter sorting:\n\n";
 for (int i = 0; i < 4; ++i)
   std::cout << "index: " << i << ", name: " << array[i].name
             << ", value: " << array[i].value << "\n";
 return 0;

}</lang>

C#

Works with: C# version 3+

<lang csharp>using System; using System.Collections.Generic; using System.Linq;

class Program { 

   struct Entry
   {
       public Entry(string name, double value) { Name = name; Value = value; }
       public string Name;
       public double Value;
   }

   static void Main(string[] args)
   {
       var Elements = new List<Entry>
       {
           new Entry("Krypton", 83.798), new Entry("Beryllium", 9.012182), new Entry("Silicon", 28.0855),
           new Entry("Cobalt", 58.933195), new Entry("Selenium", 78.96), new Entry("Germanium", 72.64)
       };

       var sortedElements = Elements.OrderBy(e => e.Name);

       foreach (Entry e in sortedElements)
           Console.WriteLine("{0,-11}{1}", e.Name, e.Value);
   }

}</lang>

Output: 

Beryllium  9.012182
Cobalt     58.933195
Germanium  72.64
Krypton    83.798
Selenium   78.96
Silicon    28.0855

Clojure

Clojure has a sort-by function which takes a keyfn and a coll. It returns a sorted sequence of the items in coll, where the sort order is determined by comparing (keyfn item).

<lang clojure>

Gathered with Google Squared

(def *langs* [["Clojure" 2007] ["Common Lisp" 1984] ["Java" 1995] ["Haskell" 1990] 

             ["Lisp" 1958] ["Scheme" 1975]])

user> (sort-by second *langs*) ; using a keyfn

(["Lisp" 1958] ["Scheme" 1975] ["Common Lisp" 1984] ["Haskell" 1990] ["Java" 1995] ["Clojure" 2007]) </lang>

You can also supply a comparator (using compare or a sibling of <). A comparator can be used with the regular sort function or the sort-by function. In the latter case, the comparator will be used on (keyfn item) instead of item.

<lang clojure> user> (sort #(compare (second %1) (second %2)) *langs*) ; using a comparator

(["Lisp" 1958] ["Scheme" 1975] ["Common Lisp" 1984] ["Haskell" 1990] ["Java" 1995] ["Clojure" 2007])

user> (sort-by second > *langs*) ; using a keyfn and a comparator

(["Clojure" 2007] ["Java" 1995] ["Haskell" 1990] ["Common Lisp" 1984] ["Scheme" 1975] ["Lisp" 1958]) </lang>

Read the docstring of sort and sort-by for more info.

Common Lisp

In Common Lisp, the sort function takes a predicate that is used as the comparator. This parameter can be any two-argument function. Additionally, the sort function can take a keyword argument :key whose result is passed to the predicate.

Let's define a composite structure of U.S. states and average test scores.

<lang lisp>CL-USER> (defparameter *test-scores* '(("texas" 68.9) ("ohio" 87.8) ("california" 76.2) ("new york" 88.2)) )

  • TEST-SCORES*</lang>

We can sort by the state name by supplying a one-argument key function that is called by the sort function to determine the value to compare. In this case, the function is first will retrieve the state name:

<lang lisp>CL-USER> (sort (copy-list *test-scores*) #'string-lessp :key #'first) (("california" 76.2) ("new york" 88.2) ("ohio" 87.8) ("texas" 68.9))</lang>

we can also sort by the test scores by supplying a different key function that return the test score instead:

<lang lisp>CL-USER> (sort (copy-list *test-scores*) #'< :key #'second) (("texas" 68.9) ("california" 76.2) ("ohio" 87.8) ("new york" 88.2))</lang>

D

<lang d>import std.stdio, std.algorithm;

void main() { 

   static struct Pair { string name, value; }

   Pair[] pairs = [{"Joe",    "5531"},
                   {"Adam",   "2341"},
                   {"Bernie",  "122"},
                   {"Walter", "1234"},
                   {"David",    "19"}];

   schwartzSort!(p => p.name)(pairs);
   writeln(pairs);

}</lang> Output: 

[Pair("Adam", "2341"), Pair("Bernie", "122"), Pair("David", "19"), Pair("Joe", "5531"), Pair("Walter", "1234")]

Delphi

<lang Delphi>program SortCompositeStructures;

{$APPTYPE CONSOLE}

uses SysUtils, Generics.Collections, Generics.Defaults;

type 

 TStructurePair = record
   name: string;
   value: string;
   constructor Create(const aName, aValue: string);
 end;

constructor TStructurePair.Create(const aName, aValue: string); begin 

 name := aName;
 value := aValue;

end;

var 

 lArray: array of TStructurePair;

begin 

 SetLength(lArray, 3);
 lArray[0] := TStructurePair.Create('dog', 'rex');
 lArray[1] := TStructurePair.Create('cat', 'simba');
 lArray[2] := TStructurePair.Create('horse', 'trigger');

 TArray.Sort<TStructurePair>(lArray , TDelegatedComparer<TStructurePair>.Construct(
 function(const Left, Right: TStructurePair): Integer
 begin
   Result := CompareText(Left.Name, Right.Name);
 end));

end.</lang>

E

<lang e>def compareBy(keyfn) { # This ought to be in the standard library 

 return def comparer(a, b) {
   return keyfn(a).op__cmp(keyfn(b))
 }

}

def x := [ 

 ["Joe",3],
 ["Bill",4],
 ["Alice",20],
 ["Harry",3],

]

println(x.sort(compareBy(fn [name,_] { name })))</lang>

Erlang

Any Erlang type can be compared to any Erlang type. As such, nothing special needs to be done: <lang Erlang>1> lists:sort([{{2006,2007},"Ducks"}, 

              {{2000,2001},"Avalanche"},
              {{2002,2003},"Devils"},
              {{2001,2002},"Red Wings"},
              {{2003,2004},"Lightning"},
              {{2004,2005},"N/A: lockout"},
              {{2005,2006},"Hurricanes"},
              {{1999,2000},"Devils"},
              {{2007,2008},"Red Wings"},
              {{2008,2009},"Penguins"}]).

[{{1999,2000},"Devils"}, 

{{2000,2001},"Avalanche"},
{{2001,2002},"Red Wings"},
{{2002,2003},"Devils"},
{{2003,2004},"Lightning"},
{{2004,2005},"N/A: lockout"},
{{2005,2006},"Hurricanes"},
{{2006,2007},"Ducks"},
{{2007,2008},"Red Wings"},
{{2008,2009},"Penguins"}]</lang>

It is also possible to sort with custom functions, in this case by the team's name: <lang Erlang>2> F = fun({_,X},{_,Y}) -> X < Y end.

  1. Fun<erl_eval.12.113037538>

3> lists:usort(F, [{{2006,2007},"Ducks"}, 

                  {{2000,2001},"Avalanche"},
                  {{2002,2003},"Devils"},
                  {{2001,2002},"Red Wings"},
                  {{2003,2004},"Lightning"},
                  {{2004,2005},"N/A: lockout"},
                  {{2005,2006},"Hurricanes"},
                  {{1999,2000},"Devils"},
                  {{2007,2008},"Red Wings"},
                  {{2008,2009},"Penguins"}]).

[{{2000,2001},"Avalanche"}, 

{{1999,2000},"Devils"},
{{2002,2003},"Devils"},
{{2006,2007},"Ducks"},
{{2005,2006},"Hurricanes"},
{{2003,2004},"Lightning"},
{{2004,2005},"N/A: lockout"},
{{2008,2009},"Penguins"},
{{2007,2008},"Red Wings"},
{{2001,2002},"Red Wings"}]</lang>

Euphoria

<lang euphoria>include sort.e include misc.e

constant NAME = 1 function compare_names(sequence a, sequence b) 

   return compare(a[NAME],b[NAME])

end function

sequence s s = { { "grass", "green" }, 

     { "snow",   "white" },
     { "sky",    "blue"  },
     { "cherry", "red"   } }

pretty_print(1,custom_sort(routine_id("compare_names"),s),{2})</lang>

Output: 

{
  {
    "cherry",
    "red"
  },
  {
    "grass",
    "green"
  },
  {
    "sky",
    "blue"
  },
  {
    "snow",
    "white"
  }
}

Factor

This is essentially the same as Sorting Using a Custom Comparator.

<lang factor>TUPLE: example-pair name value ;

sort-by-name ( seq -- seq' ) [ [ name>> ] compare ] sort ;</lang>
( scratchpad ) { T{ example-pair f "omega" "a" } T{ example-pair f "gamma" "q" } T{ example-pair f "alpha" "z" } } sort-by-name .
{
    T{ example-pair { name "alpha" } { value "z" } }
    T{ example-pair { name "gamma" } { value "q" } }
    T{ example-pair { name "omega" } { value "a" } }
}

Fantom

Any object can be sorted as needed by passing an appropriate block to the 'sort' method.

<lang fantom> class Pair // create a composite structure { 

 Str name
 Str value
 new make (Str name, Str value)
 {
   this.name = name
   this.value = value
 }

 override Str toStr () 
 {
   "(Pair: $name, $value)"
 }

}

class Main { 

 public static Void main ()
 {
   // samples
   pairs := [Pair("Fantom", "OO"), Pair("Clojure", "Functional"), Pair("Java", "OO") ]

   sorted := pairs.dup // make a copy of original list 
   sorted.sort |Pair a, Pair b -> Int|  // sort using custom comparator
   {
     a.name <=> b.name
   }
   echo ("Started with : " + pairs.join(" "))
   echo ("Finished with: " + sorted.join(" "))
 }

} </lang>

Fortran

Works with: Fortran version 90 and later

Standard Fortran has no built-in sort function although some compilers add them. The following example uses an insertion sort. <lang fortran>PROGRAM EXAMPLE 

 IMPLICIT NONE  

 TYPE Pair
   CHARACTER(6) :: name
   CHARACTER(1) :: value
 END TYPE Pair

 TYPE(Pair) :: rcc(10), temp
 INTEGER :: i, j

 rcc(1) = Pair("Black", "0")
 rcc(2) = Pair("Brown", "1")
 rcc(3) = Pair("Red", "2")
 rcc(4) = Pair("Orange", "3")
 rcc(5) = Pair("Yellow", "4") 
 rcc(6) = Pair("Green", "5")
 rcc(7) = Pair("Blue", "6")
 rcc(8) = Pair("Violet", "7")
 rcc(9) = Pair("Grey", "8")
 rcc(10) = Pair("White", "9")

 DO i = 2, SIZE(rcc)
    j = i - 1
    temp = rcc(i)
       DO WHILE (j>=1 .AND. LGT(rcc(j)%name, temp%name))
          rcc(j+1) = rcc(j)
          j = j - 1
       END DO
    rcc(j+1) = temp
 END DO

 WRITE (*,"(2A6)") rcc

END PROGRAM EXAMPLE</lang> Output 

Black      0
Blue       6
Brown      1
Green      5
Grey       8
Orange     3
Red        2
Violet     7
White      9
Yellow     4

F#

F# has sortBy functions that work on collection types for this purpose. An example using an array of pairs: <lang fsharp>let persons = [| ("Joe", 120); ("foo", 31); ("bar", 51) |] Array.sortInPlaceBy fst persons printfn "%A" persons</lang>

Output: 

[|("Joe", 120); ("bar", 51); ("foo", 31)|]

An example using a list of records: <lang fsharp>type Person = { name:string; id:int } let persons2 = [{name="Joe"; id=120}; {name="foo"; id=31}; {name="bar"; id=51}] let sorted = List.sortBy (fun p -> p.id) persons2 for p in sorted do printfn "%A" p</lang>

Output: 

{name = "foo";
 id = 31;}
{name = "bar";
 id = 51;}
{name = "Joe";
 id = 120;}

Go

<lang go>package main

import ( 

   "fmt"
   "sort"

)

type pair struct { 

   name, value string

} type csArray []pair

// three methods satisfy sort.Interface func (a csArray) Less(i, j int) bool { return a[i].name < a[j].name } func (a csArray) Len() int { return len(a) } func (a csArray) Swap(i, j int) { a[i], a[j] = a[j], a[i] }

var x = csArray{ 

   pair{"joe", "120"},
   pair{"foo", "31"},
   pair{"bar", "251"},

}

func main() { 

   sort.Sort(x)
   for _, p := range x {
       fmt.Printf("%5s: %s\n", p.name, p.value)
   }

}</lang>

Groovy

<lang groovy>class Holiday { 

   def date
   def name
   Holiday(dateStr, name) { this.name = name; this.date = format.parse(dateStr) }
   String toString() { "${format.format date}: ${name}" }
   static format = new java.text.SimpleDateFormat("yyyy-MM-dd")

}

def holidays = [ new Holiday("2009-12-25", "Christmas Day"), 

                new Holiday("2009-04-22", "Earth Day"),
                new Holiday("2009-09-07", "Labor Day"),
                new Holiday("2009-07-04", "Independence Day"),
                new Holiday("2009-10-31", "Halloween"),
                new Holiday("2009-05-25", "Memorial Day"),
                new Holiday("2009-03-14", "PI Day"),
                new Holiday("2009-01-01", "New Year's Day"),
                new Holiday("2009-12-31", "New Year's Eve"),
                new Holiday("2009-11-26", "Thanksgiving"),
                new Holiday("2009-02-14", "St. Valentine's Day"),
                new Holiday("2009-03-17", "St. Patrick's Day"),
                new Holiday("2009-01-19", "Martin Luther King Day"),
                new Holiday("2009-02-16", "President's Day") ]

holidays.sort { x, y -> x.date <=> y.date } holidays.each { println it }</lang>

Output: 

2009-01-01: New Year's Day
2009-01-19: Martin Luther King Day
2009-02-14: St. Valentine's Day
2009-02-16: President's Day
2009-03-14: PI Day
2009-03-17: St. Patrick's Day
2009-04-22: Earth Day
2009-05-25: Memorial Day
2009-07-04: Independence Day
2009-09-07: Labor Day
2009-10-31: Halloween
2009-11-26: Thanksgiving
2009-12-25: Christmas Day
2009-12-31: New Year's Eve

Haskell

<lang haskell>import List

data Person = P String Int deriving Eq instance Show Person where 

   show (P name val) = "Person "++name++" with value "++(show val)

instance Ord Person where 

   compare (P n1 _) (P n2 _) = compare n1 n2

people = [(P "Joe" 12), (P "Bob" 8), (P "Alice" 9), (P "Harry" 2)] sortedPeople = sort people sortedPeopleByVal = sortBy (\(P _ v1) (P _ v2)->compare v1 v2) people</lang>

Icon and Unicon

The built-in procedure sortf will sort a list by the field in a records. <lang Icon>record star(name,HIP)

procedure main()

Ori := [ star("Betelgeuse",27989), 

        star("Rigel",24436),
        star("Belatrix", 25336),
        star("Alnilam",26311) ]

write("Some Orion stars by HIP#") every write( (x := !sortf(Ori,2)).name, " HIP ",x.HIP) end</lang>

Sample output:

Some Orion stars by HIP#
Rigel HIP 24436
Belatrix HIP 25336
Alnilam HIP 26311
Betelgeuse HIP 27989

J

The function /: sorts anything (its left argument) based on they keys supplied in its right argument. For example:

<lang j> names =: ;: 'Perlis Wilkes Hamming Minsky Wilkinson McCarthy' 

  values=: ;: 'Alan Maurice Richard Marvin James John'
  pairs =: values ,. names
  pairs /: names

+-------+---------+ |Richard|Hamming | +-------+---------+ |John |McCarthy | +-------+---------+ |Marvin |Minsky | +-------+---------+ |Alan |Perlis | +-------+---------+ |Maurice|Wilkes | +-------+---------+ |James |Wilkinson| +-------+---------+</lang>

Alternatively, J's cross operator will use the same values for both the left and right arguments for /: but, in this case, /:~ is not desirable because that would have us sorting on the values (the first column) and only using the second column for equal names (none of which appear, here).

Java

<lang java>import java.util.Arrays; import java.util.Comparator;

public class SortComp { 

   public static class Pair {
       public String name;
       public String value;
       public Pair(String n, String v) {
           name = n;
           value = v;
       }
   }

   public static void main(String[] args) {
       Pair[] pairs = {new Pair("06-07", "Ducks"), new Pair("00-01", "Avalanche"),
           new Pair("02-03", "Devils"), new Pair("01-02", "Red Wings"),
           new Pair("03-04", "Lightning"), new Pair("04-05", "lockout"),
           new Pair("05-06", "Hurricanes"), new Pair("99-00", "Devils"),
           new Pair("07-08", "Red Wings"), new Pair("08-09", "Penguins")};

       sortByName(pairs);
       for (Pair p : pairs) {
           System.out.println(p.name + " " + p.value);
       }
   }

   public static void sortByName(Pair[] pairs) {
       Arrays.sort(pairs, new Comparator<Pair>() {
           public int compare(Pair p1, Pair p2) {
               return p1.name.compareTo(p2.name);
           }
       });
   }

}</lang> Output: 

00-01 Avalanche
01-02 Red Wings
02-03 Devils
03-04 Lightning
04-05 lockout
05-06 Hurricanes
06-07 Ducks
07-08 Red Wings
08-09 Penguins
99-00 Devils

JavaScript

<lang javascript>var arr = [ 

 {id: 3, value: "foo"},
 {id: 2, value: "bar"},
 {id: 4, value: "baz"},
 {id: 1, value: 42},
 {id: 5, something: "another string"} // Works with any object declaring 'id' as a number.

]; arr = arr.sort(function(a, b) {return a.id - b.id}); // Sort with comparator checking the id. </lang>

Liberty BASIC

NB LB sorts in a non standard order. See http://libertybasicbugs.wikispaces.com/Comparison+of+characters+and+strings+is+not+ASCII+based
The method used here to simulate a compound structure can only hold pairs of terms, since LB arrays ar 1D or 2D. More complicated associated arrays could be stored in delimiter-separated string arrays. <lang lb> N =20 dim IntArray$( N, 2)

print "Original order" for i =1 to N 

   name$ =mid$( "SortArrayOfCompositeStructures", int( 25 *rnd( 1)), 1 +int( 4 *rnd( 1)))
   IntArray$( i, 1) =name$
   print name$,
   t$ =str$( int( 1000 *rnd( 1)))
   IntArray$( i, 2) =t$
   print t$

next i

sort IntArray$(), 1, N, 1 print "Sorted by name" ' ( we specified column 1) for i =1 to N 

   print IntArray$( i, 1), IntArray$( i, 2)

next i </lang>

Lua

<lang lua>function sorting( a, b ) 

   return a[1] < b[1]

end

tab = { {"C++", 1979}, {"Ada", 1983}, {"Ruby", 1995}, {"Eiffel", 1985} }

table.sort( tab, sorting ) for _, v in ipairs( tab ) do 

   print( unpack(v) )

end</lang>

Mathematica

<lang Mathematica>events = {{"2009-12-25", "Christmas Day"}, {"2009-04-22", 

   "Earth Day"}, {"2009-09-07", "Labor Day"}, {"2009-07-04", 
   "Independence Day"}, {"2009-10-31", "Halloween"}, {"2009-05-25", 
   "Memorial Day"}, {"2009-03-14", "PI Day"}, {"2009-01-01", 
   "New Year's Day"}, {"2009-12-31", 
   "New Year's Eve"}, {"2009-11-26", "Thanksgiving"}, {"2009-02-14", 
   "St. Valentine's Day"}, {"2009-03-17", 
   "St. Patrick's Day"}, {"2009-01-19", 
   "Martin Luther King Day"}, {"2009-02-16", "President's Day"}};

date = 1; name = 2; SortBy[events, #name &] // Grid SortBy[events, #date &] // Grid</lang> gives back: <lang Mathematica>2009-12-25 Christmas Day 2009-04-22 Earth Day 2009-10-31 Halloween 2009-07-04 Independence Day 2009-09-07 Labor Day 2009-01-19 Martin Luther King Day 2009-05-25 Memorial Day 2009-01-01 New Year's Day 2009-12-31 New Year's Eve 2009-03-14 PI Day 2009-02-16 President's Day 2009-03-17 St. Patrick's Day 2009-02-14 St. Valentine's Day 2009-11-26 Thanksgiving


2009-01-01 New Year's Day 2009-01-19 Martin Luther King Day 2009-02-14 St. Valentine's Day 2009-02-16 President's Day 2009-03-14 PI Day 2009-03-17 St. Patrick's Day 2009-04-22 Earth Day 2009-05-25 Memorial Day 2009-07-04 Independence Day 2009-09-07 Labor Day 2009-10-31 Halloween 2009-11-26 Thanksgiving 2009-12-25 Christmas Day 2009-12-31 New Year's Eve</lang>

MAXScript

<lang maxscript>fn keyCmp comp1 comp2 = ( 

   case of
   (
       (comp1[1] > comp2[1]):	1
       (comp1[1] < comp2[1]):	-1
       default:		0
   )

)

people = #(#("joe", 39), #("dave", 37), #("bob", 42)) qsort people keyCmp print people</lang>

Objective-C

<lang objc>@interface Pair : NSObject { 

   NSString *name;
   NSString *value;

} +(id)pairWithName:(NSString *)n value:(NSString *)v; -(id)initWithName:(NSString *)n value:(NSString *)v; -(NSString *)name; -(NSString *)value; @end

@implementation Pair +(id)pairWithName:(NSString *)n value:(NSString *)v { 

   return [[[self alloc] initWithName:n value:v] autorelease];

} -(id)initWithName:(NSString *)n value:(NSString *)v { 

   if ((self = [super init])) {
       name = [n retain];
       value = [v retain];
   }
   return self;

} -(void)dealloc { 

   [name release];
   [value release];
   [super dealloc];

} -(NSString *)name { return name; } -(NSString *)value { return value; } -(NSString *)description { 

   return [NSString stringWithFormat:@"< %@ -> %@ >", name, value];

} @end

int main() { 

   NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

   NSArray *pairs = [NSArray arrayWithObjects:
                      [Pair pairWithName:@"06-07" value:@"Ducks"],
                      [Pair pairWithName:@"00-01" value:@"Avalanche"],
                      [Pair pairWithName:@"02-03" value:@"Devils"],
                      [Pair pairWithName:@"01-02" value:@"Red Wings"],
                      [Pair pairWithName:@"03-04" value:@"Lightning"],
                      [Pair pairWithName:@"04-05" value:@"lockout"],
                      [Pair pairWithName:@"05-06" value:@"Hurricanes"],
                      [Pair pairWithName:@"99-00" value:@"Devils"],
                      [Pair pairWithName:@"07-08" value:@"Red Wings"],
                      [Pair pairWithName:@"08-09" value:@"Penguins"],
                      nil];

   // optional 3rd arg: you can also specify a selector to compare the keys
   NSSortDescriptor *sd = [[NSSortDescriptor alloc] initWithKey:@"name" ascending:YES];

   // it takes an array of sort descriptors, and it will be ordered by the
   // first one, then if it's a tie by the second one, etc.
   NSArray *sorted = [pairs sortedArrayUsingDescriptors:
                        [NSArray arrayWithObject:sd]];
   NSLog(@"%@", sorted);

   [sd release];

   [pool release];

   return 0;

}</lang>

OCaml

<lang ocaml># let people = [("Joe", 12); ("Bob", 8); ("Alice", 9); ("Harry", 2)];; val people : (string * int) list = 

 [("Joe", 12); ("Bob", 8); ("Alice", 9); ("Harry", 2)]
  1. let sortedPeopleByVal = List.sort (fun (_, v1) (_, v2) -> compare v1 v2) people;;

val sortedPeopleByVal : (string * int) list = 

 [("Harry", 2); ("Bob", 8); ("Alice", 9); ("Joe", 12)]</lang>

Oz

<lang oz>declare 

 People = [person(name:joe value:3)
           person(name:bill value:4)
           person(name:alice value:20)
           person(name:harry value:3)]

 SortedPeople = {Sort People
                 fun {$ P1 P2}
                    P1.name < P2.name
                 end
                }

in 

 {ForAll SortedPeople Show}</lang>

PARI/GP

The flag "2" means that lexicographic sorting is to be used; the "1" means that the array is to be sorted using the first element of each constituent vector. <lang parigp>vecsort([["name", "value"],["name2", "value2"]], 1, 2)</lang>

Perl

Sort by name using cmp to compare strings: <lang perl>@people = (['joe', 120], ['foo', 31], ['bar', 51]); @people = sort { $a->[0] cmp $b->[0] } @people;</lang>

Sort by number using <=> to compare numbers: <lang perl>@people = (['joe', 120], ['foo', 31], ['bar', 51]); @people = sort { $a->[1] <=> $b->[1] } @people;</lang>

Perl 6

Works with: Rakudo Star version 2010.08

<lang perl6>my class Employee { 

  has Str $.name;
  has Num $.wage;

}

my $boss = Employee.new( name => "Frank Myers" , wage => 6755.85 ); my $driver = Employee.new( name => "Aaron Fast" , wage => 2530.40 ); my $worker = Employee.new( name => "John Dude" , wage => 2200.00 ); my $salesman = Employee.new( name => "Frank Mileeater" , wage => 4590.12 );

my @team = $boss, $driver, $worker, $salesman;

my @orderedByName = @team.sort( *.name )».name; my @orderedByWage = @team.sort( *.wage )».name;

say "Team ordered by name (ascending order):"; say @orderedByName.join(' '); say "Team ordered by wage (ascending order):"; say @orderedByWage.join(' ');</lang> this produces the following output: 

Team ordered by name (ascending order): 
Aaron Fast   Frank Mileeater   Frank Myers   John Dude   
Team ordered by wage (ascending order): 
John Dude   Aaron Fast   Frank Mileeater   Frank Myers

Note that when the sort receives a unary function, it automatically generates an appropriate comparison function based on the type of the data.

PicoLisp

By default, the sort function in PicoLisp returns an ascending list (of any type) <lang PicoLisp>: (sort '(("def" 456) ("abc" 789) ("ghi" 123))) -> (("abc" 789) ("def" 456) ("ghi" 123))</lang> To sort by a certain sub-element, the function by can be used. For example, to sort by the first element <lang PicoLisp>: (by car sort '(("def" 456) ("abc" 789) ("ghi" 123))) -> (("abc" 789) ("def" 456) ("ghi" 123))</lang> or by the second element <lang PicoLisp>: (by cadr sort '(("def" 456) ("abc" 789) ("ghi" 123))) -> (("ghi" 123) ("def" 456) ("abc" 789))</lang>

PureBasic

PureBasic natively supports sorting of structured data with;

  • SortStructuredArray()
  • SortStructuredList()

The on-line documentations gives a more complete picture.


Example <lang PureBasic>Structure MyPair ; Define a structured data type 

 Name$
 Value.i

EndStructure

Dim People.MyPair(2)  ; Allocate some elements

People(0)\Name$ = "John"  ; Start filling them in People(0)\Value = 100

People(1)\Name$ = "Emma" People(1)\Value = 200

People(2)\Name$ = "Johnny" People(2)\Value = 175

If OpenConsole() 

 Define i
 ; Sort ascending by name
 SortStructuredArray(People(), #PB_Sort_Ascending, OffsetOf(MyPair\Name$), #PB_Sort_String)
 PrintN(#CRLF$+"Sorted ascending by name.")
 For i=0 To 2
   PrintN(People(i)\Name$+" - Value: "+Str(People(i)\Value))
 Next
 ; Sort descending by value
 SortStructuredArray(People(), #PB_Sort_Descending, OffsetOf(MyPair\Value), #PB_Sort_Integer)
 PrintN(#CRLF$+"Sorted descending by value.")
 For i=0 To 2
   PrintN(People(i)\Name$+" - Value: "+Str(People(i)\Value))
 Next
 ; Wait for user...
 PrintN(#CRLF$+"Press ENTER to exit"):Input()

EndIf</lang>

Outputs 

Sorted ascending by name.
Emma - Value: 200
John - Value: 100
Johnny - Value: 175

Sorted descending by value.
Emma - Value: 200
Johnny - Value: 175
John - Value: 100

Python

Recent versions of Python provide the sorted() built-in that works on any iterable.

<lang python>people = [('joe', 120), ('foo', 31), ('bar', 51)] sorted(people)</lang> Which leaves people with the value: <lang python>[('bar', 51), ('foo', 31), ('joe', 120)]</lang>


The most Pythonic (and fastest) version is to use itemgetter together with the key parameter to perform the Decorate-sort-undecorate pattern:

<lang python>from operator import itemgetter people = [(120, 'joe'), (31, 'foo'), (51, 'bar')] people.sort(key=itemgetter(0))</lang> Which leaves people with the value: <lang python>[(51, 'bar'), (31, 'foo'), (120, 'joe')]</lang>

R

In R, vectors can have names associated with any of its elements. The data is taken from the Common Lisp example. <lang R>sortbyname <- function(x, ...) x[order(names(x), ...)] x <- c(texas=68.9, ohio=87.8, california=76.2, "new york"=88.2) sortbyname(x)</lang> 

california   new york       ohio      texas 
      76.2       88.2       87.8       68.9

<lang R>sortbyname(x, decreasing=TRUE)</lang> 

     texas       ohio   new york california 
      68.9       87.8       88.2       76.2

Ruby

<lang ruby>Person = Struct.new(:name,:value) list = [Person.new("Joe",3), 

       Person.new("Bill",4),
       Person.new("Alice",20),
       Person.new("Harry",3)]

list.sort_by{|x|x.name}</lang>

Seed7

<lang seed7>$ include "seed7_05.s7i";

const type: pair is new struct 

   var string: name is "";
   var string: value is "";
 end struct;

const func integer: compare (in pair: pair1, in pair: pair2) is 

 return compare(pair1.name, pair2.name);

const func string: str (in pair: aPair) is 

 return "(" <& aPair.name <& ", " <& aPair.value <& ")";

enable_output(pair);

const func pair: pair (in string: name, in string: value) is func 

 result
   var pair: newPair is pair.value;
 begin
   newPair.name := name;
   newPair.value := value;
 end func;

var array pair: data is [] ( 

   pair("Joe",    "5531"),
   pair("Adam",   "2341"),
   pair("Bernie", "122"),
   pair("Walter", "1234"),
   pair("David",  "19"));

const proc: main is func 

 local
   var pair: aPair is pair.value;
 begin
   data := sort(data);
   for aPair range data do
     writeln(aPair);
   end for;
 end func;</lang>

Output: 

(Adam, 2341)
(Bernie, 122)
(David, 19)
(Joe, 5531)
(Walter, 1234)

Tcl

Modeling the data structure being sorted as a list (a common Tcl practice): <lang tcl>set people {{joe 120} {foo 31} {bar 51}}

  1. sort by the first element of each pair

lsort -index 0 $people</lang>

UNIX Shell

With this language, everything is a string. My list of pairs is a string where a colon ":" separates "name:value", and a newline separates different pairs. Then I can use sort -t: -k1,1 to sort the pairs by name.

<lang bash>list="namez:order! name space:in name1:sort name:Please"

newline=" "

dumplist() { ( IFS=$newline for pair in $list; do ( IFS=: set -- $pair echo " $1 => $2" ) done ) }

echo "Original list:" dumplist

list=`IFS=$newline; printf %s "$list" | sort -t: -k1,1`

echo "Sorted list:" dumplist</lang>

Output: 

Original list:
  namez => order!
  name space => in
  name1 => sort
  name => Please
Sorted list:
  name => Please
  name space => in
  name1 => sort
  namez => order!

Ursala

The built in sort operator, -<, can be parameterized by an anonymous field specification and/or a relational predicate. <lang Ursala>#import std

  1. cast %sWLW

examples =

( 

  -<&l <('z','a'),('x','c'),('y','b')>,  # sorted by the left
  -<&r <('z','a'),('x','c'),('y','b')>)  # sorted by the right</lang>

output: 

(
   <('x','c'),('y','b'),('z','a')>,
   <('z','a'),('y','b'),('x','c')>)

a more verbose example, showing a list of records of a user defined type sorted by a named field:

<lang Ursala>#import std

person :: name %s value %s

people =

< 

  person[name: 'Marilyn Monroe',value: 'priceless'],
  person[name: 'Victor Hugo',value: 'millions'],
  person[name: 'Johnny Carson',value: 'up there']>
  1. cast _person%L

example = (lleq+ ~name~~)-< people</lang> output: 

<
   person[name: 'Johnny Carson',value: 'up there'],
   person[name: 'Marilyn Monroe',value: 'priceless'],
   person[name: 'Victor Hugo',value: 'millions']>
Retrieved from "https://rosettacode.org/wiki/Sort_an_array_of_composite_structures?oldid=32825"