Thuật toán sắp xếp nổi bọt – Bubble Sort

Giới thiệu

Thuật toán sắp xếp nổi bọt (Bubble Sort) là thuật toán so sánh các phần tử liền kề và hoán đổi vị trí của chúng nếu chúng không theo thứ tự đã định. Thứ tự có thể tăng dần hoặc giảm dần.

Ý tưởng thuật toán sắp xếp nổi bọt

Bước 1

Bắt đầu từ chỉ mục đầu tiên, so sánh phần tử đầu tiên và phần tử thứ hai. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng sẽ được hoán đổi.

Bây giờ, hãy so sánh phần tử thứ hai và thứ ba. Trao đổi chúng nếu chúng không theo thứ tự.

Quá trình trên cứ tiếp tục cho đến phần tử cuối cùng.

Bước 2

Quá trình tương tự diễn ra cho các lần lặp còn lại. Sau mỗi lần lặp, phần tử lớn nhất trong số các phần tử chưa được sắp xếp được đặt ở 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.

Mảng được sắp xếp khi tất cả các phần tử chưa được sắp xếp được đặt đúng vị trí của chúng.

Thuật toán sắp xếp nổi bọt

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSortCode language: HTML, XML (xml)

Cài đặt thuật toán sắp xếp nổi bọt

function bubbleSort(array) {
  var size = array.length;

  // run loops two times: one for walking throught the array
  // and the other for comparison
  for (var i = 0; i < size - 1; i++) {
    for (var j = 0; j < size - i - 1; j++) {

      // To sort in descending order, change > to < in this line.
      if (array[j] > array[j + 1]) {

        // swap if greater is at the rear position
        var temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
}

var arr = [3, 5, -2, 14, -9, 30];
bubbleSort(arr);
console.log(arr);Code language: PHP (php)

Kết quả

[-9, -2, 3, 5, 14, 30]Code language: JSON / JSON with Comments (json)

Thuật toán sắp xếp nổi bọt tối ưu

Trong đoạn mã trên, tất cả các so sánh có thể được thực hiện ngay cả khi mảng đã được sắp xếp. Nó làm tăng thời gian thực hiện.

Đoạn mã có thể được tối ưu hóa bằng cách thêm 1 biến swapped. Sau mỗi lần lặp, nếu không có sự hoán đổi nào diễn ra thì không cần thực hiện các vòng lặp khác.

Trong trường hợp này, biến swapped được đặt là false. Do đó, chúng ta có thể ngăn được lần lặp tiếp theo.

bubbleSort(array)
  swapped <- false
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
      swapped <- true
end bubbleSortCode language: PHP (php)

Cài đặt thuật toán sắp xếp nổi bọt tối ưu

function bubbleSort(array) {
  var size = array.length;

  // run loops two times: one for walking throught the array
  // and the other for comparison
  for (var i = 0; i < size - 1; i++) {
    // swapped keeps track of swapping
    var swapped = Boolean(true);
    for (var j = 0; j < size - i - 1; j++) {
      // To sort in descending order, change > to < in this line.
      if (array[j] > array[j + 1]) {
        // swap if greater is at the rear position
        var temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;

        swapped = false;
      }
    }

    // If there is not swapping in the last swap, then the array is already sorted.
    if (swapped === true)
      break;
  }
}

var arr = [3, 5, -2, 14, -9, 30];
bubbleSort(arr);
console.log(arr);
Code language: PHP (php)

Đánh giá thuật toán sắp xếp nổi bọt

Bubble Sort là một trong những thuật toán sắp xếp đơn giản nhất. Hai vòng lặp được thực hiện trong thuật toán.

Vòng lặp	Số lượng phép so sánh
1	(n-1)
2	(n-2)
3	(n-3)
…….	……
Cuối cùng	1

Số lượng phép so sánh: (n – 1) + (n – 2) + (n – 3) +…..+ 1 = n(n – 1) / 2 gần bằng n².

Độ phức tạp: O(n²)

Ngoài ra, chúng ta có thể phân tích độ phức tạp bằng cách quan sát số vòng lặp. Có 2 vòng lặp nên độ phức tạp là n*n = n².

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

• Trường hợp xấu nhất: O(n²)
  Nếu chúng ta muốn sắp xếp theo thứ tự tăng dần và mảng đã cho theo thứ tự giảm dần thì trường hợp xấu nhất sẽ xảy ra.
• Trường hợp tốt nhất: O(n)
  Nếu mảng đã được sắp xếp thì không cần sắp xếp.
• Trường hợp trung bình: O(n²)
  Nó xảy ra khi các phần tử của mảng có thứ tự lộn xộn (không tăng dần cũng không giảm dần).

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

Độ phức tạp không gian là O(1) vì một biến temp được sử dụng để hoán đổi.

Trong thuật toán sắp xếp nổi bọt tối ưu hóa, biến được hoán đổi làm tăng thêm độ phức tạp không gian, do đó, biến nó thành O(2).

Ứng dụng của thuật toán sắp xếp nổi bọt

Thuật toán sắp xếp nổi bọt được sử dụng trong các trường hợp:

• Độ phức tạp của đoạn mã không quan trọng
• Ưu tiên đoạn mã ngắn

Các bạn có thể tham khảo các bài viết hay về thuật toán sắp xếp trong JavaScript tại đây.

---

Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.