I wrote an article on selection sorting, which many people confuse with bubble sorting. This article is an analysis of bubble sorting, and I hope you can distinguish it, but also hope to be able to answer bubble sorting perfectly during the interview. This year’s job is said to be difficult to find, of course luck plays a large part, but the stronger you are, the less luck you will have.

A, understanding bubble sort

When learning sorting algorithms before, bubble sort is often the first to be introduced, because it is too simple. Bubble sort is simple:

Compare two adjacent numbers in turn, putting the decimal first and the large number after.

Note: bubble sort compares two adjacent numbers, and selects the largest or smallest number in the entire queue for comparison.

First run: first compare the 1st and 2nd number, place the decimal first and the large number last. And then you compare the second and the third number, you put the decimal in front, the large number in back, and so on, until you compare the last two numbers, you put the decimal in front, the large number in back. (The last number must be the largest in the entire array.)

Second run: the same as the first run, but the last number is already the maximum, compare to the second to last can be. (The penultimate number must be the penultimate number of the entire array.)

The third, fourth and so on.

Here’s a GIF to illustrate:

If you look at the graph above a few times, you can see that each time you sort it out, you can pick out the maximum value of the current array. OK. Once you understand that, let’s start writing code to implement a wave.

Two, code implementation

1. Basic implementation

Let’s look at the basic implementation first.

public void BubbleSort(int arr[],int n){
	int temp;
	// There are N numbers, so N runs
	for(int i = 0; i<n; ++i)// Every time you compare from right to left, you get the minimum value
		// From left to right, we get the maximum value
		for(int j = n-1; j>i; --j)// If the number on the right is the number on the left, switch places
			if(arr[j]<arr[j-1]){
				temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp; }}Copy the code

This is very simple, but we may find that each trip actually yields a value, which may be the maximum or minimum value of the current array.

Disadvantages of this:

There is a part of the array that is already ordered, and each bubble will waste time in that part

2, improve

Now let’s improve: if we think differently, every scan we do, we set a flag for the ordered parts, true to indicate that a swap took place, and false to indicate that no swap took place, then we can skip right over it.

public static void bubbleSort2(int [] a, int n){
    int j, k = n;
    // True if swap occurs, false if swap does not occur
    boolean flag = true;
    while (flag){
        flag=false;// Set flag to unsorted before each sorting
        for(j=1; j<k; j++){
            // If the preceding number is greater than the following number, swap
            if(a[j-1] > a[j]){
                int temp;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
                // Indicates that data has been exchanged.
                flag = true; } } k--; }}Copy the code

3. Continue to improve

Although the above one is very good, it still has some limitations. For example, the array has a large amount of data of 10000, the front 3000 is disorderly, and the back 7000 are all arranged, and they are larger than the first 3000. At this time, only the first 3000 can be compared. But the improved algorithm still compares the first 3,000 to the next 7,000 every time it sorts them. That’s bloated. So we make improvements.

public static void bubbleSort3(int [] a, int n){
    int j , k;
    int flag = n ;
    while (flag > 0){
        k = flag; //k to record the trailing boundary of the traversal
        flag = 0;
        for(j=1; j<k; j++){
            if(a[j-1] > a[j]){
                int temp;
                temp = a[j-1];
                a[j-1] = a[j];
                a[j]=temp;
                // Indicates that data has been exchanged.flag = j; }}}}Copy the code

The improvement is to change the flag to a specific location so that we can record trailing boundaries. This boundary is the sort and unsorted boundary.

Third, summary

Bubble sorting is the first common case involving time complexity and space complexity in written tests or interviews. So its time is O(n^2). Although simple, but the time is really quite long.

We have to pay attention to the difference between selection sort, which is to go around and find the lowest possible value and switch places with the first student. And the bubble sort is that the neighbor is higher than the neighbor, so once you go, the highest one sinks to the end.