Sorting algorithm

Sorting algorithm . In computation and mathematics an ordering algorithm is an algorithm that puts elements of a list or a vector in a sequence given by an order relation, that is, the output result must be a permutation – or rearrangement – of the input that satisfy the given order relationship. The most used order relationships are the numerical order and the lexicographic order. Efficient ordering is important for optimizing the use of other algorithms (such as search and merge) that require ordered lists for fast execution. It is also useful for putting data into canonical form and for generating human readable results.

Since the beginning of computing, the problem of ordering has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple and familiar approach. For example, BubbleSort has been analyzed since 1956. [1] Although many may consider it a solved problem, new and useful sorting algorithms are still invented to this day (for example, the library sort was first published in 2004). Ordering algorithms are common in introductory classes in computing, where the abundance of algorithms for the problem provides a gentle introduction to the variety of algorithm core concepts, such as capital O notation, divide-and-conquer algorithms, data structures , worst, best, and average case analysis, and lower limits.

Summary

[ hide ]

  • 1 Classification
  • 2 Stability
  • 3 List of sorting algorithms
  • 4 See also
  • 5 References
  • 6 Sources

Classification

The ordering algorithms can be classified in the following ways:

  1. The most common is to classify according to the place where the ordination is carried out
  • Algorithms of internal ordering: in the memory of the computer.
  • External ordering algorithms: in an external location such as a hard drive.
  1. For the time it takes to make the order, given already ordered entries or inversely ordered:
  • Natural sorting algorithms: Takes as little time as possible when the input is sorted.
  • Unnatural ordering algorithms: Takes as little time as possible when the input is inversely ordered.
  1. For stability: a stable ordering maintains the relative order that elements with the same keys originally had. For example, if a list sorted by date is rearranged in alphabetical order with a stable algorithm, all items whose alphabetic key is the same will be in date order. Another case would be when the case is not interesting, but it is wanted that if a key aBC was before AbC, in the result both keys appear together and in the original order: aBC, AbC. When the elements are indistinguishable (because each element is ordered by the complete key), stability does not matter. Sorting algorithms that are not stable can be implemented so that they are.

The algorithms are distinguished by the following characteristics:

  • Computational complexity(worst case, average case, and best case) in terms of n, the size of the list or array. For this the concept of order of a function is used and the notation O (n) is used. The best sorting behavior (if key structure is not exploited) is O (n log n). The simplest algorithms are quadratic, that is, O (n²). Algorithms that take advantage of the structure of sort keys (eg bucket sort) can sort on O (kn) where k is the size of the key space. As this size is known a priori, it can be said that these algorithms have a linear performance, that is, O (n).
  • Use of memory and other computational resources. The O (n) notation is also used.

Stability

Stable ordering algorithms maintain a relative total preorder. This means that an algorithm is stable only when there are two R and S records with the same key and with R appearing before S in the original list.

When equal elements (indistinguishable from each other), such as integers, or more generally, any data type where the integer element is the key, stability is not an issue. However, it is assumed that the following pairs of numbers are about to be ordered by their first component:

(4, 1) (3, 7) (3, 1) (5, 6)

In this case, two different results are possible, one of which maintains a relative order of records with equal keys, and one in which it does not:

(3, 7) (3, 1) (4, 1) (5, 6) (order maintained).

(3, 1) (3, 7) (4, 1) (5, 6) (order changed).

Unstable ordering algorithms can change the relative order of records with equal keys, but stable algorithms never do. Unstable algorithms can be specially implemented to be stable. One way to do this is to artificially extend key matching, so that comparisons between two objects with equal keys are decided using the original input order. Remembering this order between two objects with the same keys is an impractical solution, since it generally entails having additional storage.

Sorting according to a primary, secondary, tertiary key, etc., can be done using any sorting method, taking all keys into consideration (in other words, using a single compound key). If a sort method is stable, it is possible to sort multiple items, each time with a different key. In this case, the keys need to be applied in order to increase the priority. Example: order pairs of numbers, using both values.

(4, 1) (3, 7) (3, 1) (4, 6) (original)

(4, 1) (3, 1) (4, 6) (3, 7) (after being ordered by the second value)

(3, 1) (3, 7) (4, 1) (4, 6) (after being ordered by the first value)

On the other hand: (3, 7) (3, 1) (4, 1) (4, 6) (after being ordered by the first value)

(3, 1) (4, 1) (4, 6) (3, 7) (after being ordered by the second value, the order by the first value is disturbed)

List of sorting algorithms

Some sorting algorithms grouped according to stability taking into account computational complexity .

Stable
Translated name Original name Complexity Memory Method
Bubble Sort Bubblesort O ( n ²) O (1) Exchange
Bidirectional bubble sorting Cocktail sort O ( n ²) O (1) Exchange
Insertion Ordering Insertion sort O ( n ²) O (1) Insertion
Sorting by lockers Bucket sort O ( n ) O ( n ) Not comparative
Sorting by accounts Counting sort O ( n + k ) O ( n + k ) Not comparative
Mix ordering Merge sort O ( n log n ) O ( n ) Mixture
Sorting with binary tree Binary tree sort O ( n log n ) O ( n ) Insertion
Pigeonhole sort O ( n + k ) O ( k )
Radix ordering Radix sort O ( nk ) O ( n ) Not comparative
Distribution sort O ( n ³) recursive version O ( n ²)
Gnome sort O ( n ²)
Unstable
Translated name Original name Complexity Memory Method
Shell Sorting Shell sort O ( 1.25 ) O (1) Insertion
Comb sort O ( n log n ) O (1) Exchange
Sorting by selection Selection sort O ( n ²) O (1) Selection
Mounding Heapsort O ( n log n ) O (1) Selection
Smoothsort O ( n log n ) O (1) Selection
Quick ordering Quicksort Average: O ( n log n ),
worst case: O ( n ²)
O (log n ) Partition
Several Unique Sort Average: O ( n u),
worst case: O ( n ²);
u = n; u = unique number of records
Questionable, impractical
Translated name Original name Complexity Memory Method
Bogosort O ( n × n !), Worse: does not end
Pancake sorting O ( n ), except on Von Neumann
machines
Randomsort

 

by Abdullah Sam
I’m a teacher, researcher and writer. I write about study subjects to improve the learning of college and university students. I write top Quality study notes Mostly, Tech, Games, Education, And Solutions/Tips and Tricks. I am a person who helps students to acquire knowledge, competence or virtue.

Leave a Comment