Visualization and comparison of nine sorting algorithms

Sorting is a very common problem in work and life. Now there are mature sorting techniques, which are widely used in various programming languages or databases. Different sorting algorithms have different performance and application scenarios. The following video compares the performance of nine sorting algorithms. The sorting algorithms are selection sort, hill sort, insertion sort, merge sort, quick sort, heap sort, bubble sort, comb sort, cocktail sort.

Bubble sort

Bubble Sort is a kind of swap Sort. The basic idea is to compare the keys of adjacent records in pairs and swap them if they are in reverse order until there are no records in reverse order.

In the best case, where the sequence itself is sorted, n – 1 comparisons are required; In the worst case, where the sequence itself is in reverse order, n(n-1)/2 comparisons are required. So the total time of bubble sort is O(n^2).

Selection sort

The basic idea of Selection sort is to select the record with the smallest (or largest) keyword from the n-i + 1 (I = 1,2,***, n-1) records as the i-th record of the ordered sequence until all elements are sorted. Selection sort is an unstable sorting algorithm.

The time complexity of selection sort is O(n^2), but the performance is slightly better than bubble sort.

Insertion sort

Insertion sort is similar to sorting cards. The basic operation is to insert a record into an already ordered sequence of numbers, resulting in an ordered sequence with the number of records plus one.

The time complexity of insertion sort is O(n^2), which is stable and suitable for sorting with a small number of sorts.

Cocktail ordering

Cocktail sort is a variation of bubble sort. Find the smallest number and put it first, then find the largest number and put it last. And then find the second smallest number and put it in the second, and then find the second largest number and put it in the second to the last. And so on until you finish sorting.

The time complexity of cocktail sorting is O(n^2).

Hill sorting

Shell Sort is a kind of insert Sort, which is an improvement of direct insert Sort algorithm. The basic idea is to form a subsequence of records separated by a certain increment D, make the subsequence basically ordered by insertion sort, and then reduce the increment to continue sorting.

The operation takes an integer d1 less than n as the first increment, and divides all records into d1 groups. All records that are multiples of DL are placed in the same group. First, insert into each group, then take the second increment d2 < d1 and repeat the above grouping and sorting, until dt = 1 (dt<dt-l<… <d2<d1), that is, until all records are placed in the same group for direct insertion sort.

The time complexity of Hill sort can reach O(n^(3/2)), which is better than the previous algorithms.

Comb the sorting

Comb sort is very similar to Hill sort. Hill sort is optimized on the basis of direct insertion sort, while comb sort is optimized on the basis of bubble sort, that is, the records separated by a certain increment D form a subsequence, by bubble sort to make the subsequence basically ordered, and then reduce the increment to continue sorting.

The time of comb sort is O(nlogn).

Merge sort

Merge-sort is a divide-and-conquer algorithm, which is an effective sorting algorithm based on merging operations. The commonly used two-way merge sort assumes that the initial sequence has N records, which can be regarded as N subsequences of length 1. By merging in pairs, n / 2 subsequences of length 2 or 1 can be obtained. Merge two more, ******, until you get an ordered sequence of length n.

The time complexity of merge sort is O(nlogn), which is a high efficiency and stable algorithm.

Quick sort

Quicksort is an improvement on bubbling sort. The basic idea is to divide the records to be sorted into two independent parts through a sorting, one part of the records are smaller than the other part, and then conduct a quick sorting of the two parts respectively, and finally achieve the sorting of the whole sequence.

The time complexity of quicksort is O(Nlogn), which is an unstable sorting algorithm.

Heap sort

A heap is a complete binary tree with the following properties:

1. The value of each node is greater than or equal to the value of its left and right children, which is called the big top heap.

2. The value of each node is less than or equal to the value of its left and right children. This is called the small top heap.

Heap sort refers to a sort algorithm designed by using Heap data structure. The basic idea is to construct a large top heap for the sequence to be sorted, where the maximum value of the sequence is the top element, place that element last, and then continue to construct a large top heap for the remaining N-1 elements until the sorting is complete.

The time complexity of heap sort is O(nlogn), which is not suitable for the case with a small number of sequences because the heap needs to be constructed.

Visualization and comparison of nine sorting algorithms

Bubble sort

Selection sort

Insertion sort

Cocktail ordering

Hill sorting

Comb the sorting

Merge sort

Quick sort

Heap sort

Related Posts

Table Analysis of commodity Module database (II)

The Linux kernel

Dubbo and Spring integration for service exposure