Sorting: Difference between revisions
(→[[C plus plus|C++]]: Additions for deque and list; improved stable_sort example to actually demonstrate the point) |
m (Split a long paragraph.) |
||
(63 intermediate revisions by 19 users not shown) | |||
Line 1: | Line 1: | ||
{{Sorting Algorithm}} |
|||
{{task}} |
|||
[[Category:Encyclopedia]] |
|||
'''Sorting''' is a way of arranging a group of things in a specified order. Normally, the order is a "natural order." Examples of natural orders are counting order or alphabetical order. |
|||
Sort an Array of Strings, from large to small and lexicographic for Strings of equal length |
|||
In computing, time and memory usage are of concern when sorting. Some algorithms are very fast, but use a lot of memory, or vice versa. Usually, speed has higher priority. |
|||
==[[Perl]]== |
|||
'''Interpeter:''' Perl |
|||
The speed of an algorithm is often determined by the number of compares and/or swaps required. This is denoted as its "order" and is shown in [[Big O]] notation. |
|||
===Numeric sort=== |
|||
my @sorted = sort {$a<=>$b} (3, 6, 4, 5, 2, 7, 1); |
|||
For example, a [[Quicksort]] is usually noted for being of "order n log n" (where n is the size of the group). This shown in Big O notation as "O(''n log(n)'')." |
|||
===Alpha-Numeric sort=== |
|||
my @sorted = sort ('this', 'that', 'and', 'the', 'other'); |
|||
Sorting algorithms often have different orders depending on characteristics of the group being sorted. |
|||
Numeric sort or Alpha-Numeric sort if a numeric sort cannot be done |
|||
For example, the Quicksort will perform at O(''n^2'') when the group is already ordered. A sort which "swaps" elements within the group is called an "in-place sort." A sort which moves elements to another group, destroys, or simply ignores the original group is sometimes called an "out-of-place sort" or a "not-in-place sort." An example of an out-of-place sort is the [http://en.wikipedia.org/wiki/Counting_sort counting sort]. |
|||
# note, this can be a oneliner |
|||
my @sorted = sort { |
|||
($a =~ /^\-?\d+\.?\d*$/ and $b =~ /^\-?\d+\.?\d*$/) ? $a <=> $b : $a cmp $b |
|||
} ('this', 'that', 'and', 'the', 'other', 3, 6, 4, 5, 2, 7, 1); |
|||
For complete implementations of various sorting algorithms, see [[:Category:Sorting Algorithms]]. |
|||
==[[Python]]== |
|||
For examples of how to use sorting functionality provided by a language, see: |
|||
'''Interpreter:''' Python 2.4 |
|||
* [[Sort an array of composite structures]] |
|||
* [[Sorting an Array of Integers]] |
|||
Python's lists have a method for in-place sorting; there's also a built-in |
|||
* [[Sorting Using a Custom Comparator]] |
|||
<tt>sorted()</tt> method that can sort any iterable. |
|||
<!-- NOTE: a single sorted(words, key=len, reverse=True) won't produce the |
|||
desired results for strings of equal length --> |
|||
# create a sample list |
|||
words = ['Long', 'words', 'are', 'more', 'interesting', 'than', 'short', 'ones'] |
|||
# order it and keep the result on another variable |
|||
sorted_words = sorted(words, key=lambda word: (-len(word), word)) |
|||
# result: ['interesting', 'short', 'words', 'Long', 'more', 'ones', 'than', 'are'] |
|||
# otherwise |
|||
words.sort(key=lambda word: (-len(word), word)) |
|||
==[[Ruby]]== |
|||
#create a test array |
|||
ary=['Long','words','are','more','interesting','than','short','ones'] |
|||
ary.sort_by {|a| [-a.size,a]} |
|||
# => ["interesting", "short", "words", "Long", "more", "ones", "than", "are"] |
|||
==[[UNIX Shell]]== |
|||
words='Long words are more interesting than short ones' |
|||
sorted_words="$( |
|||
for word in $words # doesn't work with ZSH since it won't do field splitting here |
|||
do echo "$word" |
|||
done | sort | \ |
|||
while read word |
|||
do echo -n "$word " |
|||
done |
|||
echo |
|||
)" |
|||
echo "$sorted_words" |
|||
==[[C plus plus|C++]]== |
|||
sort an array |
|||
#include <algorithm> |
|||
int arr[] = { 3, 8, 5, 2, 9 }; |
|||
int arr_length = sizeof(arr)/sizeof(arr[0]); |
|||
std::sort(arr, arr+arr_length); |
|||
sort a std-vector (this also works with std deque) |
|||
#include <algorithm> |
|||
#include <vector> |
|||
std::vector<int> vec; |
|||
vec.push_back(5); |
|||
vec.push_back(4); |
|||
vec.push_back(7); |
|||
vec.push_back(1); |
|||
std::sort(vec.begin(), vec.end()); |
|||
Sort a std list |
|||
#include <list> |
|||
std::list<int> intlist; |
|||
intlist.push_back(5); |
|||
intlist.push_back(4); |
|||
intlist.push_back(7); |
|||
intlist.push_back(1); |
|||
intlist.sort(); |
|||
Sort an array in a custom way with a function. |
|||
This also works on std-vectors and std deques. |
|||
Note: of course the function is_bigger should be outside our function. |
|||
#include <algorithm> |
|||
bool is_bigger(int a, int b) |
|||
{ |
|||
// note: for equal elements it should return false |
|||
return a>b; |
|||
} |
|||
std::sort(arr, arr+arr_length, is_bigger); |
|||
Sort a list in a custom way with a function. |
|||
#include <list> |
|||
bool is_greater(int a, int b) { return a > b; } |
|||
int values[6] = { 11, 32, 53, 64, 45, 26 }; |
|||
std::list<int> intlist(values, values+6); |
|||
intlist.sort(is_greater); |
|||
Sort an array in a custom way with a function object. |
|||
This has the advantage that you can give a state to the sorting object. |
|||
This also works on std-vectors. |
|||
Note: the struct compare_modulo should be outside our function. |
|||
#include <algorithm> |
|||
struct compare_modulo |
|||
{ |
|||
int mod; |
|||
compare_modulo(int m): mod(m) {} |
|||
bool operator()(int a, int b) const |
|||
{ |
|||
// note: for equal elements it should return false |
|||
return (a%mod)<(b%mod); |
|||
} |
|||
} |
|||
std::sort(arr, arr+arr_length, compare_modulo(3)); |
|||
Sort an array in a custom way with standard-supplied function objects |
|||
#include <algorithm> |
|||
#include <functional> |
|||
int arr[6] = { 2, 3, 7, 5, 13, 11 }; |
|||
std::sort(arr, arr+6, std::greater<int>()); |
|||
Sort an array in a stable way. This is different from the other sort in that equal elements stay in the same order as they were before sorting. This is a little slower. This has no use on int's of course, but it may be important with objects. You can also use this with std-vectors, and there is also a version that takes a third argument as the compare object, as above with std::sort. It can be demonstrated on ints with a custom sort function. |
|||
#include <algorithm> |
|||
bool has_smaller_trailing_digit(int i, int j) { return i%10 < j%10; } |
|||
int arr[] = { 13, 22, 39, 42, 59 }; |
|||
int arr_length = sizeof(arr)/sizeof(arr[0]); |
|||
std::stable_sort(arr, arr+arr_length, has_smaller_trailing_digit); |
|||
This gives the order |
|||
22, 42, 13, 39, 59 |
|||
that is, the trailing digits are in ascending order (that's what the custom function says), but the order did not change otherwise (e.g. 22 still comes before 42). An unstable sort could e.g. have given the result |
|||
42, 22, 13, 39, 59 |
|||
which also has increasing trailing digits, but otherwise the order is arbitrary. |
Latest revision as of 08:31, 15 July 2020
Sorting Algorithm
This is a sorting algorithm. It may be applied to a set of data in order to sort it.
For comparing various sorts, see compare sorts.
For other sorting algorithms, see sorting algorithms, or:
Heap sort | Merge sort | Patience sort | Quick sort
O(n log2n) sorts
Shell Sort
O(n2) sorts
Bubble sort |
Cocktail sort |
Cocktail sort with shifting bounds |
Comb sort |
Cycle sort |
Gnome sort |
Insertion sort |
Selection sort |
Strand sort
other sorts
Bead sort |
Bogo sort |
Common sorted list |
Composite structures sort |
Custom comparator sort |
Counting sort |
Disjoint sublist sort |
External sort |
Jort sort |
Lexicographical sort |
Natural sorting |
Order by pair comparisons |
Order disjoint list items |
Order two numerical lists |
Object identifier (OID) sort |
Pancake sort |
Quickselect |
Permutation sort |
Radix sort |
Ranking methods |
Remove duplicate elements |
Sleep sort |
Stooge sort |
[Sort letters of a string] |
Three variable sort |
Topological sort |
Tree sort
Sorting is a way of arranging a group of things in a specified order. Normally, the order is a "natural order." Examples of natural orders are counting order or alphabetical order.
In computing, time and memory usage are of concern when sorting. Some algorithms are very fast, but use a lot of memory, or vice versa. Usually, speed has higher priority.
The speed of an algorithm is often determined by the number of compares and/or swaps required. This is denoted as its "order" and is shown in Big O notation.
For example, a Quicksort is usually noted for being of "order n log n" (where n is the size of the group). This shown in Big O notation as "O(n log(n))."
Sorting algorithms often have different orders depending on characteristics of the group being sorted.
For example, the Quicksort will perform at O(n^2) when the group is already ordered. A sort which "swaps" elements within the group is called an "in-place sort." A sort which moves elements to another group, destroys, or simply ignores the original group is sometimes called an "out-of-place sort" or a "not-in-place sort." An example of an out-of-place sort is the counting sort.
For complete implementations of various sorting algorithms, see Category:Sorting Algorithms.
For examples of how to use sorting functionality provided by a language, see: