- Đang đếm
- Vừa chuyển
- Đã đúng chỗ
Sắp xếp đếm
Sắp xếp đếm dùng được khi các giá trị là số nguyên trong một khoảng nhỏ. Nó giữ một bộ đếm cho mỗi giá trị có thể có, đếm mỗi giá trị xuất hiện bao nhiêu lần, và từ các số đếm đó biết chính xác mỗi giá trị thuộc về đâu. Hãy xem các bộ đếm tăng dần khi danh sách được đọc, rồi giảm lại khi từng giá trị chuyển vào đoạn của nó, mỗi lần một bước. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng lần di chuyển. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Dải nằm giữa danh sách và hàng bộ đệm chứa một bộ đếm cho mỗi giá trị. Các ô đếm số giá trị đã đếm, số lần di chuyển và số bộ đếm. 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, hoặc tự nhập các số nguyên. Hãy thử một danh sách có ít giá trị khác nhau.
- Nhấn Phát, hoặc dùng Bước và Lùi để chuyển từng giá trị một. 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 các bộ đếm: chúng tăng dần khi danh sách được đọc, rồi giảm dần khi từng giá trị được đặt vào chỗ.
Sắp xếp đếm hoạt động thế nào
Tạo một bộ đếm cho mỗi giá trị từ nhỏ nhất đến lớn nhất. Đọc danh sách một lần và cộng một vào bộ đếm của mỗi giá trị bạn gặp. Rồi cộng dồn các số đếm từ giá trị nhỏ nhất: đoạn của một giá trị bắt đầu ngay sau tất cả các giá trị nhỏ hơn. Cuối cùng, duyệt danh sách lần nữa, chuyển mọi giá trị đến chỗ trống kế tiếp trong đoạn của nó, rồi chép kết quả trở lại.
Nhanh khi khoảng giá trị nhỏ
Sắp xếp đếm đọc danh sách hai lần và duyệt các bộ đếm một lần, nên khối lượng công việc tăng theo n + k: số giá trị cộng số bộ đếm. Với nhiều giá trị trong một khoảng nhỏ, như điểm thi từ 0 đến 100 hay tuổi, nó nhanh hơn mọi thuật toán sắp xếp dựa trên so sánh. Với khoảng rộng, nó lãng phí thời gian và bộ nhớ cho những bộ đếm không ai dùng: ba giá trị trải từ 1 đến 1.000.000 sẽ cần một triệu bộ đếm. Đây cũng là bước mà sắp xếp theo cơ số lặp lại cho từng chữ số.
Câu hỏi thường gặp
Sắp xếp đếm hoạt động thế nào?
Nó đếm mỗi giá trị xuất hiện bao nhiêu lần, cộng dồn các số đếm để tìm nơi đoạn của mỗi giá trị bắt đầu, rồi chuyển thẳng mọi giá trị đến chỗ trống kế tiếp trong đoạn của nó. Nó không bao giờ so sánh hai giá trị.
Khi nào nên dùng sắp xếp đếm?
Khi các giá trị là số nguyên, hoặc có thể đổi thành số nguyên, và khoảng từ nhỏ nhất đến lớn nhất không lớn hơn nhiều so với số giá trị: điểm số, tuổi, mã nhỏ. Khi đó thời gian tỉ lệ với n + k.
Sắp xếp đếm có ổn định không?
Có, khi các giá trị được chuyển theo thứ tự danh sách đến chỗ trống kế tiếp trong đoạn của chúng, như ở đây. Nhờ vậy sắp xếp theo cơ số có thể dùng nó cho từng chữ số.
Sao không chỉ viết mỗi giá trị ra đúng bằng số lần đã đếm?
Với các số đơn thuần thì cách đó được, thậm chí còn đơn giản hơn. Nhưng dữ liệu thực thường mang nhiều thứ hơn khóa, chẳng hạn một cái tên đi kèm mỗi điểm số, và chỉ viết ra các khóa đã đếm sẽ làm mất chúng. Chuyển chính các phần tử thì giữ được mọi thứ đi kèm.
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