Thuật toán sắp xếp nổi bọt - Bubble Sort | Học lập trình JavaScript

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.

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

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.

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

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;

   
   
  for
 (var
 i = 0
; i < size - 1; i++) {
    for
 (var
 j = 0
; j < size - i - 1; j++) {

       
      if
 (array
[j] > array
[j + 1]) {

         
        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 bubbleSort
Code 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;

   
   
  for
 (var
 i = 0
; i < size - 1; i++) {
     
    var
 swapped = Boolean(true);
    for
 (var
 j = 0
; j < size - i - 1; j++) {
       
      if
 (array
[j] > array
[j + 1]) {
         
        var
 temp = array[j];
        array
[j] = array
[j + 1];
        array
[j + 1] = temp;

        swapped = false;
      }
    }

     
    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ặpSố lượng phép so sánh1(n-1)2(n-2)3(n-3)…….……Cuối cùng1

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

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

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 = n2.

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

Trường hợp xấu nhất: O(n2)
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(n2)
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.

Tóm Tắt

Thuật toán sắp xếp nổi bọt – Bubble Sort | Học lập trình JavaScript

Chia sẻ

Bài viết liên quan

mtoplist