Sorting: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 08:31, 15 July 2020

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:

@@ 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.5
+* [[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 <tt>sorted()</tt> method that
+* [[Sorting Using a Custom Comparator]]
-can sort any iterable.
- # 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))
- # sorted_words: ['interesting', 'short', 'words', 'Long', 'more', 'ones', 'than', 'are']
-==[[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
-  #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 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);