- Phần đang trộn
- Đang so sánh
- Đã ghi lại
- Đã trộn
Sắp xếp trộn
Sắp xếp trộn là thuật toán chia để trị. Nó chia đôi danh sách, sắp xếp từng nửa theo cùng cách đó, rồi trộn hai nửa đã sắp xếp bằng cách liên tục lấy giá trị đầu nhỏ hơn. Xem các nửa được đưa vào hàng bộ đệm rồi ghi lại theo thứ tự, ở tốc độ bất kỳ hoặc từng bước, và đếm số phép so sánh, lần ghi và lần trộn. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Các ô đếm số phép so sánh, số lần ghi lại vào danh sách và số lần trộn. Chọn số cột, thứ tự ban đầu, hoặc tự nhập các số. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chọn số cột và thứ tự ban đầu: ngẫu nhiên, gần như đã sắp xếp, đảo ngược, hoặc ít giá trị khác nhau. Hoặc tự nhập các số.
- Nhấn Phát, hoặc dùng Bước và Lùi để đi từng bước. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình sắp xếp.
- Theo dõi mỗi lần trộn: hai nửa đã sắp xếp đi xuống bộ đệm, và giá trị đầu nhỏ hơn đi lên lại, từng giá trị một.
Cách sắp xếp trộn hoạt động
Một giá trị đơn lẻ vốn đã được sắp xếp. Với danh sách dài hơn, chia nó thành hai nửa và sắp xếp từng nửa bằng sắp xếp trộn. Rồi trộn chúng: xem giá trị đầu của mỗi nửa, chuyển giá trị nhỏ hơn vào kết quả, và lặp lại cho đến khi cả hai nửa đều trống. Vì cả hai nửa đã được sắp xếp, kết quả cũng được sắp xếp.
Luôn là n log n
Chia đôi lặp đi lặp lại tạo ra khoảng log₂ n tầng, và mỗi tầng trộn ghi mỗi giá trị một lần, nên phép sắp xếp thực hiện khoảng n log₂ n lần ghi, và số phép so sánh nhiều nhất cũng chừng ấy. Khác với sắp xếp nổi bọt, sắp xếp chọn và sắp xếp chèn, con số này không tăng theo n², và thứ tự của danh sách ít ảnh hưởng hơn nhiều. Cái giá là một bộ đệm dài bằng danh sách. Sắp xếp trộn cũng ổn định, vì thế nó là nền tảng của các hàm sắp xếp trong Python và Java.
Câu hỏi thường gặp
Sắp xếp trộn hoạt động thế nào?
Nó chia đôi danh sách, sắp xếp từng nửa bằng sắp xếp trộn, rồi trộn hai nửa đã sắp xếp bằng cách liên tục lấy giá trị nhỏ hơn trong hai giá trị đầu. Danh sách một giá trị vốn đã được sắp xếp, nên việc chia dừng ở đó.
Sắp xếp trộn thực hiện bao nhiêu phép so sánh?
Với n giá trị, nhiều nhất khoảng n log₂ n − n + 1, và ít nhất khoảng một nửa n log₂ n. Với 40 giá trị, con số đó nhiều nhất là 177. Số lần ghi lại vào danh sách luôn như nhau với cùng một n: mỗi giá trị một lần ở mỗi tầng trộn.
Vì sao sắp xếp trộn cần thêm bộ nhớ?
Trộn hai nửa ngay tại chỗ rất khó làm nhanh, nên sắp xếp trộn thông thường chép các nửa vào bộ đệm rồi ghi lại theo thứ tự. Bộ đệm dài bằng danh sách, đó là nhược điểm chính so với sắp xếp nhanh và sắp xếp vun đống.
Sắp xếp trộn có ổn định không?
Có. Khi hai giá trị đầu bằng nhau, giá trị từ nửa trái được lấy trước, nên các giá trị bằng nhau giữ nguyên thứ tự ban đầu.
Các số của tôi có bị gửi đi đâu không?
Không. Việc sắp xếp chạy trong trình duyệt của bạn, và cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
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.
Tới trình chỉnh sửa