Là một lập trình viên mới bắt đầu, bạn có thể đã nghe nói đến thuật ngữ “thuật toán sắp xếp” nhưng không biết chúng là gì hoặc chúng hoạt động như thế nào. Chà, đừ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 hiện có: sắp xếp bong bóng.
Nhưng trước khi chúng ta tìm hiểu chi tiết về cách thức hoạt động của sắp xếp bong bóng, trước tiên chúng ta hãy xác định 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ự. Nó tiếp tục làm điều này cho đến khi mảng được sắp xếp đầy đủ.
Bây giờ chúng ta đã 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ó một dãy số mà chúng ta muốn sắp xếp 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 chúng ta sẽ so sánh hai phần tử đầu tiên, 5 và 2. Vì 5 lớn hơn 2, chúng ta sẽ hoán đổi vị trí của chúng. Mảng bây giờ sẽ trông như thế này: [2, 5, 1, 4, 3] .
Tiếp theo, chúng ta sẽ so sánh phần tử thứ hai và phần tử thứ ba, 5 và 1. Vì 5 lớn hơn 1 nên chúng ta sẽ hoán đổi vị trí của chúng. Mảng bây giờ sẽ trông như thế này: [2, 1, 5, 4, 3] .
Chúng tôi sẽ tiếp tục quá trình này cho đến khi chúng tôi đến cuối mảng. Bước cuối cùng sẽ là so sánh phần tử thứ tư và phần tử thứ năm, 4 và 3. Vì 4 lớn hơn 3 nên chúng ta sẽ hoán đổi vị trí của chúng. Mảng cuối cùng được sắp xếp sẽ trông như thế này: [1, 2, 3, 4, 5] .
Vì vậy, bây giờ bạn đã hiểu rõ hơn về cách hoạt động của sắp xếp bong bóng, chúng ta hãy xem một số trường hợp sử dụng trong thế giới thực cho thuật toán này trong JavaScript bằng cách tiếp cận hướng chức năng.
Ví dụ
Sắp xếp danh sách 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 danh sách 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 danh sách 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 danh sách 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 danh sách các thành phố theo dân số của họ
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 và Hạn chế của Sắp xếp Bong bóng
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 về thời gian là O(n^2) , nghĩa là nó ngày càng trở nên chậm hơn khi kích thước của đầu vào tăng lên. Điều này làm cho nó trở thành một tùy chọn kém 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 ích. Nó là một thuật toán đơn giản và dễ hiểu, làm cho nó trở thành một lựa chọn tốt cho người mới bắt đầu. Nó cũng là một sắp xếp ổn định, nghĩa là nó bảo toàn 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 có thể hữu ích để sắp xếp các danh sách nhỏ. Mặc dù nó không phải là thuật toán hiệu quả nhất cho các danh sách lớn hơ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 về thời gian của nó khi quyết định có sử dụng sắp xếp bong bóng cho nhu cầu sắp xếp của bạn 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. Xin cảm ơn và hẹn gặp lại các bạn trong những bài viết tiếp theo!
Nếu các bạn thích bài viết này thì hãy cho mình 1 like và subscribe để ủng hộ mình nhé. Cảm ơn bạn.