preface

Believe in sequence for each programmer will be familiar, you may learn the first algorithm is sorting, especially bubble sort you were probably at random, but when from school into the workplace, the classic sort have slowly fade out of our line of sight, because, in the daily development high-level language has packaged help us sorting algorithms, Qsort () in C, sort() and stable_sort() in C++ STL, and collections.sort () in Java are certainly well-written algorithms, but we, as aspiring programmers, It’s worth understanding these classical sorting algorithms a little more thoroughly.

In this chapter, we take a look at three classic sorting algorithms: bubbling, selection, and insertion sort.

thinking

As we all know, when analyzing the quality of an algorithm, our first reaction is to analyze their time complexity. The time complexity of a good algorithm will naturally be low. In addition, the space complexity is also the standard to measure their quality.

As mentioned above, time complexity and space complexity are basically the standards to measure algorithms, but for sorting algorithms, we need to consider more, so what other factors will affect the quality of sorting algorithms?

Factors affecting the

With the question, let’s discuss the advantages and disadvantages of sorting algorithms from the following aspects.

1. Time complexity

Best, worst, average time complexity

Generally, the time complexity we refer to is the average time complexity, but if subdivision is needed, the time complexity can also be divided into the best case, the worst case and the average case, so we need to analyze the execution efficiency of the sorting algorithm through these three cases.

Coefficients, constants, and low orders of time complexity

We know that the (average) time complexity reflects an increasing tendency when n is very large, and its coefficients, constants, and low orders tend to be ignored. But when we’re sorting only 100, 1,000, or 10,000 numbers, we can’t ignore them.

Number of comparisons and number of swaps

When sorting, we often need to compare sizes and swap positions, and this data also needs to be taken into account when comparing execution efficiency.

2. Space complexity

The memory consumption of an algorithm can be expressed in terms of space complexity, and here is a concept that we call the sorting algorithm with space complexity O(1) the in-place sorting algorithm.

3. Stability of sorting algorithm

The stability of a sorting algorithm means that the relative positions of elements with the same value are the same as before the sorting process. For example, if the first array is {3, 2, 1, 2′, 4}, we use 2′ to distinguish the second 2 from the first 2. If the algorithm is stable, it must be {1, 2, 2′, 3, 4}. If the algorithm is not stable, it must be {1, 2, 2′, 3, 4}. The result might be {1, 2′, 2, 3, 4}.

Why do we emphasize stability? For example, if we need to sort an order, need to be done in accordance with the time and price ascending order, will first all ascending order according to time order first, and then to the ascending order of price, are available if the price is not a stable, so the order of time can not arranged in ascending order, so in certain cases, The stability of the sorting algorithm is an important consideration.

Bubble sort

Let’s start with bubble sort.

The principle of bubble sort is to compare two adjacent elements to see if they meet the size relationship. If not, they will switch positions. Each bubble will put an element in its position, and then carry out n rounds of bubble sort, that is, bubble sort is completed.

For example, if we need to sort the array {5,4,3,1,8,2} in ascending order, then after the first bubble, 8 bubbles to the last position because it is the maximum.

Repeat this for six rounds, as shown below, to bubble each element of the array to its position, thus completing the sorting.

Of course, this is a non-optimized bubble sort, and in fact when the array is no longer exchanging data, we can just exit, because it’s already an ordered array. The specific code is as follows:

public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for(int i = 0; i < n; ++ I) {// Exit bubbling flag Boolean flag =false;
    for (int j = 0; j < n - i - 1; ++j) {
      if(a[j] > a[j]) {// int TMP = a[j]; a[j] = a[j+1]; a[j+1] = tmp; // Indicates that there is data exchange flag =true; }} // There is no data exchange, exit earlyif(! flag)break; }}Copy the code

With the above code, we summarize the characteristics of bubble sort.

1. Time complexity

When the array is ordered, it only has to traverse it once, so the best time is O(n); If the data is in reverse order, and this is O(n^2), what is the average time?

Calculating average time complexity is tricky because it involves quantitative analysis in probability theory, so it can be done in the following way. Using the sorting array above as an example, let’s understand the following concepts:

  • Degree of order: degree of order refers to the number of ordered pairs in an array. For example, the number of ordered pairs in the array above is (4,5), (4,8), (3,5), (3,8), (1,5), (1,8), (5,8), (2,8), so the degree of order is 9.
  • Full order degree: Full order degree refers to the ordered number pairs when an array is in the ordered state, or the ordered number pairs after the above array is sorted. There are 15 pairs by summing the arithmetic sequence, and the general formula for finding full order degree is n(n-1)/2.
  • Degree of reverse order: Degree of reverse order is exactly the opposite of degree of order, so the value of the array above is 15-9=6, that is, degree of reverse = full order – degree of order.

Once we understand these three concepts, we can see that sorting an array is actually a process of increasing the degree of order and decreasing the degree of reverse order, so our sorting process is actually a process of finding the degree of reverse order.

So we can calculate the average time complexity of bubble sort, the best case is 0, the worst case is n(n-1)/2, so the average time complexity takes the middle value, which is N (n-1)/4, so after simplifying the coefficients, constants, and lower orders, the average time complexity is O(n^2).

2. Space complexity

Because bubble sort only needs constant level temporary space, so the space complexity is O(1), it is an in-place sorting algorithm.

Stability of 3.

In bubble sort, only when the two elements do not meet the conditions will need to swap, so only when the latter element is greater than the previous element will be swapped, then bubble sort is a stable sorting algorithm.

Selection sort

The principle of selection sort is the process of selecting the smallest element in the unsorted part and placing it in the next place after the sorted part.

Like bubble sort, we analyze the selection sort by sorting the array {5,4,3,1,8,2}, as shown in the figure below.

After 6 cycles, the array sort is completed, and the specific implementation code is as follows:

public static int[] SelectSort(int[] array) {
	for(int i = 0; i < array.length; i++) { int index = i;for(int j = i; j < array.length ; J++) {// find the minimum value for each roundif(array[j] < array[index]) { index = j; Int temp = array[I]; int temp = array[I]; array[i] = array[index]; array[index] = temp; }return array;
}
Copy the code

The selection sort is analyzed by the sorting process diagram and code above.

1. Time complexity

The best-case, worst-case, and average-case time complexities of selection sort are all O(n^2). Because the array, whether ordered or not, is sorted by comparing each pair of elements, and then swapping when the comparison is done, the time in each case is O(n^2).

2. Space complexity

Because only temporary space is needed, it is an in-place sorting algorithm with space complexity O(1).

Stability of 3.

As shown in the figure below, we sort {5, 5′, 1}, and we know that the position of the two 5’s after sorting has been switched, so it is not stable sorting.

Insertion sort

Let’s think about what happens when we insert an element into an ordered array and keep it ordered. The diagram below.

Insert sort is the operation shown above, where you take an element from an unordered array, find its position in the ordered array, and then insert, add one element to the ordered array, subtract one from the unordered array, until the length of the unordered array is 0.

As with the previous two sorting algorithms, we use insert sort to sort the array {5,4,3,1,8,2}, as shown in the figure below.

If above process can be know, every time take the first element in the array from the chaos, cached, then at the start of the last element from the sorted comparison, when the element is greater than sorted elements, ward a sorted elements, until meet elements smaller than he, and then in smaller than his elements of a position after the insertion of cached element, This adds one element to the sorted array and subtracts one element from the unsorted array until the end.

In summary, the algorithm is as follows:

public void insertSort(int[] arr, int n) {
	if (n <= 0) {
		return;
	}

	for(int i = 0; i < n; i++) { int temp = arr[i]; Int j= I -1; int j= I -1;while(j>=0) {
			if(arr[j] > temp) {// If the current element is larger than temp, arr[j] = arr[j]; j--; }else{// If the current element is less than temp, temp is larger than all the previous onesbreak; } // insert arr[j+1] = temp; }}Copy the code

Insert sort is analyzed through the sorting process diagram and code above.

1. Time complexity

The best time complexity is O(n) when the array is ordered. The worst time complexity is O(n^2) when the array is reversed. We know that the average time to insert an element into an ordered array is O(n), so n operations are done, so the average time is O(n^2).

2. Space complexity

Insertion sort is in place, so the space complexity is O(1).

Stability of 3.

Insert sort Each insert position is greater than or equal to the previous element, so stable sort.

Three more

After the above analysis of the three algorithms with time complexity O(n^2), we can know their differences as shown in the following table:

It can be seen from the comparison that both bubble and insert sort are better than selection sort, but insert sort is often more easily selected than bubble sort. Why is this?

Although bubbling and inserted on the time complexity and space complexity, stable performance is the same, but we don’t overlook the things that we find the time complexity of it is ignored coefficient, constant and low order parameter, looking at the code we know that the bubbling and insert when swapping elements are as follows, if an assignment operation time consuming as K, So bubble sort takes 3K to do a swap, whereas insert sort takes K.

Int TMP = a[j]; a[j] = a[j+1]; a[j+1] = tmp;Copy the code
// Insert sort swap element arr[j+1] = arr[j];Copy the code

And, of course, this is just a theoretical analysis, when I use my own machines, respectively with bubbling and insertion algorithm of 10000 the same array (200 each array element), sort, bubble sort takes 490 ms, insertion sort takes 8 ms, so visible insertion sort because every time is a relatively short time consuming, so overall less time consuming than bubbling.

conclusion

Although the complexity of these three kinds of sorting is high, up to O(n^2), bubble and selection sort can not be used in practice, can only stay in theoretical research, and insertion sort or its in-place sorting and stability can be used in some specific scenarios.