Bubble Sort (Sắp xếp nổi bọt)

Posted on by mtoplistChuyên mục:Top List

Bubble Sort là một thuật toán sắp xếp đơn giản. Nó được sử dụng để sắp xếp một tập hợp n phần tử đã cho được cung cấp dưới dạng một mảng với n số phần tử.

Giả sử yêu cầu mảng phải được sắp xếp theo thứ tự tăng dần, thì sẽ bắt đầu bằng cách so sánh phần tử đầu tiên của mảng với phần tử thứ hai, nếu phần tử thứ nhất lớn hơn phần tử thứ hai, nó sẽ hoán đổi cả hai phần tử và sau đó chuyển sang so sánh phần tử thứ hai và phần tử thứ ba, v.v… Nếu có n phần tử, thì ta phải lặp lại quá trình này n - 1 lần.

Nó được gọi là Bubble Sort (Sắp xếp nổi bọt), bởi vì với mỗi lần lặp hoàn chỉnh, phần tử lớn nhất trong mảng đã cho sẽ “nổi” sang bên phải của mảng, giống như một bong bóng nước nổi lên trên mặt nước.

1. Cơ chế hoạt động của Bubble Sort

Lấy ví dụ một mảng với các giá trị {5, 1, 6, 2, 4, 3}. Hình ảnh dưới đây mô tả cách sắp xếp mảng đã cho theo Bubble Sort:

Image source: Studytonight

2. Cài đặt Bubble Sort

Mã code dưới đây sẽ mô tả cách cài đặt giải thuật Bubble Sort trong Java: 

package com.icancodeit.algorithm.sorting;

import java.util.Arrays;

public class BubbleSort {

  // Sort the original data
  private static final int[] NUMBERS = {5, 1, 6, 2, 4, 3};

  public static void bubbleSort(int[] arr) {
    int temp, length = arr.length;
    for (int i = 0; i < length - 1; i++) {
      for (int j = 0; j < length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    bubbleSort(NUMBERS);
    System.out.println(Arrays.toString(NUMBERS) + " bubbleSort");
  }

}

Kết quả:

[1, 2, 3, 4, 5, 6] bubbleSort

Lưu ý:

length - 1 - i để bỏ qua phần tử đã được so sánh trong các lần lặp trước đó.

3. Optimized giải thuật

Để tối ưu hóa giải thuật này, chúng ta sẽ sử dụng một biến flag để theo dõi xem các phần tử có bị hoán đổi bên trong vòng lặp for thứ 2 hay không.

Nếu không có sự hoán đổi nào xảy ra, điều đó có nghĩa là mảng đã được sắp xếp, và ta sẽ break ra khỏi vòng lặp for phía ngoài thay vì phải lặp tất cả.

Lấy ví dụ một mảng với các giá trị {11, 17, 18, 26, 23}. Hình ảnh dưới đây mô tả việc tối ưu giải thuật Bubble Sort với mảng đã cho:

Image Source: Studytonight

Mã code cài đặt trong Java:

package com.icancodeit.algorithm.sorting;

import java.util.Arrays;

public class BubbleSortOptimized {

  // Sort the original data
  private static final int[] NUMBERS = {11, 17, 18, 26, 23};

  public static void bubbleSort(int[] arr) {
    int temp, length = arr.length;
    boolean flag = false;

    for (int i = 0; i < length - 1; i++) {
      for (int j = 0; j < length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
          flag = true;
        }
      }

      if (!flag) {
        break;
      }
    }
  }

  public static void main(String[] args) {
    bubbleSort(NUMBERS);
    System.out.println(Arrays.toString(NUMBERS) + " bubbleSort Optimized");
  }

}

Kết quả:

[11, 17, 18, 23, 26] bubbleSort Optimized

4. Phân tích độ phức tạp của Bubble Sort

  • Ưu điểm lớn nhất của giải thuật Bubble Sort là sự đơn giản, dễ cài đặt, sử dụng.
  • Nhược điểm là nó chạy khá là chậm với tập dữ liệu có kích thước lớn.

Ta có n - 1 bước so sánh ở vòng lặp 1st, n - 2 bước ở vòng lặp 2nd, n - 3 bước ở vòng lặp 3rd, v.v… Vì vậy tổng số bước so sánh sẽ là:

(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
Sum = n(n-1)/2

Áp dụng các quy tắc tính Time Complexity (Quy tắc bỏ hằng số, quy tắc lấy Max,…) ta sẽ tính được TM của giải thuật Bubble Sort là O(n2)

Space Complexity của Bubble Sort là O(1), vì chỉ cần một không gian bộ nhớ bổ sung duy nhất cho biến temp.

Đọc thêm:

https://www.studytonight.com/data-structures/bubble-sort

https://github.com/amejiarosario/

Advertisement

mtoplist