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]].
+For examples of how to use sorting functionality provided by a language, see:
-==[[Ruby]]==
+* [[Sort an array of composite structures]]
-  #create a test array
+* [[Sorting an Array of Integers]]
-  ary=['Long','words','are','more','interesting','than','short','ones']
+* [[Sorting Using a Custom Comparator]]
-  ary.sort do |wx,wy|
-    if wx.length==wy.length
-      wx <=> wy
-    else
-      wy.length <=> wx.length
-    end
-  end
-  # => ["interesting", "short", "words", "Long", "more", "ones", "than", "are"]