Thuật toán sắp xếp — So sánh Bubble Sort, Merge Sort và Quick Sort

Thuật toán sắp xếp là cách sắp lại chính các phần tử đó theo một thứ tự nhất định, chẳng hạn từ nhỏ đến lớn. Nếu muốn câu trả lời ngắn gọn trước, thì bubble sort đơn giản nhưng thường quá chậm với danh sách lớn, merge sort cho hiệu năng $O(n \log n)$ ổn định, còn quick sort thường chạy nhanh trong thực tế khi các lần chia phần tương đối cân bằng.

Câu hỏi đúng không phải là "thuật toán sắp xếp nào tốt nhất?" mà là "tốt nhất trong điều kiện nào?" Bubble sort giúp minh họa các phép đổi chỗ cục bộ, merge sort thể hiện rõ chiến lược chia để trị, còn quick sort cho thấy vì sao tốc độ trung bình có thể rất tốt ngay cả khi không có đảm bảo ở trường hợp xấu nhất.

Thuật Toán Sắp Xếp Làm Gì

Với một danh sách như $[5, 1, 4, 2]$, thuật toán cần trả về đúng các giá trị đó nhưng theo thứ tự:

$$[1, 2, 4, 5]$$

Nghe có vẻ đơn giản, nhưng các thuật toán khác nhau lại đạt kết quả đó theo những cách rất khác nhau. Những khác biệt chính là:

• cách chúng di chuyển các phần tử
• số lượng phép so sánh hoặc đổi chỗ mà chúng thường dùng
• lượng bộ nhớ bổ sung mà chúng cần
• mức độ nhạy với các mẫu đầu vào xấu

Bubble Sort: Đổi Chỗ Các Phần Tử Kề Nhau Nhiều Lần

Bubble sort đi qua danh sách và đổi chỗ hai phần tử liền kề nếu chúng đang sai thứ tự. Sau một lượt duyệt đầy đủ, phần tử lớn nhất trong phần chưa sắp xếp sẽ "nổi" về cuối.

Với $[5, 1, 4, 2]$, lượt đầu tiên trông như sau:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Sau đó nó lặp lại trên phần còn chưa sắp xếp cho đến khi không cần đổi chỗ nữa.

Bubble sort chủ yếu hữu ích cho việc học. Nói chung, nó có độ phức tạp thời gian $O(n^2)$, nên số phép so sánh tăng rất nhanh khi danh sách lớn hơn. Với các ví dụ nhỏ trong lớp học thì điều đó không sao. Nhưng với các bài toán sắp xếp thực tế, nó thường không phải lựa chọn phù hợp.

Merge Sort: Chia Nhỏ, Sắp Xếp, Rồi Trộn Lại

Merge sort dùng ý tưởng chia để trị. Nó chia danh sách thành các phần nhỏ hơn, sắp xếp từng phần, rồi trộn các phần đã sắp xếp lại với nhau.

Với $[5, 1, 4, 2]$, một cách nhìn gọn gàng là:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Sắp xếp từng nửa:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Sau đó trộn hai nửa đã sắp xếp:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Điểm mạnh chính của merge sort là tính ổn định và dễ dự đoán. Thời gian chạy của nó là $O(n \log n)$ trong phân tích thông thường, không chỉ đúng ở trung bình. Chi phí chính là bộ nhớ: các cách cài đặt phổ biến trên mảng dùng thêm không gian trong lúc trộn.

Quick Sort: Phân Hoạch Quanh Một Pivot

Quick sort cũng dùng chia để trị, nhưng theo cách khác. Nó chọn một pivot, đưa các phần tử nhỏ hơn sang một phía và các phần tử lớn hơn sang phía còn lại, rồi sắp xếp đệ quy hai phía đó.

Dùng pivot $4$ trên $[5, 1, 4, 2]$, một cách phân hoạch có thể là:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Lúc này phần bên trái và bên phải đều nhỏ hơn nhiều, nên việc sắp xếp kết thúc nhanh.

Quick sort thường nhanh trong thực tế vì nhiều cách cài đặt phân hoạch ngay trên chỗ và làm bài toán nhỏ đi rất nhanh khi pivot chia danh sách khá đều. Nhưng điều kiện đó rất quan trọng. Nếu việc chọn pivot liên tục kém, chẳng hạn cứ tạo ra một phía rất nhỏ và một phía gần như đầy lặp đi lặp lại, thì trường hợp xấu nhất sẽ thành $O(n^2)$.

Bubble Sort vs Merge Sort vs Quick Sort

Thuật toán	Ý tưởng cốt lõi	Thời gian điển hình	Thời gian trường hợp xấu nhất	Bộ nhớ bổ sung
Bubble sort	Đổi chỗ các phần tử kề nhau lặp lại	$O(n^2)$	$O(n^2)$	Thấp
Merge sort	Chia đôi, sắp xếp từng nửa, rồi trộn	$O(n \log n)$	$O(n \log n)$	Cao hơn trong các cài đặt mảng phổ biến
Quick sort	Phân hoạch quanh một pivot	Thường là $O(n \log n)$	$O(n^2)$	Thường thấp hơn merge sort

Nếu muốn rút ra một ý thực tế, thì đó là: bubble sort là thuật toán để giảng dạy, merge sort là lựa chọn ổn định và dễ dự đoán, còn quick sort thường là lựa chọn nhanh trong thực tế khi cách cài đặt xử lý pivot tốt.

Một Ví Dụ Cụ Thể Trên Cùng Một Danh Sách

Dùng cùng danh sách:

$$[5, 1, 4, 2]$$

Bubble sort liên tục sửa các sai sót cục bộ. Nó không "nhìn thấy" toàn bộ cấu trúc, nên có thể cần nhiều lượt duyệt.

Merge sort trước hết tách bài toán thành các phần nhỏ đã được sắp xếp, rồi kết hợp chúng lại. Cấu trúc đó là lý do hiệu năng của nó vẫn ổn định khi danh sách lớn dần.

Quick sort cố tạo ra một lần chia mạnh ngay từ đầu. Nếu lần chia đủ cân bằng, phần việc còn lại sẽ giảm rất nhanh.

Đó là lý do sinh viên thường nhớ các con số độ phức tạp tốt hơn sau khi quan sát một danh sách đi qua từng phương pháp. Những con số đó không phải các nhãn tùy ý. Chúng phản ánh cách thuật toán làm giảm sự lộn xộn.

Những Sai Lầm Thường Gặp Khi So Sánh Các Thuật Toán Sắp Xếp

Cho Rằng Quick Sort Luôn Nhanh Hơn

Quick sort thường nhanh trong thực tế, chứ không được đảm bảo là nhanh nhất trong mọi trường hợp. Việc chọn pivot tệ có thể làm nó chậm đi rất nhiều.

Xem Mọi Thuật Toán $O(n \log n)$ Là Giống Nhau

Merge sort và quick sort có thể cùng có tốc độ tăng trưởng trung bình như nhau nhưng vẫn khác nhau về cách dùng bộ nhớ, đảm bảo ở trường hợp xấu nhất, hoặc chi tiết cài đặt.

Dùng Bubble Sort Chỉ Vì Nó Dễ Viết Mã

Dễ viết mã không đồng nghĩa với phù hợp. Với các ví dụ minh họa rất nhỏ thì bubble sort ổn. Nhưng với đầu vào thực tế lớn hơn, nó thường làm nhiều việc không cần thiết.

Quên Mô Hình Đầu Vào

Các so sánh này thường giả sử việc sắp xếp dựa trên so sánh với đầu vào tổng quát. Nếu dữ liệu có cấu trúc đặc biệt, các thuật toán không dựa trên so sánh như counting sort có thể làm thay đổi hoàn toàn quyết định.

Khi Nào Dùng Từng Thuật Toán Sắp Xếp

Bubble sort chủ yếu được dùng để giảng dạy, truy vết từng bước, và các ví dụ rất nhỏ nơi tính rõ ràng quan trọng hơn hiệu năng.

Merge sort được dùng khi cần hành vi $O(n \log n)$ ổn định và có thể chấp nhận thêm bộ nhớ. Nó cũng phù hợp tự nhiên với danh sách liên kết và với các tình huống cần sắp xếp ổn định, tùy theo cách cài đặt.

Quick sort được dùng khi tốc độ thực tế là quan trọng và cách cài đặt có chiến lược chọn pivot tốt hoặc có cơ chế bảo vệ dự phòng. Nhiều chiến lược sắp xếp trong thư viện chuẩn dùng ý tưởng của quick sort kết hợp với các biện pháp an toàn, thay vì phiên bản sách giáo khoa đơn giản.

Cách Nhanh Để Nhớ Sự Khác Biệt

Hãy nhớ chúng qua chuyển động:

• bubble sort sửa các phần tử kề nhau
• merge sort xây dựng các nửa đã sắp xếp
• quick sort chia quanh một pivot

Hình dung đó hữu ích hơn việc chỉ học thuộc ba cái tên và ba công thức.

Tự Thử Một Phiên Bản Của Bạn

Lấy danh sách $[7, 3, 6, 1]$ và lần theo một lượt của bubble sort, một chu kỳ chia-và-trộn của merge sort, và một lần phân hoạch theo pivot của quick sort. Nếu bạn có thể giải thích vì sao danh sách thay đổi khác nhau trong từng trường hợp, thì bạn đã thực sự hiểu khái niệm.