Rosetta Stone - Sorting Arrays

Question

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;
}

Answer 1

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());

Answer 2

Java:

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

// Still pretty simple Lists
List<E> list;
Collections.sort(list);
Collections.sort(list, yourComparator<E>);

Answer 3

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.

Answer 4

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;
    }
}

Answer 5

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

Answer 6

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

Answer 7

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)

Answer 8

Smalltalk:

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

#(1 3 2) sortBy: [:lhs :rhs | lhs > rhs]
>  an OrderedCollection(3 2 1)

Answer 9

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.

Answer 10

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

Answer 11

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

Answer 12

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;
}

Answer 13

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.

Answer 14

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

Answer 15

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

Answer 16

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.

Answer 17

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.

Answer 18

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];
}

Answer 19

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.

Answer 20

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)