Lesson 10 — Non-comparison Sorts

Ba thuật toán sort không dùng so sánh — phá rào Ω(n log n) bằng cách dùng giá trị làm index/digit. Mỗi module dưới đây mô phỏng từng bước với số liệu thật.

1. Counting Sort Animator

Nhập các số nguyên không âm (cách nhau bởi dấu cách). Quan sát 3 bước: đếm tần suất → prefix sum → đặt vào output (duyệt ngược để ổn định).

Mảng gốc
count[v] (sau prefix sum = số phần tử ≤ v)
Output
Nhấn "Nạp" rồi "Bước tiếp" để bắt đầu.
đang xử lý đã đặt vào output count đang đọc

2. Radix Sort (LSD) Animator

Sort theo từng chữ số, từ hàng đơn vị → chục → trăm. Mỗi pass phân vào 10 bucket (0–9) theo digit, rồi gom lại theo thứ tự. Bucket giữ thứ tự ban đầu → ổn định.

Mảng hiện tại
Bucket (theo digit đang xử lý)
Nhấn "Nạp" rồi "Pass tiếp".

3. Decision Tree — giới hạn dưới comparison sort

Mọi comparison sort = cây nhị phân với ≥ n! lá (mỗi lá một hoán vị). Cây cao h có ≤ 2^h lá → h ≥ log₂(n!) = Ω(n log n). Đây là số so sánh tối thiểu.

Nhập n (2–6) rồi nhấn "Vẽ cây".
So sánh tối thiểu theo n
nn! (số lá)⌈log₂(n!)⌉ = so sánh tối thiểun·log₂n (xấp xỉ)