Comparison of bubble sort, insertion sort, and selection sort algorithms in C language

Mastering the commonly used sorting algorithms can save a lot of time in actual project development. There are differences in the execution efficiency of each sorting algorithm. These small time differences may not be felt in ordinary connections, but they are especially important in systems with relatively large amounts of data or tight resources. Important, such as embedded systems. The following is a brief introduction to three commonly used sorting algorithms and a comparison of their execution efficiency.

                                                                                 use using   through   using with   using   using using  -           out out out out out out out out out out out through out of  into  into  office through. -1 pairwise comparison, in the jth comparison, n-j pairwise comparisons are performed.

Implementation code:

void BublleSort (int arr [], int count)
    {
        int i, j, temp;
        for(j=0; j<count-1; j ) /* 冒泡法要排序n-1次*/
            for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
            {
                if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
                {
                    temp=arr[i 1];
                    arr[i 1]=arr[i];
                    arr[i]=temp;
                }
            }
    }

Insertion sort:

Idea: After getting the array to be sorted, divide the array into two parts, the first element of the array is one part, and the remaining elements are one part, and then start from Starting from the second element of the array, compare it with all the elements before this element. If the previous element is not larger than this element, then the position of the element remains unchanged. If there is an element whose value is larger than this element, then record it. The position; for example, I, the position of the element is k, then all elements from i to k positions will be moved back one bit, and then the value at k position will be moved to i position. In this way, the location of K is found. Do this for each element and you will end up with a sorted array.

        Implementation code:

void InsertSort ( int arr[],int count)
    {
            int i,j,temp;
        for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
        {
            temp = arr[i];//操作当前元素，先保存在其它变量中
            for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
            {
                arr[i] = arr[j];
                arr[j] = temp;
            }
    }
}

                                                            ’ s ’ s ’ s ’ t                   out out out out through out out out down to ’ s cue through ’ s right through through through through out through through through through through through through through through through through through through through through through through through‐‐ through‐to‐‐‐‐‐‐ to A[0] ‐‐ ‐ ‐ ‐ ‐ ‐                       0]….A[9] finds the smallest element and exchanges it with A[0]. Then move its reference position one position to the right and repeat the above action. For example, using A[1] as the reference, find the smallest one among A[1]~A[9] and exchange it with A[1]. Sorting ends when the base position is moved to the last element of the array.

          Implementation code:

void SelectSort(int arr[], int count)
    {
        int i,j,min,temp;
        for(i=0; i<count; i )
            {
            min = arr[i];//以此元素为基准
            for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
            {
                if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中 
                {
                    temp = arr[j];
                    arr[j] = min;
                    min = temp;
                }
            }
        }
    }

      Efficiency comparison:

                                                                                  together Out Togetherpsy Out belongingpspspspspspspspscepscepsoperceps straightceceps apart out journey through out journeympserveymptofetoto'eeeeeeeeeeeeeeeeeeeeeeeeeeeeeemptotoluaftotoaftoobaftoobafservtotoobserve-playouttoobsoletetoobsoletepaththroughtoplayouttakeoutderver basis standout.pacts 10000 times. The following is the main function of the test program:

#include <stdio.h>
#include<stdlib.h>
#include <sys/time.h>
#include <unistd.h>

#define MAX 6

int array[MAX];
int count = MAX;

/********创建数组，并输入元素************/
void BuildArray()
{
    int a,i=0;
    printf("请输入数组元素: ");
    for(; i<count; i )
    {
        scanf("%d", &a);
        array[i] = a;
    }
    printf("\n");
}
/**********遍历输出数组元素*************/
void Traverse(int arr[], int count)
{
    int i;
    printf("数组输出: ");
    for(i=0; i<count; i )
        printf("%d\t", arr[i]);
    printf("\n");
}
void BublleSort(int arr[], int count)
{
    int i,j,temp;
    for(j=0; j<count-1; j ) /* 气泡法要排序n-1次*/
        for(i=0; i<count-j-1; i )/* 值比较大的元素沉下去后，只把剩下的元素中的最大值再沉下去就可以啦 */
        {
            if(arr[i]>arr[i 1])/* 把值比较大的元素沉到底 */
            {
                temp=arr[i 1];
                arr[i 1]=arr[i];
                arr[i]=temp;
            }
        }
}

void InsertSort(int arr[],int count)
{
    int i,j,temp;
    for(i=1; i<count; i )//数组分两个部分，从第二个数组元素开始
    {
        temp = arr[i];//操作当前元素，先保存在其它变量中
        for(j=i-1; j>-1&&arr[j]>temp;j--)//从当前元素的上一个元素开始查找合适的位置，一直查找到首元素
        {
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
}

void SelectSort(int arr[], int count)
{
    int i,j,min,temp;
    for(i=0; i<count; i )
    {
        min = arr[i];//以此元素为基准
        for(j=i 1; j<count; j )//从j往前的数据都是排好的，所以从j开始往下找剩下的元素中最小的
        {
            if(min>arr[j])//把剩下元素中最小的那个放到arr[j]中 
            {
                temp = arr[j];
                arr[j] = min;
                min = temp;
            }
        }
    }
}

int main()
{ 
    int i;
    struct timeval tv1,tv2;
    struct timezone tz;
    BuildArray();//创建数组
    Traverse(array, count);//输出最初数组
    gettimeofday(&tv1,&tz);
    for(i=0;i<10000;i++)
        BublleSort(array, count);//冒泡排序
    gettimeofday(&tv2,&tz);
    printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
    Traverse(array, count);//输出排序后的数组
    
    gettimeofday(&tv1,&tz);
    for(i=0;i<10000;i++)
        InsertSort(array, count);//插入排序
    gettimeofday(&tv2,&tz);
    printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec);
    Traverse(array, count);//输出排序后的数组
     
    gettimeofday(&tv1,&tz);
    for(i=0;i<10000;i++)
        SelectSort(array, count);//插入排序
    gettimeofday (&tv2,&tz);
    printf("%d:%d/n",tv2.tv_sec-tv1.tv_sec,tv2.tv_usec-tv1.tv_usec); 
    Traverse(array, count);//输出排序后的数组
    return 0;
}

Compile: gcc –g –Wall sort_test.c –o sort_test

Run: ./sort_test

The results are as follows:

After multiple tests, insertion sort is the fastest quick.

For more comparison of bubble sort, insertion sort, and selection sort algorithms in C language, please pay attention to the PHP Chinese website for related articles!