MỘT THUẬT TOÁN CẢI TIẾN CHO BÀI TOÁN SẮP XẾP MỘT DANH SÁCH CÁC THÀNH VIÊN CHA VÀ CON

Phạm Văn Việt

doi:10.34238/tnu-jst.13147

MỘT THUẬT TOÁN CẢI TIẾN CHO BÀI TOÁN SẮP XẾP MỘT DANH SÁCH CÁC THÀNH VIÊN CHA VÀ CON

Thông tin bài báo

Ngày nhận bài: 29/06/25 Ngày hoàn thiện: 26/12/25 Ngày đăng: 31/12/25

Các tác giả

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

Tóm tắt

Bài báo tập trung vào thách thức sắp xếp danh sách các thành viên cha và con. Một thuật toán được đề xuất để sắp xếp danh sách, dựa trên một thuật toán hiện có (Pham, 2023). Thuật toán bao gồm ba giai đoạn. Giai đoạn đầu tạo một danh sách, list4F, để định vị một thành viên nhất định trong danh sách đầu vào dựa trên mã định danh của nó một cách hiệu quả. Giai đoạn hai xây dựng một danh sách S bằng list4F. Mỗi phần tử trong S duy trì các phần tử đại diện tương ứng với các thành viên con của một thành viên đầu vào duy nhất, do đó tạo điều kiện tham chiếu hiệu quả đến bất kỳ thành viên con nào. Giai đoạn ba đưa ra danh sách đã sắp xếp với các thành viên theo thứ tự cây phả hệ, bằng cách sử dụng danh sách S. Thuật toán mới sử dụng cấu trúc dữ liệu danh sách thay vì cấu trúc dữ liệu cây AVL, như trong thuật toán hiện có, để lưu trữ dữ liệu trong hai giai đoạn đầu. Những điều chỉnh này làm cho thuật toán mới nhanh hơn đáng kể so với thuật toán trước đó. Cả hai thuật toán đều yêu cầu thời gian O(nlog(n)) và không gian O(n) để sắp xếp danh sách đầu vào chứa n thành viên. Tuy nhiên, giai đoạn ba của thuật toán chỉ mất thời gian O(n), trong khi giai đoạn này của thuật toán hiện có yêu cầu thời gian O(nlog(n)).

Từ khóa

Thuật toán sắp xếp; Thuật toán sắp xếp hòa nhập; Các thành viên cha và con; Phân tích thuật toán; 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] V. V. Pham, "An efficient algorithm for sorting a set of elements with parent-child relationships," TNU Journal of Science and Technology, vol. 228, no. 15, pp. 29 - 36, 2023.

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

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

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

[5] 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.

[6] 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.

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

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

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

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

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

[12] 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.

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

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

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

[16] M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, "5.4.1 Python's List and Tuple Classes," in Data Structures & Algorithms in Python, Wiley, 2013, pp. 202-207.

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

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ớ