Understanding Bubble Sort Algorithm (with Examples in Java)

Detailed explanation of Bubble Sort: a simple sorting algorithm

Bubble sort is one of the simplest sorting algorithms. It works by repeatedly comparing adjacent elements and swapping them if they are out of order. For example, if the sort order is ascending, adjacent elements are compared and the larger element is placed on the right. In each iteration, we compare only the unsorted elements and place the largest element at the last position of the unsorted elements in the array.

This algorithm is aptly named bubble sort because the elements move toward the right side of the array on each iteration, like a bubble rising to the surface of the water.

How bubble sort works

Suppose we want to sort this array in ascending order:

First iteration

In the first iteration, we try to move the largest element to the end of the array. So we will repeatedly compare adjacent elements and swap them if they are out of order.

Elements that have been moved to the correct position are considered sorted.

Following iterations

This process is repeated for all iterations until the array is sorted. In each iteration, we only compare the unsorted elements since the sorted elements are already in the correct order.

We iterate over the array n-1 times, where n is the length of the array. That is, since our array has six elements, we only iterate through the array five times. This is because, after the fifth iteration, the five elements have been placed in their correct positions, so the final unsorted element is considered sorted. After all iterations are completed, we will get a sorted array.

Implementation of bubble sort

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Running this code will print the following output in the console:

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

In this implementation of bubble sort, we will iterate through the array each time, even if the array is already sorted. We can further optimize the code so that the sorting stops once the array has been sorted.

Optimized bubble sort

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果没有交换，则数组已排序
        if(!swapped) break;
    }
}

With this implementation, if we try to sort an array that is already sorted, we will only iterate once and stop when no sorting occurs.

Complexity of bubble sort

Time complexity:

Best case (O(n)):

The best case scenario is that the input array is already sorted. The algorithm only iterates the array once to check if it is sorted and does not perform any swapping.

Average case (O(n²)):

When the input array elements are in random order. The algorithm must iterate multiple times and perform swaps to sort the array.

Worst case (O(n²)):

The worst case scenario is that the input array is sorted in reverse order. The algorithm goes through n-1 iterations and performs the maximum number of swaps.

Space complexity O(1):

Bubble sort is an in-place sorting algorithm, that is, it does not require any additional memory proportional to the size of the input array.

Conclusion

Bubble sort is an algorithm that is easy to understand and implement. However, due to its high time complexity, it is not suitable for processing large data sets. Bubble sort can be used when working with small data sets, or when you don't care about complexity.

The above is the detailed content of Understanding Bubble Sort Algorithm (with Examples in Java). For more information, please follow other related articles on the PHP Chinese website!