- Đang so sánh
- Đánh dấu (nhỏ nhất, chốt hoặc khóa)
- Vừa hoán đổi hoặc di chuyển
- Đã đúng chỗ
| Hạng | Thuật toán | So sánh hoặc đọc | Hoán đổi hoặc di chuyển | Thao tác |
|---|
Cuộc đua sắp xếp
Thuật toán sắp xếp nào nhanh nhất? Còn tùy danh sách. Cuộc đua sắp xếp chạy cả tám thuật toán sắp xếp trên cùng một danh sách cùng lúc, mỗi thuật toán một làn, và tính mỗi phép so sánh, lần đọc, hoán đổi và di chuyển là một thao tác. Các làn tiến lên khi số đếm tăng, nên bạn có thể thấy các thuật toán hiệu quả về đích trong khi các thuật toán chậm vẫn đang hoán đổi, và thấy thứ hạng thay đổi khi danh sách gần như đã sắp xếp hoặc bị đảo ngược. Nhấn Phát để xem cả tám thuật toán sắp xếp đua trên cùng một danh sách, hoặc Bước và Lùi để đi từng thao tác. Kéo thanh trượt để nhảy đến bất kỳ đâu. Mỗi phép so sánh, lần đọc, hoán đổi hoặc di chuyển tính là một thao tác, và mỗi làn tiến lên khi số đếm của chính nó tăng, nên thuật toán cần ít thao tác nhất sẽ về đích trước. Chọn số cột và 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 và theo dõi tám làn. Bước và Lùi đi từng thao tác; thanh trượt nhảy đến bất kỳ đâu trong cuộc đua.
- So sánh bảng kết quả, rồi thử một danh sách gần như đã sắp xếp và một danh sách đảo ngược để thấy thứ hạng thay đổi.
Cuộc đua diễn ra thế nào
Cả tám thuật toán nhận cùng một danh sách. Mỗi phép so sánh hai giá trị, mỗi chữ số hoặc giá trị mà sắp xếp theo cơ số và sắp xếp đếm đọc, và mỗi lần hoán đổi hoặc di chuyển đều tính là một thao tác. Tại mỗi thời điểm của cuộc đua, mỗi làn cho thấy thuật toán của nó đã đi được bao xa với chừng ấy thao tác. Thuật toán cần ít thao tác hơn sẽ về đích sớm hơn. Bảng kết quả liệt kê số phép so sánh, số lần hoán đổi hoặc di chuyển, và tổng của từng thuật toán.
Kết quả cho thấy gì
Với 40 giá trị ngẫu nhiên, sắp xếp đếm cần khoảng 120 thao tác, sắp xếp theo cơ số khoảng 240, sắp xếp nhanh khoảng 260 và sắp xếp trộn khoảng 380. Tiếp theo là sắp xếp vun đống với khoảng 490, còn sắp xếp chọn và sắp xếp chèn cần khoảng 820 và sắp xếp nổi bọt hơn 1.100. Trên danh sách gần như đã sắp xếp, sắp xếp chèn thắng với khoảng 50, và sắp xếp nổi bọt về nhì. Trên danh sách đảo ngược, cả sắp xếp nổi bọt và sắp xếp chèn đều cần 1.560. Sắp xếp đếm và sắp xếp theo cơ số thắng thường xuyên vì các giá trị này là số nguyên nhỏ; với dữ liệu khác thì chúng hoàn toàn không dùng được.
Câu hỏi thường gặp
Thuật toán sắp xếp nào nhanh nhất?
Còn tùy dữ liệu. Với số nguyên nhỏ, sắp xếp đếm và sắp xếp theo cơ số cần ít thao tác nhất. Với dữ liệu thông thường, sắp xếp nhanh và sắp xếp trộn nhanh nhất trên danh sách ngẫu nhiên, còn sắp xếp chèn nhanh nhất trên danh sách gần như đã sắp xếp. Sắp xếp nổi bọt và sắp xếp chọn đều chậm, trừ khi danh sách rất nhỏ.
Thế nào được tính là một thao tác?
Mỗi phép so sánh hai giá trị, mỗi chữ số hoặc giá trị mà sắp xếp theo cơ số và sắp xếp đếm đọc, và mỗi lần hoán đổi hoặc di chuyển một giá trị. Đây là một mô hình đơn giản: thời gian chạy thực tế còn phụ thuộc vào việc truy cập bộ nhớ và chi phí của mỗi thao tác.
Vì sao sắp xếp đếm và sắp xếp theo cơ số hay thắng?
Vì chúng không bao giờ so sánh các giá trị. Chúng tận dụng việc các giá trị là số nguyên nhỏ, nên khối lượng công việc tăng theo n cộng với khoảng giá trị, chứ không theo n log n. Với dữ liệu không phải số nguyên nhỏ, chúng không áp dụng được.
Vì sao sắp xếp chèn thắng trên danh sách gần như đã sắp xếp?
Vì khối lượng công việc của nó bằng số giá trị cộng với số cặp sai thứ tự. Danh sách gần như đã sắp xếp có rất ít cặp như vậy, nên mỗi giá trị chỉ dịch một hai vị trí.
Các số của tôi có bị gửi đi đâu không?
Không. Cuộc đua chạy trong trình duyệt của bạn, và cài đặt gần nhất của bạn đượ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