C language bubble sort algorithm and code

Bubble sort is a kind of sorting algorithm with clear ideas and concise code. It is often used in computer courses for college students.

The name "bubble" comes from the fact that larger elements will slowly "float" to the top of the sequence through exchange, hence the name.

Here is an example of sorting from small to large.

Basic idea and examples

The basic idea of ​​bubble sort is to continuously compare two adjacent numbers, so that the larger element continues to move back. After one round of comparison, the largest number is selected; after the second round of comparison, the second largest number is selected, and so on.

The following is an explanation of bubble sorting 3 2 4 1.

First round of sorting process
3 2 4 1 (Initially)
2 3 4 2 (Compare 3 and 2, swap)
2 3 4 1 (Compare 3 and 4, no swap)
2 3 1 4 (Compare 4 and 1, swap)
The first round is over, the largest number 4 is already at the end, so the second round of sorting only needs to compare the first three numbers again.

Second round of sorting process
2 3 1 4 (First round sorting result)
2 3 1 4 (Compare 2 and 3, no exchange)
2 1 3 4 (Compare 3 and 1, exchange
End of the second round , the second largest number is already in the second to last position, so the third round only needs to compare the first two elements

The third round of sorting process
2 1 3 4 (the second round of sorting results)
1 2 3 4 (Compare 2 and 1, exchange)
At this point, the sorting is over.

Algorithm summary and implementation

For an array R[n] with N elements, perform up to N-1 rounds of comparison;

The first round, one by one. Compare (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), …. (R[N-1], R[ N]); The largest element will be moved to R[N].

In the second round, compare (R[1], R[2]), (R[2], R[3]), ( R[3], R[4]), …. (R[N-2], R[N-1]); the second largest element will be moved to R[N-1]. . .
And so on, until the entire array is sorted from small to large.

The general implementation and optimization implementation of bubble sorting are common implementation methods in textbooks, and will be performed regardless of whether the array is sorted. N-1 rounds of comparison; and the optimized implementation will exit the comparison early when the array has been sorted, reducing the time complexity of the algorithm

#include<stdio.h>
#include<stdlib.h>

#define N 8

void bubble_sort(int a[],int n);


//一般实现
void bubble_sort(int a[],int n)//n为数组a的元素个数
{
//一定进行N-1轮比较
for(int i=0; i<n-1; i++)
{
//每一轮比较前n-1-i个，即已排序好的最后i个不用比较
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
}
}

//优化实现
void bubble_sort_better(int a[],int n)//n为数组a的元素个数
{
//最多进行N-1轮比较
for(int i=0; i<n-1; i++)
{
bool isSorted = true;
//每一轮比较前n-1-i个，即已排序好的最后i个不用比较
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
isSorted = false;
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
if(isSorted) break; //如果没有发生交换，说明数组已经排序好了
}
}


int  main()
{
int num[N] = {89, 38, 11, 78, 96, 44, 19, 25};

bubble_sort(num, N); //或者使用bubble_sort_better(num, N);

for(int i=0; i<N; i++)
printf("%d  ", num[i]);

printf("\n");


system("pause");
return 0;
}

More C language bubble sorting algorithms. For code-related articles, please pay attention to the PHP Chinese website