Sort an array of composite structures: Difference between revisions

{{Sorting Algorithm}}

[[Category:Sorting]]

 

Sort an array of composite structures by a key.

and an array of such pairs:

 

 

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

 

<br><br>

 

=={{header|ACL2}}==

(cond ((endp os) (list o))

((< (cdr (assoc key o))

(weight . 15)

(value . 60)))

 

Output:

(WEIGHT . 153)

(VALUE . 200)))</pre>

 

=={{header|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.

with Ada.Text_IO; use Ada.Text_IO;

 

Put_Line (Data (I));

end loop;

Result:

<pre>

</pre>

[[Ada 2005]] also provides ordered containers, so no explicit call is required. Here is an example of an ordered set:

with Ada.Text_IO; use Ada.Text_IO;

 

Data.Insert (New_Item => (Name => +"David", Value => +"19"));

Data.Iterate (Put_Line'Access);

Result:

<pre>

</pre>

There is no standard sort function for [[Ada 95]]. The example below implements a simple bubble sort.

with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;

 

Sort_Name(My_Pairs);

Print(My_Pairs);

 

=={{header|ALGOL 68}}==

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput}} -->

OP < = (PERSON a,b)BOOL: age OF a < age OF b;

PR READ "prelude/sort.a68" PR;

 

[]SORTSTRUCT person = (("joe", 120), ("foo", 31), ("bar", 51));

Output:

<pre>

macOS Yosemite onwards, for import of Foundation framework

 

 

----- SORTING COMPOSITE STRUCTURES (BY MULTIPLE KEYS) ------

end script

end if

{{Out}}

<pre>{{pop:24.2, city:"Sao Paulo "}, {pop:24.2, city:"Shanghai "}, {pop:23.5, city:"Karachi "}, {pop:21.5, city:"Beijing "}, {pop:17.0, city:"Dhaka "}, {pop:16.8, city:"Delhi "}, {pop:16.1, city:"Lagos "}}</pre>

 

 

 

 

 

{{out}}

 

 

=={{header|AutoHotkey}}==

built ListView Gui, contains a table sorting function which can be used for this.

Gui, Add, ListView, r20 w200, 1|2

data =

 

GuiClose:

 

=={{header|AWK}}==

# syntax: GAWK -f SORT_AN_ARRAY_OF_COMPOSITE_STRUCTURES.AWK

BEGIN {

printf("\n")

}

{{out}}

<pre>

First, we construct a list-of-maps and assign it to variable baz. Next, we sort baz by key "foo" and assign it to variable bop. Finally, we lookup "foo" in each map in list bop and display the resulting list of numbers - they are in sorted order.

 

babel> bop baz { <- "foo" lumap ! -> "foo" lumap ! lt? } lssort ! <

babel> bop {"foo" lumap !} over ! lsnum !

 

The same technique works for any list of data-objects you may have. User-code can expect to have the top two elements of the stack set to be the two objects to be compared. Simply access the relevant field in each object, and then perform a comparison. For example, here is a list of pairs sorted by first element:

 

babel> dup {lsnum !} ... --> display the shuffled list, pair-by-pair

( 11 10 )

( 15 13 )

( 17 3 )

 

The gpsort utility performs this kind of comparison "automagically" by leveraging the ordering of Babel's underlying data-structure. Using the shuffled list from the example above:

 

babel> dup {lsnum !} ...

( 0 2 )

( 15 13 )

( 17 3 )

 

Note that gpsort will not work for the case where you want to sort on the second element of a list of pairs. But it will work for performing a canonical sort on numbers, arrays of numbers, lists of numbers, lists of lists, lists of arrays, arrays of lists, and so on. You should not use gpsort with strings; use lexsort or strsort instead. Here's an example of sorting a mixture of pairs and triples using gpsort:

 

( 7 2 )

( 6 4 )

( 8 2 3 )

( 9 6 10 )

 

=={{header|BBC BASIC}}==

{{works with|BBC BASIC for Windows}}

Uses the supplied SORTSALIB library.

sort% = FN_sortSAinit(0,0)

FOR i% = 1 TO DIM(array{()}, 1)

PRINT array{(i%)}.name$, array{(i%)}.number%

Output:

<pre>

=={{header|Bracmat}}==

The easiest way to sort an array of elements in Bracmat is to handle it as a sum of terms. A sum, when evaluated, is automatically sorted.

& out$"unsorted array:"

& lst$tab

& out$"But tab is still unsorted:"

& lst$tab

 

Output:

 

When evaluating <code>!tab</code>, the expression bound to the variable name <code>tab</code> is sorted, but the unevaluated expression is still bound to <code>tab</code>. An assignment binds the sorted expression to <code>tab</code>:

& out$"Now tab is sorted:"

& lst$tab

 

Output:

 

To sort an array that is not a sum expression, we can convert it to a sum:

((name.compass),(weight.13),(value.35))

((name.water),(weight.153),(value.200))

& out$("Array after sorting (descending order):" !array \n)

& out$("Array after sorting (ascending order):" reverse$!array \n)

 

Output:

 

Bracmat has a left to right sorting order. If an array must be sorted on another field than the first field, that other field has to be made the first field. After sorting, the fields can take their original positions.

(Adam,2341)

(Bernie,122)

\n

)

 

Output:

=={{header|C}}==

Using qsort, from the standard library.

#include <stdio.h>

#include <stdlib.h>

 

return 0;

Output:

<pre> This is the order in which many strings should be sorted.

{{works with|C sharp|C#|3+}}

 

using System.Collections.Generic;

using System.Linq;

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

}

 

Output:

Uses C++11. Compile with

g++ -std=c++11 sort.cpp

#include <iostream>

#include <string>

std::cout << "{" << e.name << ", " << e.value << "}\n";

}

Output:

<pre>

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)''.

 

;; Gathered with Google Squared

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

 

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

 

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''.

 

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

 

 

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

 

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

Let's define a composite structure of U.S. states and average 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:

 

 

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

 

 

=={{header|D}}==

 

struct Pair { string name, value; }

 

pairs.schwartzSort!q{ a.name }.writeln;

{{out}}

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

 

=={{header|Delphi}}==

 

{$APPTYPE CONSOLE}

Result := CompareText(Left.Name, Right.Name);

end));

 

=={{header|E}}==

 

return def comparer(a, b) {

return keyfn(a).op__cmp(keyfn(b))

]

 

 

=={{header|EchoLisp}}==

;; sorting (name value) by name - Ignoring case

(define (name a) (first a))

→ (("albert" 33) ("Antoinette" 42) ("elvis" 666) ("Simone" 44) ("😃" 1000) ("😎" -42))

 

 

=={{header|Elena}}==

import extensions;

KeyValue.new("Germanium", 72.64r)};

{

console.printLine(element.Key," - ",element)

}

 

=={{header|Elixir}}==

defstruct name: "", value: 0

end

Enum.sort(list) |> Enum.each(fn x -> IO.inspect x end)

IO.puts ""

 

{{out}}

=={{header|Erlang}}==

Any Erlang type can be compared to any Erlang type. As such, nothing special needs to be done:

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

{{2002,2003},"Devils"},

{{2006,2007},"Ducks"},

{{2007,2008},"Red Wings"},

 

It is also possible to sort with custom functions, in this case by the team's name:

#Fun<erl_eval.12.113037538>

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

{{2008,2009},"Penguins"},

{{2007,2008},"Red Wings"},

 

=={{header|Euphoria}}==

include misc.e

 

{ "cherry", "red" } }

 

 

Output:

=={{header|F_Sharp|F#}}==

F# has <code>sortBy</code> functions that work on collection types for this purpose. An example using an array of pairs:

Array.sortInPlaceBy fst persons

Output:

 

An example using a list of records:

let persons2 = [{name="Joe"; id=120}; {name="foo"; id=31}; {name="bar"; id=51}]

let sorted = List.sortBy (fun p -> p.id) persons2

 

Output:

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

 

 

 

( scratchpad ) { T{ example-pair f "omega" "a" } T{ example-pair f "gamma" "q" } T{ example-pair f "alpha" "z" } } sort-by-name .

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

 

class Pair // create a composite structure

{

}

}

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

Standard Fortran has no built-in sort function although some compilers add them. The following example uses an insertion sort.

IMPLICIT NONE

 

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

 

Output

Black 0

 

=={{header|FreeBASIC}}==

 

Type Pair

Print

Print "Press any key to quit"

 

{{out}}

[snow, white]

</pre>

 

=={{header|Go}}==

 

import (

fmt.Printf("%5s: %s\n", p.name, p.value)

}

 

=={{header|Groovy}}==

def date

def name

 

holidays.sort { x, y -> x.date <=> y.date }

 

Output:

 

=={{header|Haskell}}==

import Data.Function (on)

 

mapM_ print $ sort people

putStrLn []

 

{{Out}}

To sort a list of triples by the third element, for example:

 

import Data.List (sortBy)

 

 

main :: IO ()

{{Out}}

<pre>("Maurice","Wilkes",1913)

=={{header|Icon}} and {{header|Unicon}}==

The built-in procedure sortf will sort a list by the field in a records.

 

procedure main()

write("Some Orion stars by HIP#")

every write( (x := !sortf(Ori,2)).name, " HIP ",x.HIP)

 

Sample output:<pre>Some Orion stars by HIP#

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

 

values=: ;: 'Alan Maurice Richard Marvin James John'

pairs =: values ,. names

+-------+---------+

|James |Wilkinson|

 

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).

 

=={{header|Java}}==

import java.util.Comparator;

 

});

}

Output:

<pre>00-01 Avalanche

In Java 8, we can write the above using a lambda:

{{works with|Java|8+}}

Arrays.sort(pairs, (p1, p2) -> p1.name.compareTo(p2.name));

 

We can further use <code>Comparator.comparing()</code> to construct the comparator from a "key" function:

{{works with|Java|8+}}

Arrays.sort(pairs, Comparator.comparing(p -> p.name));

 

=={{header|JavaScript}}==

===ES5===

{id: 3, value: "foo"},

{id: 2, value: "bar"},

];

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

 

===ES6===

 

'use strict';

 

.sort(on(flip(compare), name))

});

 

{{Out}}

=={{header|jq}}==

In this section we will focus on JSON objects since the task description mentions keys. As an example, we will use this array:

[

{"name": "Joe", "value": 3},

{"name": "Alice", "value": 20},

{"name": "Harry", "value": 3}

====Using sort_by builtin ====

jq's sort_by builtin can be used to sort by the value of a given key (whether or not it is a string), so we will first use that.

# example | sort_by(.name)

 

# To abbreviate the results, we will just show the names after sorting:

 

{{Out}}

$ jq -n -c -f Sort_an_array_of_composite_structures.jq

====Using quicksort(cmp)====

sort_by(f) can easily be implemented using quicksort(cmp) as defined at [[Sorting_Using_a_Custom_Comparator#jq]] as follows:

'''Example''':

{{Out}}

As above.

{{works with|Julia|0.6}}

 

Pair("neon", "inert"),

Pair("sulphur", "yellow"),

println("\nThe list, sorted by name: \n - ", join(lst, "\n - "))

sort!(lst; by=last)

 

{{out}}

 

=={{header|Kotlin}}==

 

data class Employee(val name: String, var category: String) : Comparable<Employee> {

employees.sort()

for ((name, category) in employees) println("${name.padEnd(6)} : $category")

 

{{out}}

 

=={{header|Lambdatalk}}==

{def H.sort

{def H.sort.i

David Bernie Walter Adam Joe

19 122 1234 2341 5531

 

=={{header|Liberty BASIC}}==

<br>

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.

N =20

dim IntArray$( N, 2)

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

next i

 

=={{header|Lua}}==

return a[1] < b[1]

end

for _, v in ipairs( tab ) do

print( unpack(v) )

 

=={{header|M2000 Interpreter}}==

Checkit3 same as CheckIt3 except values are groups, which now have only a x as value, but we can add more.

 

Module CheckIt {

Flush ' empty stack of values

}

Checkit3

 

{{Out}}

</pre>

 

"Earth Day"}, {"2009-09-07", "Labor Day"}, {"2009-07-04",

"Independence Day"}, {"2009-10-31", "Halloween"}, {"2009-05-25",

name = 2;

SortBy[events, #[[name]] &] // Grid

gives back:

2009-04-22 Earth Day

2009-10-31 Halloween

2009-11-26 Thanksgiving

2009-12-25 Christmas Day

 

=={{header|MAXScript}}==

(

case of

people = #(#("joe", 39), #("dave", 37), #("bob", 42))

qsort people keyCmp

 

=={{header|NetRexx}}==

options replace format comments java crossref symbols nobinary

 

else signal IllegalArgumentException('Arguments must be of type PairBean')

return cRes

'''Output:'''

<pre>

 

=={{header|Nim}}==

 

var people = @{"joe": 120, "foo": 31, "bar": 51}

sort(people, (x,y) => cmp(x[0], y[0]))

 

=={{header|Objeck}}==

use Collection;

 

}

}

 

<pre>

 

=={{header|Objective-C}}==

NSString *name;

NSString *value;

 

return 0;

 

=={{header|OCaml}}==

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 =

 

=={{header|Oforth}}==

 

{{out}}

<pre>

[[Adam, 2341], [Bernie, 122], [David, 19], [Joe, 5531]]

</pre>

 

=={{header|ooRexx}}==

a = .array~new

 

-- perform the comparison on the names

return -left~name~compareTo(right~name)

Output:

<pre>

 

=={{header|Oz}}==

People = [person(name:joe value:3)

person(name:bill value:4)

}

in

 

=={{header|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.

 

=={{header|Pascal}}==

=={{header|Perl}}==

Sort by name using cmp to compare strings:

 

Sort by number using <=> to compare numbers:

 

=={{header|Phix}}==

The standard sort compares the first element, then 2nd, 3rd, etc. A custom_sort or sort_columns can be used to sort by other elements.<br>

Elements can be any mix of types, with atoms (ie ints/floats) deemed less than sequences/strings.

{{out}}

<pre>

{{3.4,-1},{0,1.2},{"sky","blue"},{"grass","green"},{"cherry","red"},{"snow","white"}}

</pre>

 

=={{header|Phixmonti}}==

 

def minverse

 

/# sorted by second component #/

 

=={{header|PicoLisp}}==

By default, the [http://software-lab.de/doc/refS.html#sort sort] function in

PicoLisp returns an ascending list (of any type)

To sort by a certain sub-element, the function

[http://software-lab.de/doc/refB.html#by by] can be used. For example, to

sort by the first element

or by the second element

 

=={{header|PowerShell}}==

{{works with|PowerShell|4.0}}

 

$list = @{

"def" = "one"

}

$list.GetEnumerator() | sort {-($PSItem.Name).length}, Name

<b>Output:</b>

<pre>

 

'''Example'''

Name$

Value.i

; Wait for user...

PrintN(#CRLF$+"Press ENTER to exit"):Input()

 

'''Outputs

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

 

Which leaves <code>people</code> with the value:

 

<br>The most Pythonic (and fastest) version is to use itemgetter together with the key parameter to <code>sort</code> resp. <code>sorted</code> to perform the [[wp:Decorate-sort-undecorate|Decorate-sort-undecorate]] pattern:

 

people = [(120, 'joe'), (31, 'foo'), (51, 'bar')]

Which leaves <code>people</code> with the value:

 

=={{header|R}}==

In R, vectors can have names associated with any of its elements. The data is taken from the Common Lisp example.

x <- c(texas=68.9, ohio=87.8, california=76.2, "new york"=88.2)

california new york ohio texas

76.2 88.2 87.8 68.9

 

texas ohio new york california

68.9 87.8 88.2 76.2

 

=={{header|Racket}}==

#lang racket

 

(sort data string<? #:key (compose1 symbol->string car))

;; --> '((Adam 2341) (Bernie 122) (David 19) (Joe 5531) (Walter 1234))

 

=={{header|Raku}}==

(formerly Perl 6)

{{Works with|rakudo|2016.05}}

has Str $.name;

has Rat $.wage;

say @orderedByName.join(' ');

say "Team ordered by wage (ascending order):";

this produces the following output:

<pre>Team ordered by name (ascending order):

=={{header|REXX}}==

This version sorts the structure by color; &nbsp; as entered (built), &nbsp; the structure is ordered by value (percent).

'''output''' &nbsp; when using the (internal) default inputs:

<pre>

 

=={{header|Ring}}==

aList= sort([:Eight = 8, :Two = 2, :Five = 5, :Nine = 9, :One = 1,

:Three = 3, :Six = 6, :Seven = 7, :Four = 4, :Ten = 10] , 2)

? item[1] + space(10-len(item[1])) + item[2]

next

{{out}}

<pre>

=={{header|Ruby}}==

 

def to_s; "name:#{name}, value:#{value}" end

end

puts list.sort_by{|x|x.name}

puts

{{out}}

<pre>

 

=={{header|Run BASIC}}==

mem$ = "CREATE TABLE people(num integer, name text,city text)"

#mem execute(mem$)

city$ = #row city$()

print num;" ";name$;" ";city$

5 Frank Houston

2 Fred Oregon

=={{header|Rust}}==

{{trans|Kotlin}}

 

#[derive(Debug)]

println!("{:<6} : {}", e.name, e.category);

}

{{out}}

<pre>Alice : Sales

 

=={{header|Scala}}==

val input = Array(Pair("Krypton", 83.798), Pair("Beryllium", 9.012182), Pair("Silicon", 28.0855))

input.sortBy(_.name) // Array(Pair(Beryllium,9.012182), Pair(Krypton,83.798), Pair(Silicon,28.0855))

// alternative versions:

input.sortBy(struct => (struct.name, struct.value)) // additional sort field (name first, then value)

 

=={{header|Seed7}}==

 

const type: pair is new struct

writeln(aPair);

end for;

 

Output:

 

=={{header|Sidef}}==

var people = [['joe', 120], ['foo', 31], ['bar', 51]];

 

 

# Display the sorted array

 

{{out}}

 

=={{header|Simula}}==

 

CLASS COMPARABLE;;

OUTIMAGE;

{{out}}

<pre>ADAM 2341

 

=={{header|SQL}}==

create table pairs (name varchar(16), value varchar(16));

insert into pairs values ('Fluffy', 'cat');

insert into pairs values ('Francis', 'fish');

-- order them by name

{{out}}

<pre>NAME VALUE

=={{header|Swift}}==

 

func sorted<Value>(

on: KeyPath<Element, Value>,

let c = Person(name: "charlie", role: "driver")

 

 

{{out}}

=={{header|Tcl}}==

Modeling the data structure being sorted as a list (a common Tcl practice):

# sort by the first element of each pair

 

=={{header|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 <tt>sort -t: -k1,1</tt> to sort the pairs by name.

 

name space:in

name1:sort

 

echo "Sorted list:"

 

Output: <pre>Original list:

The built in sort operator, -<, can be parameterized by an

anonymous field specification and/or a relational predicate.

 

#cast %sWLW

(

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

output:

<pre>(

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

 

 

person :: name %s value %s

#cast _person%L

 

output:

<pre>

=={{header|Wren}}==

{{libheader|Wren-sort}}

 

class Pair is Comparable {

Sort.insertion(pairs)

System.print("\nAfter sorting:")

 

{{out}}

 

=={{header|XPL0}}==

char Dict(10,10);

int Entries;

for I:= 0 to Entries-1 do \show sorted entries

[ChOut(0, Dict(I,0)); ChOut(0, ^ ); Text(0, @Dict(I,1)); CrLf(0)];

 

{{out}}

=={{header|zkl}}==

The list of lists way is available or:

fcn init(nm,val){name,value=vm.arglist}

fcn __opLT(p){name<p.name} // implementation of P1 < P2

p:=List(P("sam","a"),P("fred","b"),P("chris","c"));

p.sort();