Sort stability: Difference between revisions
(New task and Python solution.) |
(added a bunch) |
||
| Line 8: | Line 8: | ||
UK Birmingham</pre> |
UK Birmingham</pre> |
||
The task is to '''examine the documentation on any in-built sort routines supplied by a language and indicate if an in-built routine is supplied, and if supplied, whether it is stable or not'''. (This [[wp:Stable_sort#Comparison_of_algorithms|Wikipedia table]] shows the stability of some common sort routines). |
The task is to '''examine the documentation on any in-built sort routines supplied by a language and indicate if an in-built routine is supplied, and if supplied, whether it is stable or not'''. (This [[wp:Stable_sort#Comparison_of_algorithms|Wikipedia table]] shows the stability of some common sort routines). |
||
=={{header|C++}}== |
|||
C++ standard library's [http://www.sgi.com/tech/stl/sort.html std::sort()] function is not guaranteed stable. The stable analog of it is the [http://www.sgi.com/tech/stl/stable_sort.html std::stable_sort()] function. In addition, [http://www.sgi.com/tech/stl/List.html std::list]'s <tt>sort()</tt> method is guaranteed stable. |
|||
=={{header|Haskell}}== |
|||
Haskell's <tt>sort</tt> and <tt>sortBy</tt> functions are guaranteed stable.[http://www.haskell.org/onlinereport/list.html#sect17.3] |
|||
=={{header|Java}}== |
|||
Java's [http://java.sun.com/javase/6/docs/api/java/util/Collections.html#sort(java.util.List) Collections.sort()] and [http://java.sun.com/javase/6/docs/api/java/util/Arrays.html#sort(java.lang.Object%5B%5D) Arrays.sort()] methods are guaranteed stable. |
|||
=={{header|OCaml}}== |
|||
OCaml's [http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALsort List.sort] and [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html#VALsort Array.sort] functions are not guaranteed to be stable. The stable versions are [http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALstable_sort List.stable_sort] and [http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html#VALstable_sort Array.stable_sort], respectively. |
|||
=={{header|Perl}}== |
|||
The stability of Perl's in-built [http://perldoc.perl.org/functions/sort.html sort] function is version-dependent. If you want to guarantee a stable sort from it, you should use the following [http://perldoc.perl.org/sort.html sort pragma]: |
|||
<lang perl>use sort 'stable';</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
Python's in-built [http://docs.python.org/library/functions.html#sorted sorted] function as well as the [http://docs.python.org/library/stdtypes.html#mutable-sequence-types sort method of lists] are guaranteed stable (since version 2.3). |
|||
Revision as of 09:49, 6 June 2009
You are encouraged to solve this task according to the task description, using any language you may know.
When sorting records in a table by a particular column or field, a stable sort will always retain the relative order of records that have the same key.
For example, in this table of countries and cities, a stable sort on the second column, the cities, would keep the US Birmingham above the UK Birmingham. (Although an unstable sort might, in this case, place the US Birmingham above the UK Birmingham, a stable sort routine would guarantee it).
UK London US New York US Birmingham UK Birmingham
The task is to examine the documentation on any in-built sort routines supplied by a language and indicate if an in-built routine is supplied, and if supplied, whether it is stable or not. (This Wikipedia table shows the stability of some common sort routines).
C++
C++ standard library's std::sort() function is not guaranteed stable. The stable analog of it is the std::stable_sort() function. In addition, std::list's sort() method is guaranteed stable.
Haskell
Haskell's sort and sortBy functions are guaranteed stable.[1]
Java
Java's Collections.sort() and Arrays.sort() methods are guaranteed stable.
OCaml
OCaml's List.sort and Array.sort functions are not guaranteed to be stable. The stable versions are List.stable_sort and Array.stable_sort, respectively.
Perl
The stability of Perl's in-built sort function is version-dependent. If you want to guarantee a stable sort from it, you should use the following sort pragma: <lang perl>use sort 'stable';</lang>
Python
Python's in-built sorted function as well as the sort method of lists are guaranteed stable (since version 2.3).