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
<lang algol>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++
<lang cpp>
- include <iterator>
- include <algorithm>
- 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)
{
return s1.*member < s2.*member;
}
private:
MemberType Struct::*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>
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.
CL-USER> (defparameter *test-scores* '(("texas" 68.9) ("ohio" 87.8) ("california" 76.2) ("new york" 88.2)) )
*TEST-SCORES*
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:
CL-USER> (sort (copy-list *test-scores*) #'string-lessp :key #'first)
(("california" 76.2) ("new york" 88.2) ("ohio" 87.8) ("texas" 68.9))
we can also sort by the test scores by supplying a different key function that return the test score instead:
CL-USER> (sort (copy-list *test-scores*) #'< :key #'second)
(("texas" 68.9) ("california" 76.2) ("ohio" 87.8) ("new york" 88.2))
D
<lang d>module sortcomposite ; import std.stdio ; import std.algorithm ;
struct S {
string name ;
string value ;
int amount ;
string toString() {
return "<" ~ name ~ "|" ~ value ~ "|" ~ std.string.toString(amount) ~ ">" ;
}
}
T[] csort(string FIELD , T)(T[] arr) {
mixin("sort!(\"a." ~ FIELD ~ " < b." ~ FIELD ~ "\")(arr) ;") ;
//compile as statement :
// sort!("a.FIELD < b.FIELD")(arr) ;
return arr ;
}
void main() {
S[] datas = [S("Joe", "0x47f", 13), S("Bob", "0x100", 31),
S("Alice", "0x3e8", 50), S("Harry", "0x2d4", 43)] ;
sort!("a.name < b.name")(datas) ;
writefln(datas) ;
writefln(csort!("value")(datas)) ;
writefln(csort!("amount")(datas)) ;
}</lang> Limitation: The field name has to be compile-time determined.
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>
Fortran
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
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
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
J
The function /: sorts anything. For example:
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| +-------+---------+
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
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
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
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() {
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]; return 0;
}</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)]
# let sortedPeopleByVal = List.sort (fun (_, v1) (_, v2) -> compare v1 v2) people;;
val sortedPeopleByVal : (string * int) list =
[("Harry", 2); ("Bob", 8); ("Alice", 9); ("Joe", 12)]
Perl
Sort by name using cmp to compare strings:
@people = (['joe', 120], ['foo', 31], ['bar', 51]);
@people = sort { $a->[0] cmp $b->[0] } @people;
Sort by number using <=> to compare numbers:
@people = (['joe', 120], ['foo', 31], ['bar', 51]);
@people = sort { $a->[1] <=> $b->[1] } @people;
Python
The easy case describe in this task, the name is the first item of a tuple, simple sort just works:
people = [('joe', 120), ('foo', 31), ('bar', 51)]
people.sort()
If the name is not the first one, you can use a cmp (for comparison) function:
people = [(120, 'joe'), (31, 'foo'), (51, 'bar')] people.sort( lambda x, y: cmp(x[1], y[1]) )
But this is slow for large data sets. To make it much faster, use the Schwartzian_transform:
people = [(120, 'joe'), (31, 'foo'), (51, 'bar')] tmp = [(person[1], person) for person in people] tmp.sort() people = [person for key, person in tmp]
Recent Python versions add a key argument to sort, which make this much cleaner:
people = [(120, 'joe'), (31, 'foo'), (51, 'bar')] people.sort(key=lambda x: x[0])
The most Pythonic (and faster) version is using itemgetter:
from operator import itemgetter people = [(120, 'joe'), (31, 'foo'), (51, 'bar')] people.sort(key=itemgetter(0))
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}
Tcl
Modeling the data structure being sorted as a list (a common Tcl practice): <lang tcl>set people {{joe 120} {foo 31} {bar 51}}
- sort by the first element of each pair
lsort -index 0 $people</lang>