1. Bubble Sort

Bubble sort là một thuật toán sắp xếp so sánh hai phần tử lần lượt và hoán đổi cho đến khi theo thứ tự mà chúng ta mong muốn.

2. Chi tiết thuật toán

2.1 Vòng lặp đầu tiền (So sánh và hoán đổi)

• Bắt đầu từ phần tử đầu tiên và phần tử thứ 2 trong mảng.
• Nếu phần tử đầu tiên nhỏ hơn phần tử thứ 2, chúng ta hoán đổi vị trị 2 phần tử.
• Tiếp theo, so sánh phần tử thứ 2 và phần tử thứ 3. Hoán đổi vị trí nếu chưa đúng thứ tự.
• Quá trình tiếp tục đến phần tử cuối cùng.

2.2 Lặp lại quá trình

• Quá trình được thực hiện tương tự cho các vòng lặp còn lại.
• Sau mỗi lần lặp lại, phần tử lớn nhất trong chuỗi chưa được sắp xếp sẽ được đặt ở vị trí cuối.

Trong mỗi lần lặp, việc so sánh diễn ra cho đến phần tử chưa được sắp xếp cuối cùng.

Và cuối cùng sau khi được sắp xếp, các phần tử sẽ ở đúng vị trí.

3. Code thực hiện thuật toán

// Bubble sort in Java
 
import java.util.Arrays;
 
class Main {
 
  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
 
    // loop to access each array element
    for (int i = 0; i < size - 1; i++)
 
      // loop to compare array elements
      for (int j = 0; j < size - i - 1; j++)
 
        // compare two adjacent elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {
 
          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }
 
  public static void main(String args[]) {
 
    int[] data = { -2, 45, 0, 11, -9 };
 
    // call method using class name
    Main.bubbleSort(data);
 
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

4. Tối ưu thuật toán Bubble Sort

Trong thuật toán trên, quá trình thực hiện tất cả các so sánh ngay cả khi mảng đã được sắp xếp.

Điều này làm tăng thời gian thực hiện chương trình.

Để giải quyết vấn đề này. Chúng ta thêm 1 biến swapped. Giá trị của swapped bằng false nếu như không có phần tử nào được hoán đổi. Ngược lại, swapped bằng true

Và sau khi thực hiện bất kì 1 vòng lặp nào trong quá trình, nếu không có sự hoán đổi nào. Điều này có nghĩa là mảng đã được sắp xếp và không cần thực hiện thêm các lần lặp còn lại.

Điều này sẽ làm giảm thời gian thực hiện và giúp tối ưu thuật toán.

5. Code sau khi được tối ưu

// Optimized Bubble sort in Java
 
import java.util.Arrays;
 
class Main {
 
  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
 
    // loop to access each array element
    for (int i = 0; i < (size-1); i++) {
 
      // check if swapping occurs
      boolean swapped = false;
 
      // loop to compare adjacent elements
      for (int j = 0; j < (size-i-1); j++) {
 
        // compare two array elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {
 
          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
 
          swapped = true;
        }
      }
      // no swapping means the array is already sorted
      // so no need for further comparison
      if (!swapped)
        break;
 
    }
  }
 
  public static void main(String args[]) {
 
    int[] data = { -2, 45, 0, 11, -9 };
 
    // call method using the class name
    Main.bubbleSort(data);
 
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

6. Độ phức tạp thuật toán

Độ phức tạp chi tiết

Bubble Sort so sánh các phần tử liền kề.

Do đó, số lần cần so sánh là:

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

gần bằng to n^2

Do đó, độ phức tạp thuật toán: O(n^2) Ngoài ra, nếu chúng ta đọc code, có thể thấy được bubble sort cần 2 vòng lặp. Do đó độ phức tạp sẽ là n*n=n^2

6.1 Độ phức tạp thời gian

• Trường hợp xấu nhất: O(n^2)

  Nếu chúng ta sắp xếp tăng dần và mảng đang được sắp xếp theo thứ tự giảm dần thì trường hợp xấu nhất xảy ra.

• Trường hợp tối nhất: O(n)

  Nếu mảng đã được sắp xếp, thì không cần phải sắp xếp 😁.

• Trường hợp thường xảy ra: O(n^2)

  Trường hợp này xảy ra khi các phần tử của mảng không theo thứ tự nào cả (không tăng và cũng không giảm dần).

6.2 Độ phức tạp không gian

• Độ phức tạp không gian là O(1) bởi vì chỉ cần 1 biến bổ sung để hoán đổi.
• Trong thuật toán được tối ưu, 2 biến được sử dụng. Do đó độ phức tạp không gian sẽ là O(2)

7. Ứng dụng thuật toán Bubble Sort

Thuật toán Bubble Sort được sử dụng khi:

• Độ phức tạp không quan trọng.
• Code đơn giản và ngắn.