Sorting: Difference between revisions
(→[[C plus plus|C++]]: Sorting std list) |
m (Split a long paragraph.) |
||
(64 intermediate revisions by 20 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. |
|||
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 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 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. |
|||
#include <algorithm> |
|||
int arr[] = { 3, 2, 9, 2, 9 }; |
|||
int arr_length = sizeof(arr)/sizeof(arr[0]); |
|||
std::stable_sort(arr, arr+arr_length); |
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: