Sort using a custom comparator: Difference between revisions
Line 325: | Line 325: | ||
qSort strList myCmp |
qSort strList myCmp |
||
print strList |
print strList |
||
=={{header|Nial}}== |
|||
sort fork [=[tally first,tally first rest],up,>=[tally first,tally first rest]] ['Here', 'are', 'some', 'sample', 'strings', 'to', 'be', 'sorted'] |
|||
=|strings|sample|sorted|Here|some|are|be|to| |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
Revision as of 20:50, 7 October 2008
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Sort an array (or list) of strings in order of descending length, and in ascending lexicographic order for strings of equal length. Use a sorting facility provided by the language/library, combined with your own callback comparison function.
Note: Lexicographic order is case-insensitive.
Ada
Comparator_Package.ads
package Comparator_Package is procedure Move_String(From : Natural; To : Natural); function Len (Left, Right : Natural) return Boolean; function Lt (Left, Right : Natural) return Boolean; procedure Print_Array; end Comparator_Package;
Comparator_Package.adb
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded; with Ada.Text_Io; use Ada.Text_Io; with Ada.Characters.Handling; use Ada.Characters.Handling; package body Comparator_Package is type Data is array(Natural range <>) of Unbounded_String; Strings : Data := (Null_Unbounded_String, To_Unbounded_String("this"), To_Unbounded_String("is"), To_Unbounded_String("a"), To_Unbounded_String("set"), To_Unbounded_String("of"), To_Unbounded_String("strings"), To_Unbounded_String("to"), To_Unbounded_String("sort")); procedure Move_String(From : Natural; To : Natural) is begin Strings(To) := Strings(From); end Move_String; function Len (Left, Right : Natural) return Boolean is begin return Length(Strings(Left)) > Length(Strings(Right)); end Len; function Lt (Left, Right : Natural) return Boolean is begin return To_Lower(To_String(Strings(Left))) < To_Lower(To_String(Strings(Right))); end Lt; procedure Print_Array is begin for I in 1..Strings'Last loop Put_Line(To_String(Strings(I))); end loop; end Print_Array; end Comparator_Package;
Custom_Comparator.adb
with Gnat.Heap_Sort_A; use Gnat.Heap_Sort_A; with Ada.Text_Io; use Ada.Text_Io; with Comparator_Package; use Comparator_Package; procedure Custom_Comparator is begin Put_Line(" Unsorted Array:"); Print_Array; New_Line; Put_Line(" Sorted in descending length:"); Sort(8, Move_String'access, Len'access); Print_Array; New_Line; Put_Line(" Sorted in Ascending order:"); Sort(8, Move_String'access, Lt'access); Print_Array; end Custom_Comparator;
Output File
Unsorted Array: this is a set of strings to sort Sorted in descending length: strings sort this set to is of a Sorted in Ascending order: a is of set sort strings this to
C
Platform: BSD
#include <stdlib.h> #include <strings.h> int mycmp(const void *s1, const void *s2) { int d; const char *l = *(const char **)s1, *r = *(const char **)s2; if (d = strlen(r) - strlen(l)) return d; return strcasecmp(l, r); } int main() { char *strings[8] = {"Here", "are", "some", "sample", "strings", "to", "be", "sorted"}; qsort(strings, 8, sizeof(char *), mycmp); }
C++
#include <algorithm> #include <string> #include <cctype> // compare character case-insensitive bool icompare_char(char c1, char c2) { return std::toupper(c1) < std::toupper(c2); } // return true if s1 comes before s2 bool compare(std::string const& s1, std::string const& s2) { if (s1.length() > s2.length()) return true; if (s1.length() < s2.length()) return false; return lexicographical_compare(s1.begin(), s1.end(), s2.begin(), s2.end(), icompare_char); } int main() { std::string strings[8] = {"Here", "are", "some", "sample", "strings", "to", "be", "sorted"}; std::sort(strings, strings+8, compare); }
Clean
import StdEnv less s1 s2 | size s1 > size s2 = True | size s1 < size s2 = False | otherwise = lower s1 < lower s2 where lower :: String -> String lower s = {toLower c \\ c <-: s} Start = sortBy less ["This", "is", "a", "set", "of", "strings", "to", "sort"]
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. Common Lisp defines a case-insensitive predicate called string-lessp:
CL-USER> (defvar *strings* ("Cat" "apple" "Adam" "zero" "Xmas" "quit" "Level" "add" "Actor" "base" "butter")) *STRINGS* CL-USER> (sort *strings* #'string-lessp) ("Actor" "Adam" "add" "apple" "base" "butter" "Cat" "Level" "quit" "Xmas" "zero") CL-USER>
D
module customsort ; import tango.io.Stdout ; import tango.text.Ascii ; // for lexi compare // csort need the following 2 modules import tango.util.collection.ArraySeq ; import tango.util.collection.model.Comparator ; T[] csort(T)(inout T[] arr, int function(T, T) fn_cmp) { ArraySeq!(T).quickSort(arr, 0, arr.length - 1, new class() Comparator!(T){ int compare(T a, T b) { return fn_cmp(a,b) ; } }) ; return arr ; } int cmpLen(char[] a, char[] b) { if (a.length < b.length) return 1 ; // longer string come first else if (a.length > b.length) return -1 ; return 0 ; } int cmpLex(char[] a, char[] b) { return icompare(a,b) ; // case-insensitive compare } int cmpLenThenLex(char[] a, char[] b) { // in case misunderstood the task return cmpLen(a,b) == 0 ? cmpLex(a,b) : cmpLen(a,b) ; } void main() { char[][] d = ["This", "is", "a", "set", "of", "strings", "to", "sort"]; Stdout(d.csort(&cmpLen)).newline ; // descending length char[][] a = ["BbCC","4321","cBBA","Abbc","1234","bBac","baCA","BAcC"] ; Stdout(a.csort(&cmpLex)).newline ; // ascending lexi order char[][] m = ["Bab","abbcc","baacc","Abbc","aAcc","abBac","bba","BAC"] ; Stdout(m.csort(&cmpLenThenLex)).newline ; // descending length then ascending lexi order }
Output:
[ strings, This, sort, set, of, is, to, a ] [ 1234, 4321, Abbc, baCA, BAcC, bBac, BbCC, cBBA ] [ abBac, abbcc, baacc, aAcc, Abbc, Bab, BAC, bba ]
E
/** returns a if it is nonzero, otherwise b() */ def nonzeroOr(a, b) { return if (a.isZero()) { b() } else { a } } ["Here", "are", "some", "sample", "strings", "to", "be", "sorted"] \ .sort(fn a, b { nonzeroOr(b.size().op__cmp(a.size()), fn { a.compareToIgnoreCase(b) }) })
Haskell
import List import Char mycmp s1 s2 = case compare (length s2) (length s1) of EQ -> compare (map toLower s1) (map toLower s2) x -> x strings = ["Here", "are", "some", "sample", "strings", "to", "be", "sorted"] sorted = sortBy mycmp strings
Alternate definition of mycmp
using the Monoid
instance for Ordering
:
import Data.Monoid mycmp s1 s2 = mappend (compare (length s2) (length s1)) (compare (map toLower s1) (map toLower s2))
J
Case-insensitivity is obtained using lower, a verb taken from Change string case. Standard utilities tolower or toupper may be substituted.
mycmp=: 1 :'/:u' length_and_lex =: (-@:# ; lower)&> strings=: 'Here';'are';'some';'sample';'strings';'to';'be';'sorted' length_and_lex mycmp strings +-------+------+------+----+----+---+--+--+ |strings|sample|sorted|Here|some|are|be|to| +-------+------+------+----+----+---+--+--+
Java
import java.util.Comparator; import java.util.Arrays; class MyComparator implements Comparator<String> { // returns -, 0, or +, for less than, equals, greater than, respectively public int compare(String s1, String s2) { if (s1.length() > s2.length()) return -1; else if (s1.length() < s2.length()) return 1; else return s1.compareToIgnoreCase(s2); } } public class Test { public static void main(String[] args) { String[] strings = {"Here", "are", "some", "sample", "strings", "to", "be", "sorted"}; Arrays.sort(strings, new MyComparator()); } }
JavaScript
function lengthSorter(a, b) { var result = b.length - a.length; if (result == 0) result = a.localeCompare(b); return result; } var test = ["Here", "are", "some", "sample", "strings", "to", "be", "sorted"]; test.sort(lengthSorter); alert( test.join(' ') ); // strings sample sorted Here some are be to
MAXScript
fn myCmp str1 str2 = ( case of ( (str1.count < str2.count): 1 (str1.count > str2.count): -1 default:( -- String compare is case sensitive, name compare isn't. Hence... str1 = str1 as name str2 = str2 as name case of ( (str1 > str2): 1 (str1 < str2): -1 default: 0 ) ) ) ) strList = #("Here", "are", "some", "sample", "strings", "to", "be", "sorted") qSort strList myCmp print strList
Nial
sort fork [=[tally first,tally first rest],up,>=[tally first,tally first rest]] ['Here', 'are', 'some', 'sample', 'strings', 'to', 'be', 'sorted'] =|strings|sample|sorted|Here|some|are|be|to|
OCaml
<ocaml>let mycmp s1 s2 =
if String.length s1 <> String.length s2 then compare (String.length s2) (String.length s1) else String.compare (String.lowercase s1) (String.lowercase s2)</ocaml>
List: <ocaml>
- let strings = ["Here"; "are"; "some"; "sample"; "strings"; "to"; "be"; "sorted"];;
val strings : string list =
["Here"; "are"; "some"; "sample"; "strings"; "to"; "be"; "sorted"]
- List.sort mycmp strings;;
- : string list = ["strings"; "sample"; "sorted"; "Here"; "some"; "are"; "be"; "to"] </ocaml>
Array: <ocaml>
- let strings = [|"Here"; "are"; "some"; "sample"; "strings"; "to"; "be"; "sorted"|];;
val strings : string array =
[|"Here"; "are"; "some"; "sample"; "strings"; "to"; "be"; "sorted"|]
- Array.sort mycmp strings;;
- : unit = ()
- strings;;
- : string array = [|"strings"; "sample"; "sorted"; "Here"; "some"; "are"; "be"; "to"|] </ocaml>
Perl
sub mycmp { length $b <=> length $a or lc $a cmp lc $b } @strings = ("Here", "are", "some", "sample", "strings", "to", "be", "sorted"); @sorted = sort mycmp @strings;
PHP
<?php function mycmp($s1, $s2) { if ($d = strlen($s2) - strlen($s1)) return $d; return strcasecmp($s1, $s2); } $strings = array("Here", "are", "some", "sample", "strings", "to", "be", "sorted"); usort($strings, "mycmp"); ?>
Pop11
lvars ls = ['Here' 'are' 'some' 'sample' 'strings' 'to' 'be' 'sorted']; define compare(s1, s2); lvars k = length(s2) - length(s1); if k < 0 then return(true); elseif k > 0 then return(false); else return (alphabefore(uppertolower(s1), uppertolower(s2))); endif; enddefine;
syssort(ls, compare) -> ls;
NOTE: The definition of compare can also be written thus: define compare(s1, s2); lvars l1 = length(s1), l2 = length(s2); l1 > l2 or (l1 == l2 and alphabefore(uppertolower(s1), uppertolower(s2))) enddefine;
Python
In the following we use the key argument to sorted which uses the decorate-sort-undecorate method of transparently replacing the members by the key function of the members of the original list. Use of the key argument is to be preferred in most cases. <python>strings = ["here", "are", "Some", "sample", "strings", "to", "be", "sorted"] print sorted(strings, key=lambda s: (-len(s), s.upper())) </python> In this, we use a cmp (for comparison) function which will be called every time members of the original list are to be compared. <python> def mycmp(s1, s2):
d = len(s2) - len(s1) return d if d else cmp(s1.upper(), s2.upper())
print sorted(strings, cmp=mycmp) </python> Note that for lexicographic secondary ordering the string 'here' comes before 'Some'.
The answer printed in both cases is: <python>['strings', 'sample', 'sorted', 'here', 'Some', 'are', 'be', 'to']</python>
Ruby
Since Ruby 1.8.6 arrays (or any enumerable)have a "sort_by" method.
words = %w(Here are some sample strings to be sorted) puts words.sort_by{|word| word.downcase} puts words.sort_by{|word| word.size}
Smalltalk
#('here' 'are' 'some' 'sample' 'strings' 'to' 'sort' 'since' 'this' 'exercise' 'is' 'not' 'really' 'all' 'that' 'dumb' '(sorry)' ) asSortedCollection sortBlock: [:first :second | (second size = first size) ifFalse: [second size < first size] ifTrue: [first < second]]