MỘT THUẬT TOÁN HIỆU QUẢ ĐỂ SẮP XẾP MỘT TẬP CÁC PHẦN TỬ VỚI QUAN HỆ CHA CON

Tóm tắt

Một hệ thống trong thế giới thực có thể có một bảng cơ sở dữ liệu gồm các bản ghi có mối quan hệ cha-con. Các bản ghi có thể không được chèn vào bảng theo thứ tự cây gia đình. Bài báo này đề xuất một thuật toán hiệu quả để giải bài toán sắp xếp danh sách các phần tử có quan hệ cha-con tương ứng với tất cả các bản ghi trong bảng cơ sở dữ liệu. Giả sử rằng tất cả các bản ghi được tải vào bộ nhớ dưới dạng danh sách các phần tử. Đầu tiên, thuật toán tạo một danh sách S với phần tử đầu tiên lưu trữ các đại diện của các phần tử gốc và mỗi phần tử khác lưu trữ tập đại diện của các con của một phần tử trong danh sách đầu vào. Danh sách S tạo thành một tập các cây của các phần tử đầu vào. Sau đó, mỗi phần tử đầu vào được thêm vào danh sách được sắp xếp đầu ra bằng cách thực hiện tìm kiếm theo chiều sâu trên mỗi cây. Thuật toán cần thời gian O(nlog(n)) và không gian O(n) để giải bài toán trong đó n là số phần tử. Thuật toán mất khoảng 154 (giây) để sắp xếp 2.441.405 phần tử, sử dụng máy tính xách tay có bộ xử lý Intel(R) Core(TM) i7-4510U CPU @ 2,00GHz 2,60 GHz và RAM 8 GB.