Thắc mắc về sắp xếp khối dữ liệu lớn vào bộ nhớ trong

[Tien_Si (vipprobm1)]

Bài toán 4 :

Sắp xếp một dãy số nguyên 20000 số phân biệt khác nhau (các số nguyên đó có trị từ 1…30000) mà bộ nhớ trong chỉ có 1200 từ (4 bytes/từ).

Với bộ nhớ trong hạn chế theo như đề bài, ta không thể lưu trữ hết 20000 số nguyên vào bộ nhớ trong để áp dụng các giải thuật sort nội. Trong trường hợp này, một giải pháp có thể được là lưu 20000 số vào bộ nhớ ngoài và áp dụng giải thuật sort ngoại để sắp xếp chúng. Với cách thức lưu trữ và sắp xếp này, ta sẽ tốn thời gian để truy xuất dữ liệu và sắp xếp.

Em đang thắc mắc là nếu mình tạo 1 mảng chứa 3750 bytes thì sao được ạ

[SITUVN.gcd]

Đề cho tối đa 1200 từ * 4 (byte/từ) = 4800 byte.
Hướng giải chỉ dùng 3750 byte (3750 * 8 = 30000 bit) là phù hợp (dư 1050 byte).
Hướng làm này đúng do tất mỗi số đều có giá trị riêng biệt duy nhất (không có số nào trùng giá trị).

[rogp10]

Đây gọi là counting sort và độ phức tạp phụ thuộc vào miền giá trị.

[Tien_Si (vipprobm1)]

@SITUVN.gcd

375

dạ tks anh ạ. Em hiểu r ạ