Sort an array of composite structures
From Rosetta Code
Programming Task
This is a programming task. It lays out a problem which Rosetta Code users are encouraged to solve, using languages they 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.
Contents |
[edit] Ada
There is no standard sort function for Ada. The example below implements a simple bubble sort.
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;
[edit] 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.
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
Output
Black 0 Blue 6 Brown 1 Green 5 Grey 8 Orange 3 Red 2 Violet 7 White 9 Yellow 4
[edit] 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))
[edit] D
Works with: D version 2.011+
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)) ; }
Limitation: The field name has to be compile-time determined.
[edit] 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
[edit] 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| +-------+---------+
[edit] 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
[edit] 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)]
[edit] Perl
Sort by name using cmp:
@people = (['joe', 120], ['foo', 31], ['bar', 51]);
@people = sort { $a->[0] cmp $b->[0] } @people;
Sort by number using <=>:
@people = (['joe', 120], ['foo', 31], ['bar', 51]);
@people = sort { $a->[1] <=> $b->[1] } @people;
[edit] 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 function:
people = [(120, 'joe'), (31, 'foo'), (51, 'bar')] people.sort(lambda x: x[1])
But it is slow. To make it much faster, use 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, 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))
[edit] 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}
Categories: Programming Tasks | Sorting | Ada | Fortran | Common Lisp | D | Haskell | J | MAXScript | OCaml | Perl | Python | Ruby
