Thuật toán JavaScript: Sắp xếp bong bóng

Sắp xếp bong bóng là một thuật toán đơn giản để sắp xếp, nhưng nó cũng khá kém hiệu quả, vì trường hợp xấu nhất của nó làO(n^2)sự phức tạp.

Nhưng nó đáng để học hỏi về nó.

Chúng tôi lặp qua một mảng và chúng tôi tiếp tục so sánh một mục với một mục ngay bên cạnh nó.

Nếu mục bên phải nhỏ hơn, chúng tôi hoán đổi hai vị trí.

Đây là cách triển khai của chúng tôi:

const bubbleSort = (originalArray) => {
  let swapped = false

const a = […originalArray]

for (let i = 1; i < a.length - 1; i++) { swapped = false

<span style="color:#66d9ef">for</span> (<span style="color:#66d9ef">let</span> <span style="color:#a6e22e">j</span> <span style="color:#f92672">=</span> <span style="color:#ae81ff">0</span>; <span style="color:#a6e22e">j</span> <span style="color:#f92672">&lt;</span> <span style="color:#a6e22e">a</span>.<span style="color:#a6e22e">length</span> <span style="color:#f92672">-</span> <span style="color:#a6e22e">i</span>; <span style="color:#a6e22e">j</span><span style="color:#f92672">++</span>) {
  <span style="color:#66d9ef">if</span> (<span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>] <span style="color:#f92672">&lt;</span> <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span>]) {
    ;[<span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span>], <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>]] <span style="color:#f92672">=</span> [<span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span> <span style="color:#f92672">+</span> <span style="color:#ae81ff">1</span>], <span style="color:#a6e22e">a</span>[<span style="color:#a6e22e">j</span>]]
    <span style="color:#a6e22e">swapped</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">true</span>
  }
}

<span style="color:#66d9ef">if</span> (<span style="color:#f92672">!</span><span style="color:#a6e22e">swapped</span>) {
  <span style="color:#66d9ef">return</span> <span style="color:#a6e22e">a</span>
}

}

return a }

Bạn có thể nhìn thấyO(n^2)xuất phát từ thực tế là chúng ta đang lặp lại mảng 2 lần, để kiểm tra xem chúng ta có cần hoán đổi mục với mục ở bên phải hay không.

Chúng tôi bắt đầu với phần tử đầu tiên và so sánh nó với phần tử thứ hai. Nếu cái đầu tiên lớn hơn, chúng tôi hoán đổi chúng. Nếu không, chúng ta để nguyên nó và chuyển sang phần tử thứ hai của mảng. Chúng tôi so sánh nó với thứ ba. Một lần nữa, nếu cái thứ 2 lớn hơn cái thứ 3, chúng ta hoán đổi chúng và tiếp tục hoán đổi cho đến khi nó tìm thấy vị trí của nó trong mảng.

Đây là một ví dụ:

Giả sử chúng ta chạybubbleSort([2, 1, 3]).

Đầu tiên, chúng tôi so sánh 2 với 1. 2 là> 1, vì vậy chúng tôi hoán đổi chúng:

1 2 3

then we compare 2 with 3. 2 < 3, so we leave it as-is. We skip the last element, since we know that due to our workflow, it’s always going to be the biggest element.


More js tutorials: