Implementation of Bubble Sort Algorithm in C Language

The bubble sort algorithm is a simple and intuitive sorting method that compares adjacent elements and swaps their positions (if they are in the wrong order) by repeatedly traversing the array to be sorted until the entire array is in order.

The name of this algorithm comes from the fact that smaller elements gradually "float" to the top of the array like bubbles.

Basic bubble sort algorithm.

First, let's look at the implementation of a basic bubble sort algorithm:

#include 

// 函数声明
void bubbleSort(int arr[], int n);
void printArray(int arr[], int size);

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

// 冒泡排序函数
void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        // 最后i个元素已经排好序了
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

In this code, bubbleSortThe function is the core part, it implements sorting through two layers of loops.

The outer loop controls the number of traversals, and the inner loop is responsible for comparing and exchanging adjacent elements.

If the former element is found to be larger than the latter, swap their positions.

This process is repeated until there are no elements to swap.

Time complexity analysis.

The time complexity of bubble sort is O (n ^ 2), where n is the length of the array.

This is because in the worst case, we need to do n *(n -1)/2 comparison and exchange operations.

Although bubble sort works well on small datasets, it is less efficient when dealing with large datasets.

Bubble sort for optimized versions.

In order to improve the efficiency of bubble sort, we can introduce a flag variable to detect whether the array has been ordered.

If no exchange occurs during a full traversal, the sort process can be terminated early, as this means that the array is already ordered.

void optimizedBubbleSort(int arr[], int n) {
    int i, j;
    int swapped;
    for (i = 0; i < n-1; i++) {
        swapped = 0; // 初始化标志变量
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换arr[j]和arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1; // 发生了交换
            }
        }
        // 如果在这一轮中没有发生交换，则数组已经有序
        if (swapped == 0)
            break;
    }
}

In this optimized version, we added a swappedFlag variable.

Every time the inner loop begins, we will swappedSet to 0.

If an exchange occurs in the inner loop, we will swappedSet to 1.

If at the end of an outer loop swappedStill 0, indicating that the array has been ordered, we can exit the loop early.

Practical application scenarios.

Although bubble sort is not the optimal sorting algorithm, it still has its application value in some specific scenarios.

For example, when the amount of data is small or the data is already partially ordered, bubble sort may perform better than more complex sorting algorithms such as quick sort or merge sort.

In addition, the implementation of bubble sort is simple, easy to understand and teach, so it is often used in teaching to introduce the basic concept of sort.

In short, although bubble sort is not as efficient as other advanced sorting algorithms in practical applications, it is still a good starting point for understanding sorting principles.

By learning and practicing bubble sorting, we can better master the design and analysis skills of sorting algorithms.