AN IMPROVED ALGORITHM FOR SORTING A LIST OF PARENT AND CHILD MEMBERS

Tóm tắt

The paper focuses on the challenge of sorting a list of parent and child members. An algorithm is proposed to sort the list, based on an existing algorithm (Pham, 2023). The algorithm includes three stages. The first stage creates a list, list4F, to locate the position of a given member in the input list based on its identifier efficiently. The second stage constructs a list S using list4F. Each element in S maintains representative elements corresponding to the child members of a single input member, thereby facilitating efficient reference to any child member. The third stage outputs the sorted list with members in family tree order, using the list S. The new algorithm uses list data structures instead of AVL tree data structures, as in the existing algorithm, to hold data in the first two stages. These adjustments make the new algorithm significantly faster than the previous algorithm. Both algorithms require O(nlog(n)) time and O(n) space to sort the input list containing n members. However, the third stage of the new algorithm takes only O(n) time, whereas that of the existing algorithm requires O(nlog(n)) time.