For any programmer, the first algorithm to learn is probably sorting. The most commonly used are: bubble sort, count sort, insert sort, quick sort, selection sort, etc. Among them, the time complexity of bubble sort, insertion sort and selection sort is O(n^2), and the sorting algorithm is based on comparison.

Consider: Insert sort and bubble sort have the same time complexity, O(n2). In real software development, why do we prefer to use insert sort rather than bubble sort?

How to analyze a sorting algorithm

Learning sorting algorithm, in addition to learning his algorithm principle, code implementation, more important is to learn how to evaluate, analyze a sorting algorithm. Analysis of a sorting algorithm, generally from the following aspects:

The execution efficiency of sorting algorithm

  1. Best case, worst case, average case time complexity
  2. Time complexity coefficient, constant, low order
  3. Comparison times and swap (or move) times (memory consumption of sorting algorithm, stability of sorting algorithm)

Bubble sort parsing

Bubble sort is in place sort algorithm?

The bubbling process only involves the exchange operation of adjacent data and only requires constant level temporary space, so its spatial complexity is O(1) and it is an in-place sorting algorithm.

Is bubble sort a stable sorting algorithm?

In bubble sort, only swapping can change the order of two elements. In order to ensure the stability of bubble sort algorithm, when there are two adjacent elements of the same size, we do not exchange, the same size of data before and after sorting will not change the order, so bubble sort is a stable sorting algorithm.

What is the time complexity of bubble sort?

In the best case, the data to be sorted is already in order, and we only need one bubble operation, and we’re done, so in the best case, the time is order n. And in the worst case, the data that we’re sorting happens to be in reverse order, so we need to bubble n times, so in the worst case it’s order n^2.

Insertion sort parsing

Insert sort is in place sort algorithm?

It can be clearly seen from the implementation process that the operation of insertion sorting algorithm does not need additional storage space, so its space complexity is O(1), is an in situ sorting algorithm.

Is insertion sort a stable sorting algorithm?

In insert sort, for elements with the same value, we can choose to insert the element appearing after the element appearing before, so that the original order can remain unchanged, so the stable sorting algorithm of insert sort.

What is the time complexity of insertion sort?

If the data to be sorted is already in order, we do not need to move any data. If we look up the insertion position from end to end in an ordered data set, we can determine the insertion position by comparing only one data at a time. So in this case, the best time complexity is O(n).

If the array is in reverse order, each insert is equivalent to inserting new data in the first position of the array, so a large amount of data needs to be moved, so the worst event complexity is O(n^2).

Bubble sort and insert sort are both O(n^2) in time, both are in place sorting algorithms, so why is insert sort more popular than bubble sort?

It can be concluded from the previous analysis that no matter how bubble sort is optimized, the number of element exchange is a fixed value, which is the reverse order of the original data. Insert sort is the same, no matter how optimized it is, the number of element moves is equal to the degree of reverse order of the original data.

However, from the point of view of code implementation, the data exchange of bubble sort is more complicated than the data movement of insert sort. Bubble sort requires three assignment operations, while insert sort only needs one.

The exchange of data in bubble sortif(a) [j] > [m + 1] a) {/ / exchange int TMP = a [j] a [j] = a [m + 1] a [j + 1) = TMP flag =true} insert the movement of data in sortif(a[j] > value) {a[j] = a[j]Copy the code

We roughly count the time it takes to execute an assignment statement as unit_time, and then sort the same array of reverse degree K using bubble sort and insert sort, respectively. Bubble sort requires k swaps, each of which requires 3 assignments, so the total swap time is 3*K units of time. In insert sort, data movement takes K units of time.

Conclusion:

So, although bubble sort and insert sort are the same in terms of time complexity, O(n^2), if we want to maximize performance, insert sort is definitely preferred. Of course, the idea of insertion sort also has a lot of room for optimization, so hill sort appeared again.