Algorithm of the sorting algorithm algorithm ideas and use of the scene summary

1. An overview of the

Sorting algorithm is the most basic algorithm in computer technology, many complex algorithms will use sorting. Although sorting algorithms have been packaged as library functions for programmers to use, it is important to understand the ideas and principles of sorting algorithms for writing high-quality software.

This paper introduces the common sorting algorithm, and summarizes the algorithm idea, complexity and usage scenarios.

2. A few concepts

(1) stable sorting: if two Numbers are the same, the result of sorting them is that their relative order is unchanged. So, for example, A={1,2,1,2,1} and then after sorting, A={1, 1,1,1,2,2} is stable because the first 1 after sorting is the first 1 before sorting, the second 1 is the second 1 before sorting, and the third 1 is the third 1 before sorting. Same thing with 2. Instability is when they don't start in the same order.

(2) in-situ sort: refers to the sort that does not apply for extra space, that is, the sort that is compared and exchanged in the original sort data. For example, quicksort, heap sort and so on are in place sort, merge sort, count sort and so on are not in place sort.

In general, sorting algorithms are designed in two ways, one based on comparison and the other not. The introduction to algorithms provides a proof that "the optimal time complexity of a comparation-based algorithm is O (N lg N)". For comparation-based algorithms, there are three design ideas: insertion sort, exchange sort and selection sort. The time complexity of non-comparation-based sorting algorithms is O(lg N), which is so low because they generally have special requirements for sorting data. For example, counting sort requires that the data range is not too large, and radix sort requires that the data can be decomposed into multiple attributes.

3. Sorting algorithm based on comparison

As described in the previous section, there are three design approaches to comparation-based sorting algorithms: insertion, exchange, and selection. For insertion sort, there are mainly direct insertion sort, hill sort; For exchange sort, there are mainly bubble sort, quick sort; For selection sort, there are mainly simple selection sort, heap sort; Other sorts: merge sort.

3.1   Insertion sort

(1) direct insertion sort
Features: stable sort, in-place sort, time complexity O(N*N)
Idea: divide the data to be sorted into two sequences, one is the ordered sequence S, the other is the sequence U to be sorted, initially, S is empty, U is the sequence of all data, and then successively insert the data in U into the ordered sequence S, until U becomes empty.

Applicable scenario: when the data has been basically ordered, insertion sort can significantly reduce the number of data exchange and data movement, thus improving the sorting efficiency.

(2) hill sort

Features: unstable sort, in situ sort, time complexity O(n^lamda)(1) < lambda < 2) lamda is related to the selection of each step size.

Idea: incremental narrowing sort. Firstly, the sequence is divided into several groups with approximate number of elements according to the increment. Then, the direct insertion sort method is used to sort each group. Then, the increment is reduced to 1.

Applicable scenario: this algorithm is not commonly used because incremental initial values are not easy to choose.

3.2   Exchange sort

(1) bubble sort

Features: stable sort, in-place sort, time complexity O(N*N)
Idea: the whole sequence is divided into two sub-sequences of unordered and ordered, and the sequence is completed by exchanging larger elements to the first of the unordered sub-sequence.

Applicable scenario: similar to direct insertion sort

(2) quick sort

Features: unstable sort, in-place sort, time complexity O(N*lg N)
Idea: keep looking for the pivot point of a sequence, then move the data that is less than and greater than the pivot point to both sides of the pivot point respectively, and then continue this operation in both sides of the sequence until the whole sequence is sorted.

Scenario: it is widely used, with quicksort apis available in almost every language

3.3   Selection sort

(1) simple selection sort

Features: unstable sort (for example, sort 3, 3, 2, the first 3 will be exchanged with 2), in-place sort, time complexity O(N*N)

Idea: divide the sequence into two sub-sequences of unordered and ordered, search for the minimum (large) value in the unordered sequence and the exchange of the first element of the unordered sequence, expand the ordered area by one, loop on, and finally complete the sorting.

Applicable scenario: few exchanges

(2) heap sort

Features: unstable sort, in situ sort, time complexity O(N*lg N)
Idea: small top pile or large top pile
Applicable scenario: not as extensive as quicksort

3.4   Other sort

(1) merge sort

Features: stable sort, non-in-place sort, time complexity O(N*N)
Idea: first, treat the whole sequence (N elements in total) as N ordered subsequences, then merge two adjacent subsequences in turn, and so on until it becomes a whole ordered sequence.
Applicable scenario: external sorting

4. Non-comparation-based sorting algorithm

There are three kinds of sorting algorithms that are not based on comparison: radix sort, bucket sort and count sort. These algorithms are for special data, not as good as the requirement of uniform data distribution, data deviation is not too big. The idea is to use memory to change time, so all non - in - place sort.

4.1 radix sort

Features: stable sort, non-in-situ sort, time complexity O(N)

Idea: treat each data as d attributes, sort the data according to d attributes (count sort can be used for each round of sorting), the complexity is O(d*N).

Applicable scenario: data is clearly composed of several keywords or attributes

4.2   Bucket sort

Features: stable sort, non-in-situ sort, time complexity O(N)

Idea: divide the data by size into buckets (such as linked lists), each bucket sorted by a simple sorting algorithm.

Applicable scenario: 0

4.3   Count sorting

Features: stable sort, non-in-situ sort, time complexity O(N)

Idea: a technique for counting the number of occurrences of each data (the simplest hash is an array!) , and then output each data from large to small or from small to large.

Usage scenario: much more extensive than radix sort and bucket sort.

5.   conclusion

For comparation-based sorting algorithms, most simple sorts (direct insertion sort, selection sort and bubble sort) are stable except selection sort. Most advanced sorts (with the exception of simple sorts) are unstable except for merge sorts, which require extra storage. For the sorting algorithms which are not based on comparison, they all have special requirements for data rules and adopt the idea of memory changing time. There are so many sorting algorithms that it is often necessary to choose the most suitable sorting algorithm according to the practical application.