Là một lập trình viên mới làm quen, bạn có thể đã nghe đến thuật ngữ “thuật toán sắp xếp” nhưng không biết nó là gì hoặc nó hoạt động như thế nào. Vậy thì đừng sợ! Trong bài viết này, chúng ta sẽ đi sâu vào một trong những thuật toán sắp xếp cơ bản nhất, sắp xếp bong bóng.
Nhưng trước khi tìm hiểu cách hoạt động của sắp xếp bong bóng, trước tiên chúng ta hãy định nghĩa nó là gì. Nói một cách đơn giản, sắp xếp bong bóng là một thuật toán so sánh các phần tử liền kề trong một mảng và hoán đổi vị trí của chúng nếu chúng không theo đúng thứ tự. Tiếp tục làm điều này cho đến khi mảng được sắp xếp hoàn toàn.
Bây giờ bạn đã có hiểu biết cơ bản về sắp xếp bong bóng, hãy xem cách nó hoạt động với một ví dụ. Giả sử chúng ta cần sắp xếp một dãy số từ nhỏ nhất đến lớn nhất: [5, 2, 1, 4, 3] .
Sử dụng sắp xếp bong bóng, trước tiên hãy so sánh hai phần tử đầu tiên, 5 và 2. Vì 5 lớn hơn 2 nên hoán đổi vị trí của chúng. Mảng trông như thế này: [2, 5, 1, 4, 3] .
Sau đó, so sánh các phần tử thứ hai và thứ ba, 5 và 1. Vì 5 lớn hơn 1 nên ta hoán đổi vị trí của chúng. Mảng trông như thế này: [2, 1, 5, 4, 3] .
Tiếp tục quá trình này cho đến hết mảng. Bước cuối cùng là so sánh phần tử thứ 4 và thứ 5, 4 và 3. Vì 4 lớn hơn 3 nên hoán đổi vị trí của chúng. Mảng hoán vị cuối cùng trông như thế này: [1, 2, 3, 4, 5] .
Đó là tất cả để hiểu rõ hơn về cách thức hoạt động của sắp xếp bong bóng. Bây giờ hãy xem xét một số ví dụ về việc sử dụng thuật toán này một cách thực tế trong JavaScript.
thí dụ
sắp xếp tên theo thứ tự bảng chữ cái
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | <span class="token keyword">const</span> <span class="token function-variable function">sortNames</span> <span class="token operator">=</span> <span class="token parameter">names</span> <span class="token operator">=></span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator"><</span> names <span class="token punctuation">.</span> length <span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> j <span class="token operator"><</span> names <span class="token punctuation">.</span> length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> j <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> names <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">></span> names <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Swap names[j] and names[j + 1]</span> <span class="token keyword">let</span> temp <span class="token operator">=</span> names <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">;</span> names <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">=</span> names <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> names <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token operator">=</span> temp <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> names <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">;</span> <span class="token keyword">const</span> names <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token string">'John'</span> <span class="token punctuation">,</span> <span class="token string">'Bob'</span> <span class="token punctuation">,</span> <span class="token string">'Sue'</span> <span class="token punctuation">,</span> <span class="token string">'Alice'</span> <span class="token punctuation">,</span> <span class="token string">'Zack'</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">sortNames</span> <span class="token punctuation">(</span> names <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// ['Alice', 'Bob', 'John', 'Sue', 'Zack']</span> |
Sắp xếp các số từ nhỏ nhất đến lớn nhất
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | <span class="token keyword">const</span> <span class="token function-variable function">sortNumbers</span> <span class="token operator">=</span> <span class="token parameter">numbers</span> <span class="token operator">=></span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator"><</span> numbers <span class="token punctuation">.</span> length <span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> j <span class="token operator"><</span> numbers <span class="token punctuation">.</span> length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> j <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> numbers <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">></span> numbers <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Swap numbers[j] and numbers[j + 1]</span> <span class="token keyword">let</span> temp <span class="token operator">=</span> numbers <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">;</span> numbers <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">=</span> numbers <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> numbers <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token operator">=</span> temp <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> numbers <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">;</span> |
Sắp xếp sản phẩm theo giá
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | <span class="token keyword">const</span> <span class="token function-variable function">sortProducts</span> <span class="token operator">=</span> <span class="token parameter">products</span> <span class="token operator">=></span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator"><</span> products <span class="token punctuation">.</span> length <span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> j <span class="token operator"><</span> products <span class="token punctuation">.</span> length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> j <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> products <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">.</span> price <span class="token operator">></span> products <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">.</span> price <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Swap products[j] and products[j + 1]</span> <span class="token keyword">let</span> temp <span class="token operator">=</span> products <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">;</span> products <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">=</span> products <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> products <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token operator">=</span> temp <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> products <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">;</span> <span class="token keyword">const</span> products <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">'Product A'</span> <span class="token punctuation">,</span> price <span class="token operator">:</span> <span class="token number">9.99</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">'Product B'</span> <span class="token punctuation">,</span> price <span class="token operator">:</span> <span class="token number">7.99</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">'Product C'</span> <span class="token punctuation">,</span> price <span class="token operator">:</span> <span class="token number">12.99</span> <span class="token punctuation">}</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">sortProducts</span> <span class="token punctuation">(</span> products <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// [{ name: 'Product B', price: 7.99 }, { name: 'Product A', price: 9.99 }, { name: 'Product C', price: 12.99 }]</span> |
Sắp xếp nhân viên theo chức danh công việc
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | <span class="token keyword">const</span> <span class="token function-variable function">sortEmployees</span> <span class="token operator">=</span> <span class="token punctuation">(</span> <span class="token parameter">employees</span> <span class="token punctuation">)</span> <span class="token operator">=></span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator"><</span> employees <span class="token punctuation">.</span> length <span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> j <span class="token operator"><</span> employees <span class="token punctuation">.</span> length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> j <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> employees <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">.</span> jobTitle <span class="token operator">></span> employees <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">.</span> jobTitle <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Swap employees[j] and employees[j + 1]</span> <span class="token keyword">let</span> temp <span class="token operator">=</span> employees <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">;</span> employees <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">=</span> employees <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> employees <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token operator">=</span> temp <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> employees <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">;</span> <span class="token keyword">const</span> employees <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"John"</span> <span class="token punctuation">,</span> jobTitle <span class="token operator">:</span> <span class="token string">"Manager"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"Sue"</span> <span class="token punctuation">,</span> jobTitle <span class="token operator">:</span> <span class="token string">"Developer"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"Alice"</span> <span class="token punctuation">,</span> jobTitle <span class="token operator">:</span> <span class="token string">"Designer"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"Bob"</span> <span class="token punctuation">,</span> jobTitle <span class="token operator">:</span> <span class="token string">"Salesperson"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">sortEmployees</span> <span class="token punctuation">(</span> employees <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// [</span> <span class="token comment">// { name: 'Alice', jobTitle: 'Designer' },</span> <span class="token comment">// { name: 'Sue', jobTitle: 'Developer' },</span> <span class="token comment">// { name: 'John', jobTitle: 'Manager' },</span> <span class="token comment">// { name: 'Bob', jobTitle: 'Salesperson' }</span> <span class="token comment">// ]</span> |
Sắp xếp các thành phố theo dân số
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | <span class="token keyword">const</span> <span class="token function-variable function">sortCities</span> <span class="token operator">=</span> <span class="token punctuation">(</span> <span class="token parameter">cities</span> <span class="token punctuation">)</span> <span class="token operator">=></span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> i <span class="token operator"><</span> cities <span class="token punctuation">.</span> length <span class="token punctuation">;</span> i <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">for</span> <span class="token punctuation">(</span> <span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> j <span class="token operator"><</span> cities <span class="token punctuation">.</span> length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> j <span class="token operator">++</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> cities <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">.</span> population <span class="token operator">></span> cities <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">.</span> population <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token comment">// Swap cities[j] and cities[j + 1]</span> <span class="token keyword">let</span> temp <span class="token operator">=</span> cities <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">;</span> cities <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token operator">=</span> cities <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> cities <span class="token punctuation">[</span> j <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">]</span> <span class="token operator">=</span> temp <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> cities <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">;</span> <span class="token keyword">const</span> cities <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"New York"</span> <span class="token punctuation">,</span> population <span class="token operator">:</span> <span class="token number">8175133</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"Los Angeles"</span> <span class="token punctuation">,</span> population <span class="token operator">:</span> <span class="token number">3792621</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"Chicago"</span> <span class="token punctuation">,</span> population <span class="token operator">:</span> <span class="token number">2695598</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> name <span class="token operator">:</span> <span class="token string">"Houston"</span> <span class="token punctuation">,</span> population <span class="token operator">:</span> <span class="token number">2130332</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">sortCities</span> <span class="token punctuation">(</span> cities <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// [</span> <span class="token comment">// { name: 'Houston', population: 2130332 },</span> <span class="token comment">// { name: 'Chicago', population: 2695598 },</span> <span class="token comment">// { name: 'Los Angeles', population: 3792621 },</span> <span class="token comment">// { name: 'New York', population: 8175133 }</span> <span class="token comment">// ]</span> |
Hiệu suất sắp xếp bong bóng và những hạn chế
Bây giờ chúng ta đã thấy một số ví dụ thực tế về việc sử dụng sắp xếp bong bóng trong JavaScript, hãy nói về hiệu suất và những hạn chế của thuật toán này.
Một trong những hạn chế chính của sắp xếp bong bóng là độ phức tạp về thời gian của nó. Cụ thể, sắp xếp bong bóng có độ phức tạp thời gian là O(n^2) và chậm hơn khi kích thước của đầu vào tăng lên. Đây không phải là tùy chọn hiệu quả hơn để sắp xếp các danh sách lớn.
Tuy nhiên, sắp xếp bong bóng có một số lợi thế. Đây là một thuật toán đơn giản, dễ hiểu và là một lựa chọn tốt cho người mới bắt đầu. Nó cũng có tính năng sắp xếp ổn định giúp duy trì thứ tự tương đối của các phần tử có khóa bằng nhau.
Phần kết luận
Tóm lại, sắp xếp bong bóng là một thuật toán đơn giản và dễ hiểu giúp bạn sắp xếp các danh sách nhỏ. Nó không phải là thuật toán hiệu quả nhất để sắp xếp các danh sách lớn, nhưng nó vẫn có thể là một công cụ hữu ích trong một số trường hợp nhất định. Hãy nhớ lưu ý đến độ phức tạp của thời gian khi quyết định có sử dụng thuật toán này hay không.
Như mọi khi, tôi hy vọng bạn thích bài viết này và học được điều gì đó mới.
Cảm ơn rất nhiều. Hẹn gặp lại các bạn trong bài viết tiếp theo!
Nếu các bạn thích bài viết này, hãy ủng hộ chúng tôi bằng cách like và subscribe. Cảm ơn rất nhiều.