So sánh các thuật toán sắp xếp
Không có thuật toán sắp xếp nào luôn nhanh nhất. Có thuật toán đơn giản nhưng chậm, có thuật toán nhanh với dữ liệu ngẫu nhiên nhưng vấp với dữ liệu đã sắp xếp, và có thuật toán hoàn toàn không phải sắp xếp so sánh. Cho cả tám đua trên cùng một danh sách sẽ thấy ngay sự khác biệt.
Ba nhóm
Sắp xếp nổi bọt, chọn và chèn là các thuật toán đơn giản. Chúng so sánh và hoán đổi các giá trị gần nhau và cần thời gian tỉ lệ với n² trên danh sách ngẫu nhiên. Sắp xếp trộn, nhanh và vun đống chia công việc một cách khéo léo và cần thời gian tỉ lệ với n log n, mức tốt nhất mà một thuật toán có thể đạt khi nó chỉ được hỏi giá trị nào trong hai giá trị lớn hơn. Sắp xếp theo cơ số và sắp xếp đếm bỏ qua hẳn câu hỏi đó: chúng dùng chính các chữ số hoặc giá trị, điều chỉ áp dụng được cho các khóa như số nguyên nhỏ.
Đo khối lượng công việc
Cuộc đua sắp xếp tính một thao tác cho mỗi phép so sánh, mỗi lần đọc chữ số hoặc giá trị, và mỗi lần hoán đổi hoặc di chuyển. Với 40 giá trị ngẫu nhiên, con số là khoảng 120 cho sắp xếp đếm, 240 cho sắp xếp theo cơ số, 260 cho sắp xếp nhanh, 380 cho sắp xếp trộn, 490 cho sắp xếp vun đống, khoảng 820 mỗi thuật toán cho sắp xếp chọn và sắp xếp chèn, và hơn 1.100 cho sắp xếp nổi bọt. Máy tính thật còn phụ thuộc vào bộ nhớ: trong thực tế sắp xếp nhanh thường nhanh hơn con số của nó gợi ý, còn sắp xếp vun đống chậm hơn, do cách chúng di chuyển qua danh sách.
Dữ liệu đầu vào quan trọng
Trên danh sách gần như đã sắp xếp, với 40 giá trị, sắp xếp chèn chỉ cần khoảng 50 thao tác và sắp xếp nổi bọt khoảng 90, vì mỗi giá trị đều gần vị trí của nó. Trên danh sách đảo ngược, cả hai cùng cần 1.560, trường hợp xấu nhất của chúng. Sắp xếp chọn, vun đống, trộn, theo cơ số và đếm hầu như không bị ảnh hưởng bởi thứ tự. Sắp xếp nhanh dùng trung vị của ba xử lý tốt danh sách đã sắp xếp và đảo ngược, nhưng với cách chọn chốt đơn giản thì danh sách đã sắp xếp lại là trường hợp xấu nhất. Ít giá trị khác nhau làm sắp xếp nhanh chậm lại, vì các giá trị bằng nhau đều dồn về một phía.
Bộ nhớ và tính ổn định
Sắp xếp nổi bọt, chọn, chèn, nhanh và vun đống làm việc tại chỗ, với ít hoặc không cần bộ nhớ thêm. Sắp xếp trộn, theo cơ số và đếm cần một bộ đệm dài bằng danh sách. Thuật toán sắp xếp ổn định giữ các giá trị bằng nhau theo thứ tự ban đầu: sắp xếp nổi bọt, chèn, trộn, theo cơ số và đếm là ổn định, còn sắp xếp chọn, nhanh và vun đống thì không. Tính ổn định quan trọng khi bạn sắp xếp các bản ghi lần lượt theo từng trường.
Nên dùng thuật toán nào
Trong thực tế, bạn dùng hàm sắp xếp có sẵn trong ngôn ngữ lập trình: thường là Timsort, một dạng sắp xếp trộn dùng sắp xếp chèn cho các đoạn ngắn và nhanh với dữ liệu đã sắp xếp một phần, hoặc introsort, một dạng sắp xếp nhanh chuyển sang sắp xếp vun đống khi cần và dùng sắp xếp chèn cho các phần nhỏ. Với nhiều khóa là số nguyên nhỏ, sắp xếp đếm hoặc sắp xếp theo cơ số có thể nhanh hơn cả hai. Sắp xếp nổi bọt và sắp xếp chọn chủ yếu là công cụ giảng dạy.
Khám phá
Mở cuộc đua sắp xếp và nhấn Phát. Mỗi làn là một thuật toán trên cùng một danh sách; con số bên phải đếm số thao tác của nó, và làn chuyển xanh lá khi xong. Thử danh sách gần như đã sắp xếp, danh sách đảo ngược và danh sách ít giá trị khác nhau, rồi xem thứ tự về đích thay đổi. Mỗi thuật toán còn có ứng dụng riêng, nơi bạn có thể đi qua từng bước chi tiết.
Câu hỏi thường gặp
Thuật toán sắp xếp nhanh nhất là gì?
Với dữ liệu thông thường, sắp xếp nhanh và sắp xếp trộn (cùng các thuật toán lai dựa trên chúng, như introsort và Timsort) nhanh nhất trung bình, ở mức n log n. Với khóa là số nguyên nhỏ, sắp xếp đếm và sắp xếp theo cơ số còn nhanh hơn. Với danh sách ngắn hoặc gần như đã sắp xếp, sắp xếp chèn thắng.
Vì sao không sắp xếp so sánh nào vượt được n log n?
Một danh sách n giá trị có thể có n! thứ tự, và mỗi phép so sánh có hai kết quả, nên trong trường hợp xấu nhất cần ít nhất log₂(n!) phép so sánh để phân biệt tất cả. Con số đó khoảng n log₂ n. Sắp xếp theo cơ số và sắp xếp đếm tránh được giới hạn này vì chúng không so sánh.
Thuật toán sắp xếp nào ổn định?
Sắp xếp nổi bọt, chèn, trộn, theo cơ số và đếm ổn định ở dạng thông thường. Sắp xếp chọn, sắp xếp nhanh và sắp xếp vun đống thì không, vì chúng di chuyển giá trị đi xa.
Thuật toán nào cần thêm bộ nhớ?
Sắp xếp trộn, theo cơ số và đếm cần một bộ đệm dài khoảng bằng danh sách. Sắp xếp nổi bọt, chọn, chèn và vun đống gần như không cần, còn sắp xếp nhanh chỉ cần một ít cho đệ quy.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Bắt đầu cuộc đua sắp xếp