Decorate-sort-undecorate idiom: Difference between revisions
m
→{{header|Fōrmulæ}}
| (13 intermediate revisions by 8 users not shown) | |||
Line 1:
{{task}}
[[Category:Sorting]]
;Introduction
Line 210 ⟶ 212:
<pre>
["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
</pre>
=={{header|C sharp|C#}}==
Linq makes this very easy. We can do this using 2 different syntaxes:
<syntaxhighlight lang="csharp">
public static IEnumerable<T> Schwartzian1<T, TKey>(IEnumerable<T> source, Func<T, TKey> decorator) =>
source.Select(item => (item, key: decorator(item)))
.OrderBy(tuple => tuple.key)
.Select(tuple => tuple.item);
public static IEnumerable<T> Schwartzian2<T, TKey>(IEnumerable<T> source, Func<T, TKey> decorator) =>
from item in source
let key = decorator(item)
orderby key
select item;
//Call:
string[] array = {"Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site"};
Console.WriteLine(string.Join(" ", Schwartzian1(array, i => i.Length)));
</syntaxhighlight>
{{out}}
<pre>
a is Code site Rosetta programming chrestomathy
</pre>
=={{header|C++}}==
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iostream>
#include <type_traits>
#include <vector>
template <typename Iterator, typename Function>
void decorate_sort_undecorate(Iterator begin, Iterator end, Function f) {
using ValueType = typename std::iterator_traits<Iterator>::value_type;
using KeyType = std::invoke_result_t<Function, ValueType>;
using KeyValue = std::pair<KeyType, ValueType>;
std::vector<KeyValue> tmp;
tmp.reserve(std::distance(begin, end));
std::transform(begin, end, std::back_inserter(tmp), [&f](ValueType& v) {
return std::make_pair(f(v), std::move(v));
});
std::sort(tmp.begin(), tmp.end(), [](const KeyValue& a, const KeyValue& b) {
return a.first < b.first;
});
std::transform(tmp.begin(), tmp.end(), begin,
[](KeyValue& p) { return std::move(p.second); });
}
int main() {
std::string test[] = {"Rosetta", "Code", "is", "a",
"programming", "chrestomathy", "site"};
decorate_sort_undecorate(std::begin(test), std::end(test),
[](const std::string& s) { return s.size(); });
for (const std::string& s : test)
std::cout << s << ' ';
std::cout << '\n';
}</syntaxhighlight>
{{out}}
<pre>
a is Code site Rosetta programming chrestomathy
</pre>
Line 287 ⟶ 350:
'''Solution'''
Let us create an array for testing:
[[File:Fōrmulæ - Decorate-sort-undecorate idiom 01.png]]
'''Decorate-sort-undecorate:''' The following is a solution using a decorate-sort-undecorate idiom:
Line 296 ⟶ 363:
[[File:Fōrmulæ - Decorate-sort-undecorate idiom 03.png]]
[[File:Fōrmulæ - Decorate-sort-undecorate idiom
Line 405 ⟶ 472:
=={{header|J}}==
J's native sort primitive always sorts on a key (which might be the list itself), such that each element of the key is calculated only once. This corresponds to APL's grade up primitive (though comparing dates on this approach vs. lisp's approach seems problematic due to deficiencies in historical evidence).
Line 419 ⟶ 485:
chrestomathy
</syntaxhighlight>
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.AbstractMap;
import java.util.List;
import java.util.function.Function;
import java.util.stream.Collectors;
public final class DecorateSortUndecorateIdiom {
public static void main(String[] args) {
List<String> list = List.of( "Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site" );
System.out.println(schwartzian(list, s -> s.length()));
}
/**
* Return a sorted list using the Schwartzian Transform
* which guarantees minimal use of the key extractor function.
*
* Use this method when the key extractor function is an expensive operation.
*/
private static <T, R extends Comparable<R>> List<T> schwartzian(List<T> list, Function<T, R> function) {
return list.stream().map( s -> new AbstractMap.SimpleEntry<T, R>(s, function.apply(s)) )
.sorted( (one, two) -> one.getValue().compareTo(two.getValue()) )
.map( p -> p.getKey() )
.collect(Collectors.toList());
}
}
</syntaxhighlight>
{{ out }}
<pre>
[a, is, Code, site, Rosetta, programming, chrestomathy]
</pre>
=={{header|JavaScript}}==
Line 670 ⟶ 770:
Of course, it is also possible to define a comparison function to sort by length then alphabetically and use it when sorting.
=={{header|Nu}}==
<syntaxhighlight lang="nu">
def 'sort by key' [keyfunc] {
( each {|v| {k: ($v | do $keyfunc ), v: $v}}
| sort-by k
| each {get v} )
}
"Rosetta Code is a programming chrestomathy site" | split words | sort by key {str length}
</syntaxhighlight>
{{out}}
<pre>
╭───┬──────────────╮
│ 0 │ a │
│ 1 │ is │
│ 2 │ Code │
│ 3 │ site │
│ 4 │ Rosetta │
│ 5 │ programming │
│ 6 │ chrestomathy │
╰───┴──────────────╯
</pre>
=={{header|Perl}}==
<syntaxhighlight lang="perl">#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Decorate-sort-undecorate_idiom
use warnings;
use List::AllUtils qw( nsort_by );
my @list = ("Rosetta", "Code", "is", "a", "programming", "chrestomathy", "site");
print "@list\n";
my @sortedlist = nsort_by { length } @list;
print "@sortedlist\n";</syntaxhighlight>
{{out}}
<pre>
Rosetta Code is a programming chrestomathy site
a is Code site Rosetta programming chrestomathy
</pre>
=={{header|Phix}}==
Line 891 ⟶ 1,032:
cached: ["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
transform: ["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">var str = "Rosetta Code is a programming chrestomathy site"
# Built-in
say str.split.sort_by{.len}
# Same thing explicitly
say str.split.map {|w| [w, w.len] }.sort{|a,b| a[1] <=> b[1] }.map { _[0] }
# Sort by word length, then lexical:
var str2 = str+" seven extra words added to this demo"
say str2.split.sort_by{|word| [word.len, word] }</syntaxhighlight>
{{out}}
<pre>
["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
["a", "is", "Code", "site", "Rosetta", "programming", "chrestomathy"]
["a", "is", "to", "Code", "demo", "site", "this", "added", "extra", "seven", "words", "Rosetta", "programming", "chrestomathy"]
</pre>
Line 898 ⟶ 1,058:
It's not specified how words of equal length are to be sorted. The standard sort() method used here (quicksort under the hood) is unstable and so the sort order for such words is not guaranteed.
<syntaxhighlight lang="
System.print(a.map { |e| [e, f.call(e)] } // decorate
.toList
| |||