An introduction to sorting algorithms: bubble sort

In development, it is often necessary to arrange a set of data in an orderly manner, so it is absolutely necessary to master several or even more sorting algorithms.

This article introduces one of the simpler sorting algorithms. An algorithm: Bubble sort

First try to use the simplest idea to implement sorting, so as to compare and learn bubble sort

Problem: There is an array with a size of 10 elements (int str[10]) in the array The data is unordered. Now we are required to program this unordered array into an array sorted from small to large (starting from subscript 0)

Idea: According to the requirements of the question, there is no doubt that the correct result should be like this: 1 2 3 4 5 6 7 8 9 10 To do this, the simplest and most direct way to think of is to compare and exchange.

First, put the smallest number among the 10 numbers at the position with subscript 0 (str[0])

By combining the number with subscript 0 (str[0]) and the remaining Compare and exchange the remaining 9 numbers (place the smaller number at the position with the subscript 0), and you can get the one with the smallest 10 numbers

After the 10 smallest numbers are determined, the next step is to find the remaining ones. The next 9 with the smallest number.

Since a minimum number has been determined, don’t move str[0], start directly from str[1], compare and exchange with the remaining 8 numbers, find the smallest one among the 9 numbers and put it in At the position where the subscript is 1 (str[1])

Continue to follow this idea to turn these ten numbers into an ordered (from small to large) array

Code:

#include <stdio.h>  
  
void swap(int *a, int *b); //交换两个数  
  
int main()  
{  
    int     str[10];  
    int     i, j;  
    //初始化数组为10 9 8 7 6 5 4 3 2 1  
    for (i = 0; i < 10; i++)  
    {  
        str[i] = 10 - i;  
    }  
    //排序，从a[0]开始排，从小到大  
    for (i = 0; i < 10; i++)  
    {  
        for (j = i + 1; j < 10; j++)  
        {  
            if (str[i] > str[j])  
            {  
                swap(&str[i], &str[j]);  
            }  
        }  
    }  
        //将十个数输出  
    for (i = 0; i < 10; i++)  
        printf("%d\n", str[i]);  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int     c;  
     c = *a;  
    *a = *b;  
    *b =  c;  
}

This method is relatively easy Thoughts of how to implement it. But there is a shortcoming: the smaller number originally located in the front is exchanged to the back

Demonstration:

Start: 9 4 5 6 8 3 2 7 10 1 (the subscripts are 0~9 from left to right) Follow the above procedure for comparison and exchange

The first time: 4 9 5 6 8 3 2 7 10 1

The second time: 4 9 5 6 8 3 2 7 10 1

. . . : (No exchange)

The fifth time: 3 9 5 6 8 4 2 7 10 1

The sixth time: 2 9 5 6 8 3 4 7 10 1

. . . : (No exchange)

The tenth time: 1 9 5 6 8 3 4 7 10 2

It can be seen that the original smaller number is in the front, and after a round of exchange, it is placed in the back

So How to solve this shortcoming? You can use bubble sort

What is bubble sort?

You can understand it this way: (sorted from small to large) there are 10 bubbles of different sizes, and the smaller bubbles are gradually raised from bottom to top, so that after one traversal, the smallest bubble will be raised to the top ( The subscript is 0), and then rise in this way from bottom to top, and cycle until ten bubbles are in order.

In bubble sorting, the most important idea is to compare the two, and promote the one with the smaller amount of the two.

The worst-case time complexity of bubble sorting is O(n²)

Code:

#include <stdio.h>  
void swap(int *a, int *b);  
int main()  
{  
    int    array[10] = {15, 225, 34, 42, 52, 6, 7856, 865, 954, 10};  
    int    i, j;  
    for (i = 0; i < 10; i++)  
    {  
        //每一次由底至上地上升  
        for (j = 9; j > i; j--)  
        {  
            if (array[j] < array[j-1])  
            {  
                    swap(&array[j], &array[j-1]);  
            }  
        }  
    }  
    for (i = 0; i < 10; i++)  
    {  
        printf("%d\n", array[i]);  
    }  
    return    0;  
}  
void swap(int *a, int *b)  
{  
    int    temp;  
    temp = *a;  
      *a = *b;  
      *b = temp;  
}

risk The bubble sorting algorithm will only gradually push the smaller ones up, and will not cause the shortcomings mentioned earlier in the article, so it will not be demonstrated here.

For more articles related to getting started with sorting algorithms: bubble sort, please pay attention to the PHP Chinese website!