Bubble Sort

A simpler sorting algorithm for computer science. It repeatedly walks through the column of elements to be sorted, comparing two adjacent elements in turn, and swapping them if the order is wrong (from largest to smallest, from Z to A). The task of visiting an element is repeated until no neighboring elements need to be swapped, that is, the element column has been sorted. The algorithm gets its name from the fact that smaller elements slowly “float” to the top of the sequence (ascending or descending) through exchange, just as bubbles of carbon dioxide in a carbonated drink eventually rise to the top.

The basic idea

Each time you compare two adjacent numbers, move the smaller (or larger) number to the front. Repeat this step and end up with the largest (or smallest) number at the end.

Algorithm description

1. Compare two adjacent numbers. If the first is larger than the second, swap the two numbers

2. Do the same 1 for each adjacent number, so that the largest number is the number at the end of the row from the beginning to the end.

3. For all elements except the last one.

4. Repeat steps 1 to 3 in the correct sequence.

Algorithm implementation

(Here’s an example of ordering from smallest to largest)

The C language# include<stdio.h>
int main(void)
{
	int i, j, t, n;
	int a[100];
	scanf("%d",&n);
	getchar();
	for(i=0; i<n; i++) scanf("%d",&a[i]); // go through the number groupfor(i=0; i<n-1; I++) // make n-1 comparison {for(j=0; j<n-1-i; J++)// do n-1- I comparisons per trip {if(a[J]> A [j+1]) // Comparison of two Adjacent numbers t= A [J]; a[j]=a[j+1]; a[j+1]=t; }}for(i=0; i<n; i++)printf("%d ",a[i]);
	return 0;
}
Copy the code

Algorithm analysis

Bubble sort is stable because when two numbers are equal, they don’t swap and don’t change their relative positions