views:

4148

answers:

20

I thought I would pose a question I'm describing as a "Rosetta Stone". That is to say, I am posing a question, and would like to see answers given for a number of different languages so that someone moving from one language to another can see how some typical operation is done. I have always found these types of comparisons to be very educational when moving into a new language, and a fun quick way to see differences between languages without having to use them heavily for a while.

This particular question is, given an array of items in the typical collection appropriate to the language at hand, how do you sort them? Sample code with some description would be good.

I'll present the Objective C answer:

// Can only modify mutable arrays
NSMutableArray *sortArray = [NSMutableArray arrayWithArray:myArrayOfStuff];

Sort NSString ignoring case:

[sortArray sortUsingSelector: @selector(caseInsensitiveCompare:)];

Sort most foundation objects (would also work for NSString as well), assuming numbers are wrapped in NSNumber class:

[sortArray sortUsingSelector:@selector(compare:)];

Sort instances of your own classes:

[sortArray sortUsingSelector:@selector(myCompare:)];

For the last one, in your class you'd implement a comparison method like so:

// Class instance method to compare self with object "obj"
- (NSComparisonResult) myCompare:(myObject *)obj
{
    NSComparisonResult retVal = NSOrderedSame;
    if ( self < obj ) // by whatever rules make sense for your class of course
      retVal = NSOrderedAscending;
    else if ( self > obj ) 
      retVal = NSOrderedDescending;
    return retVal;
}
+2  A: 

C++:

// a container this might work on
std::vector<std::string> container;

// uses default operator< for objects in the container
std::sort(container.begin(), container.end());

// uses a custom comparison
std::sort(container.begin(), container.end(), less<container::value_type>());

// stable sort, maintains ordering for otherwise equal objects
std::stable_sort(container.begin(), container.end());

// partial sort only sorts the first N objects
// this is more efficient for doing "top N" type calculations
std::partial_sort(container.begin(), container.begin()+N, container.end());
1800 INFORMATION
+3  A: 

Java:

// Simple arrays
int[] numbers;
Arrays.sort(numbers);

// Still pretty simple Lists
List<E> list;
Collections.sort(list);
Collections.sort(list, yourComparator<E>);
jjnguy
+3  A: 

Python:

There's a HowTo/Sorting page in the Python wiki where you can learn all of this.

# These all apply to the standard list type
myList = ["One", "Two", "Three", "Four"]

# To sort a list in-place
myList.sort()

# To get a sorted copy of a list
sortedList = sorted(myList)

# To sort using keys derived from the items
# For example, case-insensitive sorting
myList.sort(key=str.lower)

sortedList = sorted(myList, key=str.lower)

# You can also use comparison functions, which return:
#   a negative number if the first term comes second
#                zero if the terms sort equlivilently
#   a positive number if the first term comes first
# You specify the function like this:
myList.sort(comparisonFunction)

sortedList = sorted(myList, comparisionFunction)

# They can also accept the reversed parameter,
# which, as you'd expect, reverses the sorted order.
myList.sort(lambda a, b: cmp(a.name, b.name), reverse=True)
sortedList = sorted(myList, lambda a, b: cmp(a.name, b.name), reverse=True)

# If you've defined comparison methods for your class,
# the sorting method and function will work without any
# additional work required.

The comparison methods are explained in the manual, they're obviously very simple.

Jeremy Banks
It's probably work adding sorting using lambda functions and an example using the reverse option.
Dave Webb
Replace `myList.sort(lambda a, b: cmp(a->name, b->name), reverse=True)` by `mylist.sort(key=operator.attrgetter('name'), reverse=True)`. BTW `a->name` is not correct syntax (should be `a.name`)
J.F. Sebastian
Sorry. Was very tired, not thinking very well.I'd like to leave the lambda in, even if it's a bad example, because I don't have another example of using a comparison function. If you have a suggestion I'll gladly replace it.
Jeremy Banks
+4  A: 

PHP:

sort($array); // Normal sort
asort($array); // Sort and don't change the indices of the values
ksort($array); // Sort by key rather than value
rsort($array); // Sort in reverse order
usort($array, 'cmp'); // Sort using user-defined comparison function
natsort($array); // Sort an array in "natural order" (eg. 1, 2, 10, 20
                 // instead of 1, 10, 2, 20)

// Comparison function used by usort()
function cmp($a, $b) {
    if ($a == $b) {
        return 0;
    } else if ($a < $b) {
        return -1;
    } else {
        return 1;
    }
}
yjerem
+4  A: 

Ruby:

list = ["some", "list", "to", "sort"]

list.sort!                    # Sorts using default <=> method
list.sort! { |x, y| x <=> y } # custom block to sort any way you want
list.sort_by { |k| k.downcase } # sort using Schwartzian Transform
Mike Stone
A: 

This isn't the real answer, because Windows (2k/XP/+) BATCH scripts don't really have arrays. On the other hand, it does, kind of, sort the array.

@echo off
call :sort %*
exit /B 0

:sort
    set swaps=0
    set sorted=
    if $%1$ == $$ goto :sort_loop_end
    set var1=%1
    shift
    :sort_loop
        if $%1$ == $$ goto :sort_loop_end
        set var2=%var1%
        set var1=%1
        shift
        set varT=%var1%
        if /I %var1% LSS %var2% (
            set var1=%var2%
            set var2=%varT%
            set /A swaps=swaps+1
        )
        set sorted=%sorted% %var2%
        goto sort_loop
    :sort_loop_end
    set sorted=%sorted% %var1%
    if /I %swaps% GTR 0 (
        rem echo %swaps% : %sorted%
        call :sort %sorted%
    ) else (
        echo %sorted%
    )
exit /B 0

PS: I originally posted this script as a comment to an article on The Code Project, but because I'm the original author, I guess it's OK to repost it here. ;)

Paulius Maruška
+2  A: 

C# using Linq (.NET 3.5)

string[] names = { "Tom", "Dick", "Harry" };    

var sorted = from n in names orderby n ascending select n;

// Or for more flexibility using a Lambda query use:
var sorted = names.OrderBy(n=> n,StringComparer.OrdinalIgnoreCase);

Note: StringComparer.OrdinalIgnoreCase could be any class that implements IComparer)

Ash
+1  A: 

Smalltalk:

#(1 3 2) sort
>  #(1 2 3)

#(1 3 2) sortBy: [:lhs :rhs | lhs > rhs]
>  an OrderedCollection(3 2 1)
Sébastien RoccaSerra
+1  A: 

Delphi:

TArray.Sort<TExample>(SomeVar , TDelegatedComparer<TExample>.Construct(
function(const Left, Right: TExample): Integer
begin
  Result := TComparer<Integer>.Default.Compare(Left.SortOrder, Right.SortOrder);
end));

This is for Delphi 2009 for Win32, the latest version that includes generics and anonymous methods. Source.

Jim McKeeth
+1  A: 

Groovy:

def array = [1, 4, 5, 2, 3, 7, 9, 6, 8, 0]
array.sort() // normal sorting
array.sort { a, b -> b <=> a } // desc sorting

Kind Regards

marcospereira
+2  A: 

JavaScript:

[1, 4, 5, 2, 3, 7, 9, 6, 8, 0].sort(); // asc sorting
[1, 4, 5, 2, 3, 7, 9, 6, 8, 0].sort(function(a, b) { return b -a }); // using a callback function

Kind Regards

marcospereira
+1  A: 

ANSI C:

#include <stdlib.h>

int int_compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int str_compare (const void * a, const void * b)
{
  return strcmp(*(const char **)a, *(const char **)b);
}

int main(){
  // sort integers
  {
    int int_values[] = { 1, 4, 5, 2, 3, 7, 9, 6, 8, 0 };
    qsort (int_values, 10, sizeof(int), int_compare);    
  }
  // sort strings
  {
    const char* str_values[] = { "foo", "bar", "foobar" };
    qsort (str_values, 3, sizeof(char*), str_compare);
    // strcmp cannot be used directly since qsort will hand the compare function
    // pointers to the char*s and strcmp expects to be handed the char*s directly.
  } 

  return 0;
}
Rasmus Faber
Think you can remove the str_compare() function and use strcmp() directly in the qsort() call.
epatel
+14  A: 

There are plenty of sites which were created for that purpose, e.g. http://rosettacode.org

Sorting Using a Custom Comparator. There are examples in Ada, C, C++, Clean, Common Lisp, D, E, Haskell, J, Java, JavaScript, MAXScript, OCaml, Perl, PHP, Pop11, Python, Ruby, Smalltalk.

It contains code in 109 languages.

J.F. Sebastian
Ah, but no Objective C.A very interesting resource and one I had not seen before. But I have to say that if I were searching for such a thing myself I would prefer the results gathered here to the code presented there, as being more concise and having less clutter to parse through when reading.
Kendall Helmstetter Gelner
+1  A: 

F# - using the .NET library sort, so not really using any of the functional features.

#light

open System
let asc a b = (a-b)
let values = [| 1; 4; 5; 2; 3; 7; 9; 6; 8; 0 |]
values |> Array.sort asc
values |> Array.iter (fun x -> Printf.printf "%d " x)

Also see this post for some actual sort implementations in F#: http://cs.hubfs.net/forums/thread/3876.aspx

Rasmus Faber
A: 

perl 5

@array = (1, 4, 5, 2, 3, 7, 9, 6, 8, 0);
@sorted            = sort               @array;
@sorted_descending = sort { $b <=> $a } @array;

There is more than one way to do it, obviously...

Tobias Kunze
+1  A: 

K:

Here is an answer for K, a vector language descended from APL.

n:20 _draw -20   / generate 20 random numbers between 0 and 19, without repeats (negative indicates no repeats)
indices:<n       / sort n, yielding the indices that would yield sort
n[indices]       / index n at the sorted indices yields n sorted

Example:

 n:20 _draw -20   / generate 20 random numbers between 0 and 19, without repea
ts (negative indicates no repeats)
 n
17 10 19 2 11 1 8 15 18 12 9 5 16 7 4 13 3 14 0 6
 indices:<n / do the sort
 indices    / display on console
18 5 3 16 14 11 19 13 6 10 1 4 9 15 17 7 12 0 8 2
 n[indices] / display on console
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Of course, n[<n] will work just as well.

Why the indices instead of the values directly? Consider tables with related columns, firstName and lastName. Sorting to the indices of lastName allows you to index firstName matching lastName.

+1  A: 

Mathematica:

Sort[{2,1,3}, #1<#2&]

returns

{1,2,3}

The optional second argument is a function taking two elements and returning whether they're in order.

There's also something like Python's "keys" to sort by some function of the elements:

SortBy[{"apple", "cat", "Ball"}, ToLowerCase]

will do a case-insensitive sort.

dreeves
A: 

Unfortunately I am not able to add comments with my reputation, therefore I'll add my suggestion to the Objective-C method here:

Since you are comparing NSNumber or NSString most of the time you can use their build in "compare" method for more convenience

// Class instance method to compare self with object "obj"
- (NSComparisonResult)myCompare:(myObject *)obj {
  // assuming "someNonVoidMethod" is returning either NSNumber or NSString
  return [self.someNonVoidMethod compare:obj.someNonVoidMethod];
}
carnz
A: 

Clojure

Strings:

(sort ["ac" "9" "z" "a9"])

results in: ("9" "a9" "ac" "z")

Also works with numbers:

(sort [9 42 3 4.7])

results in: (3 4.7 9 42)

Mixing the two, however, will throw errors:

(sort ["a" 9])

java.lang.RuntimeException: java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String (NO_SOURCE_FILE:0)

In such cases, sort accepts an optional comparator for you to define your own comparison function. Details:

(doc sort)
-------------------------
clojure.core/sort
([coll] [comp coll])
  Returns a sorted sequence of the items in coll. If no comparator is
  supplied, uses compare. comparator must
  implement java.util.Comparator.
nilamo
A: 

Scala

object Main{
  def main(argv: Array[String]) = {
    val list = List(45, 23, 9, 86, 32)
    println( list sort (_ > _) )
  }
}

Output :

List(86, 45, 32, 23, 9)

missingfaktor