Let you understand bubble sorting (C language)

【 introduce 】
We all know , In general , Bubbles will automatically float up slowly from under the water . So we can treat the data to be sorted as a bubble , And then, according to the conditions we control “ Bubble ” People “ Automatically ” Float to the corresponding position . On the whole , The data became orderly .

【 Manual demonstration 】
Let's start at the worst （ A set of data is completely in reverse order ） Let's start with the analysis （ Assume that the data are int type ）：

We can find out , The number of times is the number of elements minus 1(len-1). The number of comparisons per trip varies with the ordinal number of trips , Apparent success Function relation , And their sum is equal to the number of elements Mathematical relations .

【 Code implementation 】
Then convert the above draft to the following code ：

void BubbleSort (int arr[], int len)    // The ginseng ： The array to sort and the number of array elements 
{
    
    int i=0;
    for (i=0; i<len-1; i++)    // The outer loop controls the number of sortations 
    {
        
    	int j=0;
    	for (j=0; j<len-1-i; j++)    // The inner loop controls the comparison times of each sort 
        {
    
            if (arr[j] > arr[j+1])   // The exchange condition of two data （ To make data in ascending or descending order ）
            {
     
                int tmp = arr[j];   //  With the help of temporary variables, the two data are exchanged 
                arr[j] = arr[j+1];    
                arr[j+1] = tmp;
            }
        }
	}
}

You can see , The integer processed in the previous trip , It has been lined up and put in the back , Therefore, there is no need to visit again in the next trip .

Test other use cases , It can also get the expected results .

What if there are multiple elements with equal values ？
If you actually implement the above code , Two elements with equal values will be close to each other during sorting , Once they are adjacent , Then subsequent sorting operations will not change their relative positions , So the bubble sort algorithm is More stable Of .

Time complexity ：
Actually , Not just int Data of type , It can also be other types of data ：

void BubbleSort (elemType arr[], int len)  
{
    
    int i=0;
    for (i=0; i<len-1; i++)    
    {
        
    	int j=0;
    	for (j=0; j<len-1-i; j++)   
        {
    
            if (arr[j] > arr[j+1])  
            {
     
                elemType tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
	}
}

【 Use examples 】
For example, the elements of the structure array are sorted according to the average score of the students ：

void BubbleSort (struct data stu[], int len)
{
    
	int i=0;
	for (i = 0; i < len-1; i++)
	{
    
		int j=0;
		for (j = 0; j < len-1-i; j++)
		{
    
			if (stu[j].average < stu[j + 1].average)   // Sort from large to small 
			{
    
				struct data tmp = stu[j];
				stu[j] = stu[j + 1];
				stu[j + 1] = tmp;
			}
		}
	}
}

Or according to the student's name （ character string ） To sort the elements of the structure array ： The above if Change statement to
if (strcmp(stu[j].name, stu[j + 1].name) > 0) that will do .

More articles ：
Let you understand the sorting of choices （C Language ）