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

Phạm Văn Việt

doi:10.34238/tnu-jst.8368

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

Thông tin bài báo

Ngày nhận bài: 20/07/23 Ngày hoàn thiện: 30/08/23 Ngày đăng: 31/08/23

Các tác giả

Phạm Văn Việt , Đại học Kỹ thuật Lê Quý Đôn

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.

Từ khóa

Thuật toán sắp xếp; Các phần tử với quan hệ cha-con; Phân tích thuật toán; Cây AVL; Các cấu trúc dữ liệu và thuật toán

Toàn văn:

PDF (English)

Tài liệu tham khảo

[1] D. Knuth, "Chapter 5 - Sorting," in The Art of Computer Programming, 3^rd ed., vol. 3: Sorting and Searching, Addison-Wesley, 1997, pp. 1-391.

[2] Y. Han, "Deterministic sorting in O(nloglogn) time and linear space," Journal of Algorithms, vol. 50, no. 1, pp. 96-105, 2004.

[3] Y. Han, "Sort Real Numbers in Time and and Linear Space," Algorithmica, vol. 82, no. 2, pp. 966-978, 2020.

[4] S. Abdel-Hafeez and A. Gordon-Ross, "An Efficient O(N) Comparison-Free Sorting," IEEE Transactions on Very Large Scale Integration Systems, vol. 25, no. 6, pp. 1930-1942, 2017.

[5] F. C. Leu, Y. T. Tsai, and C. V. Tang, "An efficient external sorting algorithm," Information Processing Letters, vol. 75, no. 4, pp. 159-163, 2000.

[6] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Section 2.1 Insertion sort," in Introduction to Algorithms, 4^th ed., The MIT Press, 2022, pp. 17-33.

[7] R. Sedgewick, "Implementing Quicksort programs," Communications of the ACM, vol. 21, no. 10, pp. 847-857, 1978.

[8] D. Knuth, "Sorting by Merging," in The Art of Computer Programming, 3^rd ed., vol. 3: Sorting and Searching, Addison-Wesley, 1998, pp. 158-166.

[9] J. W. J. Williams, "Algorithm 232 (HEAPSORT)," Communications of the ACM, vol. 7, no. 6, pp. 347-348, 1964.

[10] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Section 6 Heap sort," in Introduction to Algorithms, 4^th ed., The MIT Press, 2022, pp. 161-172.

[11] H. H. Seward, "2.4.6 Internal Sorting by Floating Digital Sort," in Information sorting in the application of electronic digital computers to business operations, Massachusetts Institute of Technology, Digital Computer Laboratory, 1954, pp. 25-28.

[12] D. E. Knuth., "Section 5.2.5: Sorting by Distribution," in The Art of Computer Programming, 3^rd ed., vol. 3: Sorting and Searching, Addison-Wesley, 1997, pp. 168-179.

[13] G. Adelson-Velskii and E. Landis, "An algorithm for the organization of information," in the USSR Academy of Sciences (in Russian), 1962.

[14] P. Brass, "3.1 Height-Balanced Trees," in Advanced Data Structures, Cambridge University Press, 2008, pp. 50-61.

DOI: https://doi.org/10.34238/tnu-jst.8368

Các bài báo tham chiếu

Hiện tại không có bài báo tham chiếu



Ghi nhớ