Lecture
Sorting algorithm — is an algorithm for arranging the elements in a list in order. When an element of a list has several fields, the field that serves as the ordering criterion is called the sort key. In practice, a number often serves as the key, while the other fields store various data that has no effect on the operation of the algorithm.
The Hollerith tabulator with a "sorting box"
The first prototypes of modern sorting methods already appeared in the 19th century. By 1890, to speed up the processing of US census data, the American Herman Hollerith created the first statistical tabulator — an electromechanical machine designed for the automatic processing of information recorded on punched cards. Hollerith's machine had a special "sorting box" with 26 internal compartments. Operating the machine required the operator to insert a punched card and pull down a lever. Thanks to the holes punched in the card, a certain electrical circuit was closed, and the reading on the associated dial increased by one. At the same time, one of the 26 lids of the sorting box would open, and the punched card would move into the corresponding compartment, after which the lid would close. This machine made it possible to process about 50 cards per minute, which sped up data processing threefold. By the 1900 census, Hollerith had improved the machine, automating the feeding of cards. The operation of Hollerith's sorting machine was based on radix sorting methods. The patent for the machine specifies sorting "separately for each column," but does not define the order. Another similar machine, patented in 1894 by John Gore, mentions sorting starting from the tens column. The method of sorting starting from the units column first appears in the literature in the late 1930s. By that time, sorting machines already made it possible to process up to 400 cards per minute.
EDVAC
Later, the history of algorithms turned out to be linked to the development of electronic computers. According to some sources, it was a sorting program that became the very first program for computing machines. Some computer designers, in particular the developers of EDVAC, called the task of sorting data the most characteristic non-numerical task for computing machines. In 1945, John von Neumann, in order to test a set of instructions for EDVAC, developed merge-sort programs. That same year, the German engineer Konrad Zuse developed a program for sorting by simple insertion. By that time, fast specialized sorting machines had already appeared, and it was against these that the efficiency of the computers being developed was measured. The first published discussion of sorting by means of computing machines was a lecture given by John Mauchly in 1946. Mauchly showed that sorting could also be useful for numerical calculations, and described the methods of simple insertion sort and binary insertion sort, as well as radix sort with partial passes. Later, the company "Eckert–Mauchly Computer Corporation," which he organized together with the engineer John Eckert, released some of the earliest electronic computing machines, BINAC and UNIVAC. Alongside the noted internal sorting algorithms, external sorting algorithms also began to appear, and their development was driven by the limited memory capacity of the first computing machines. In particular, methods of balanced two-way radix sorting and balanced two-way merging were proposed.
By 1952, many internal sorting methods were already being used in practice, but the theory was relatively poorly developed. In October 1952, Daniel Goldenberg presented five sorting methods with an analysis of the best and worst cases for each. In 1954, Harold Seward developed Goldenberg's ideas further and also analyzed methods of external sorting. In 1956, Howard Demuth examined three abstract models of the sorting problem: using cyclic memory, linear memory, and random-access memory. For each of these problems, the author proposed optimal or near-optimal sorting methods, which helped connect theory with practice. Because so few people were involved with computing technology at the time, these reports did not appear in the "open literature." The first major survey article on sorting to appear in print, in 1955, was the work of J. Hosken, in which he described all the special-purpose equipment and computer sorting methods available at the time, drawing on manufacturers' brochures. In 1956, E. Friend analyzed, in his work, the mathematical properties of a large number of internal and external sorting algorithms, proposing several new methods.
After that, many different sorting algorithms were proposed: for example, address calculation sorting in 1956; merge insertion, radix exchange sort, cascade merge sort, and Shell sort in 1959, polyphase merge sort and tree insertion sort in 1960, oscillating sort and Hoare's quicksort in 1962, Williams's heapsort and Batcher's merge exchange sort in 1964. The late 1960s also saw intensive development of sorting theory. Algorithms that appeared later were largely variations of already known methods. Adaptive sorting methods, aimed at faster execution when the input sequence satisfies predetermined criteria, became widespread.
Suppose it is required to order N elements: 
. Each element is a record 
, containing certain information and a key 
that controls the sorting process. On the set of keys an order relation «<» is defined such that for any three key values 
the following conditions hold[10]:
, or 
, or 
; and 
, then 
.These conditions define the mathematical notion of a linear, or total, ordering, and sets satisfying them can be sorted by most methods[10].
The task of sorting is to find a permutation of the records 
with indices 
, after which the keys would be arranged in non-decreasing order[10]:
A sort is called stable if it does not change the relative order of elements with equal keys[10]:
for any 
and }
.
Sorting methods can be divided into internal and external. Internal sorting is used for data that fits into main memory, which makes it more flexible in terms of data structures. External sorting is applied when the data does not fit into main memory, and it is oriented toward achieving a result under conditions of limited resources[11].
Sorting algorithms are evaluated by their execution speed and their efficiency in the use of memory:
in the general caseIn the general case, the sorting problem assumes that the only operation guaranteed to be available on elements is comparison. The answer to comparing elements 
and 
can be one of two options: 
or . Therefore, if in the course of its work the algorithm makes 
comparisons, then a total of }
combinations of answers to them are possible.
The number of permutations of 
elements equals 
. In order for it to be possible to construct a surjection from the set of combinations of answers onto the set of all permutations, the number of comparisons must be no less than 
(since comparison is the only permitted operation).
By taking the logarithm of Stirling's formula, one can discover that 
[12]
( 
), but they differ in flexibility of application. For special cases (data types) there are more efficient algorithms.Another important property of an algorithm is its scope of application. There are two main types of ordering here:
Algorithms are also classified by:
Classification of sorting algorithms
In this table is the number of records to be ordered, and is the number of unique keys.
...; the recursive version additionally requires of memory.
. Requires 
of additional memory. in the best case, and in the worst. Requires of additional memory.. Requires of additional memory. Developed for use in the Python language[14]..; an improvement on bubble sort.
or 
.
; turns the list into a heap, takes the largest element and adds it to the end of the list.. — average time, — worst case; widely known as the fastest of the known algorithms for ordering large random lists; the original data set is split into two halves so that any element of the first half is ordered relative to any element of the second half; the algorithm is then applied recursively to each half. Using of additional memory, the sort can be made stable., a combination of quicksort and heapsort. Heapsort is used when the recursion depth exceeds 
. — worst case, additionally requires of memory, and also finds the longest increasing subsequence.
.
on average. Randomly shuffle the array, check the order.
— worst-case time. For each pair, the correct order is checked, and every possible permutation of the original array is generated. or 
, requires specialized hardware., requires specialized hardware.
of additional memory and knowledge of the nature of the data being sorted, going beyond the «rearrange» and «compare» functions. Algorithm complexity: {\displaystyle O(n)}.
; requires of additional memory.
. Requires of additional memory.
Efficiency of sorting algorithms
One of the most frequent applications of sorting algorithms is the sorting of strings. This is usually done as follows: first the set of strings is sorted by the first character of each string, then each subset of strings having the same first character is sorted by the second character, and so on until all the strings are ordered. In this case, a missing character (when comparing a string of length N with a string of length N+1) is considered smaller than any character.
Applying this method to strings that represent numbers in their natural written form produces counterintuitive results: for example, «9» turns out to be greater than «11», since the first character of the first string has a greater value than the first character of the second. To fix this problem, a sorting algorithm can convert the strings being sorted into numbers and sort them as numbers. Such an algorithm is called «numeric sorting», while the one described earlier is called «string sorting». Likewise, in practice an effective way to solve the problem of sorting strings containing numbers is to add a certain number of zeros before the number, so that «011» would be considered greater than «009» because of the zeros.
Comments