自然合并排序未正确排序列表的最后两个数字-解网

问：

我试图在 python 中实现自然合并排序，我的get_sorted_run_length正常工作，但我natural_merge_sort正确排序了大部分列表，但由于某种原因，没有对列表中的最后两个整数进行排序。我不知道为什么它不起作用，这是代码。

main.py

    import sys

from NaturalMergeSorter import NaturalMergeSorter
from RunLengthTestCase import RunLengthTestCase

def main():
    # Test case list: A completely sorted lst
    list1 = [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
# Test case list: Sorted run of 3 followed by sorted run of 6
list2 = [64, 88, 91, 12, 21, 34, 43, 56, 65]

# Test case list: 5 elements in descending order, so 5 runs of length 1
list3 = [-10, -20, -30, -40, -50]

# Test case list: 8 equal elements, so 1 run of 8
list4 = [-99, -99, -99, -99, -99, -99, -99, -99]

test_cases = [
    # First test case uses an out-of-bounds starting index. remaining test
    # cases do not.
    RunLengthTestCase(list1, len(list1), 0),
    RunLengthTestCase(list1, 0, len(list1)),
    RunLengthTestCase(list1, 3, len(list1) - 3),
    RunLengthTestCase(list2, 0, 3),
    RunLengthTestCase(list2, 2, 1),
    RunLengthTestCase(list2, 3, 6),
    RunLengthTestCase(list3, 0, 1),
    RunLengthTestCase(list3, 3, 1),
    RunLengthTestCase(list4, 0, len(list4)),
    RunLengthTestCase(list4, 4, len(list4) - 4),
    RunLengthTestCase(list4, 5, len(list4) - 5),
]

for test in (test_cases):
    # Execute the test case, printing messages to sys.stdout
    test.execute(sys.stdout)

# Test case lst for sorting
list5 = [92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22]
list5_copy = list(list5)
sorter = NaturalMergeSorter()
sorter.natural_merge_sort(list5_copy)
print(f"""
{'PASS' if list5_copy == sorted(list5) else 'FAIL'}: NaturalMergeSort()
   List before calling natural_merge_sort(): {list5}
   List after calling natural_merge_sort():  {list5_copy}""")

if __name__ == '__main__':  
    main()

RunLengthTestCase.py

from NaturalMergeSorter import NaturalMergeSorter

class RunLengthTestCase:
    def __init__(self, lst, start, expected_return):
        self.lst = lst
    self.start = start
    self.expected_return = expected_return

# Executes the test case. If the test case passes, a message that starts
# with "PASS" is printed and true is returned. Otherwise a message that
# starts with "FAIL" is printed and false is returned.
def execute(self, test_feedback):
    user_sorter = NaturalMergeSorter()

    # Call the get_sorted_run_length() function with the test case parameters
    user_ret_val = user_sorter.get_sorted_run_length(self.lst, self.start)

    # The test passed only if the actual return value equals the
    # expected return value
    passed = user_ret_val == self.expected_return

    if user_ret_val == self.expected_return:
        print(f"""PASS: get_sorted_run_length()\n   List: {self.lst}""", file=test_feedback)
        print(f"""   Start index:           {self.start}""", file=test_feedback)
        print(f"""   Expected return value: {self.expected_return}""", file=test_feedback)
        print(f"""   Actual return value:   {user_ret_val}""", file=test_feedback)
        return True
    else:
        print(f"""FAIL: get_sorted_run_length()\n   List: {self.lst}""", file=test_feedback)
        print(f"""   Start index:           {self.start}""", file=test_feedback)
        print(f"""   Expected return value: {self.expected_return}""", file=test_feedback)
        print(f"""   Actual return value:   {user_ret_val}""", file=test_feedback)
        return False

class NaturalMergeSorter:
def __init__(self):
    return

def get_sorted_run_length(self, integer_list, start_index):
    if start_index < 0 or start_index >= len(integer_list):
        return 0
    r_length = 1 
    cur_index = start_index
    while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
        r_length += 1
        cur_index += 1
    return r_length


def get_sorted_run_length(self, integer_list, start_index):
    if start_index < 0 or start_index >= len(integer_list):
        return 0
    r_length = 1 
    cur_index = start_index
    while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
        r_length += 1
        cur_index += 1
    return r_length


def natural_merge_sort(self, integer_list):
    i = 0
    while i < len(integer_list):
        r1 = self.get_sorted_run_length(integer_list, i)
        
        if i + r1 == len(integer_list):
            break

        r2 = self.get_sorted_run_length(integer_list, i + r1)

        self.merge(integer_list, i, i + r1 - 1, i + r1 + r2 - 1)

        if i + r1 + r2 == len(integer_list):
            i = 0
        else:
            i = i + r1 + r2

def merge(self, numbers, left_first, left_last, right_last):
    merged_size = right_last - left_first + 1

    merged_numbers = [None] * merged_size
    merge_pos = 0
    left_pos = left_first
    right_pos = left_last + 1

    while left_pos <= left_last and right_pos <= right_last:
        if numbers[left_pos] <= numbers[right_pos]:
            merged_numbers[merge_pos] = numbers[left_pos]
            left_pos += 1
        else:
            merged_numbers[merge_pos] = numbers[right_pos]
            right_pos += 1

        merge_pos += 1

 
    while left_pos <= left_last:
        merged_numbers[merge_pos] = numbers[left_pos]
        left_pos += 1
        merge_pos += 1

    # If right partition isn't empty, add remaining elements to merged_numbers
    while right_pos <= right_last:
        merged_numbers[merge_pos] = numbers[right_pos]
        right_pos += 1
        merge_pos += 1

    # Copy merged numbers back to numbers
    for merge_pos in range(merged_size):
        numbers[left_first + merge_pos] = merged_numbers[merge_pos]

NaturalMergeSorter.py

class NaturalMergeSorter:
def __init__(self):
    return

def get_sorted_run_length(self, integer_list, start_index):
    if start_index < 0 or start_index >= len(integer_list):
        return 0
    r_length = 1 
    cur_index = start_index
    while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
        r_length += 1
        cur_index += 1
    return r_length


def get_sorted_run_length(self, integer_list, start_index):
    if start_index < 0 or start_index >= len(integer_list):
        return 0
    r_length = 1 
    cur_index = start_index
    while cur_index < len(integer_list) - 1 and integer_list[cur_index] <= integer_list[cur_index + 1]:
        r_length += 1
        cur_index += 1
    return r_length


def natural_merge_sort(self, integer_list):
    i = 0
    while i < len(integer_list):
        r1 = self.get_sorted_run_length(integer_list, i)
        
        if i + r1 == len(integer_list):
            break

        r2 = self.get_sorted_run_length(integer_list, i + r1)

        self.merge(integer_list, i, i + r1 - 1, i + r1 + r2 - 1)

        if i + r1 + r2 == len(integer_list):
            i = 0
        else:
            i = i + r1 + r2

def merge(self, numbers, left_first, left_last, right_last):
    merged_size = right_last - left_first + 1

    merged_numbers = [None] * merged_size
    merge_pos = 0
    left_pos = left_first
    right_pos = left_last + 1

    while left_pos <= left_last and right_pos <= right_last:
        if numbers[left_pos] <= numbers[right_pos]:
            merged_numbers[merge_pos] = numbers[left_pos]
            left_pos += 1
        else:
            merged_numbers[merge_pos] = numbers[right_pos]
            right_pos += 1

        merge_pos += 1

 
    while left_pos <= left_last:
        merged_numbers[merge_pos] = numbers[left_pos]
        left_pos += 1
        merge_pos += 1

    # If right partition isn't empty, add remaining elements to merged_numbers
    while right_pos <= right_last:
        merged_numbers[merge_pos] = numbers[right_pos]
        right_pos += 1
        merge_pos += 1

    # Copy merged numbers back to numbers
    for merge_pos in range(merged_size):
        numbers[left_first + merge_pos] = merged_numbers[merge_pos]

这是我得到的结果

    PASS: get_sorted_run_length()
   List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
   Start index:           10
   Expected return value: 0
   Actual return value:   0
PASS: get_sorted_run_length()
   List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
   Start index:           0
   Expected return value: 10
   Actual return value:   10
PASS: get_sorted_run_length()
   List: [15, 23, 23, 23, 31, 64, 77, 87, 88, 91]
   Start index:           3
   Expected return value: 7
   Actual return value:   7
PASS: get_sorted_run_length()
   List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
   Start index:           0
   Expected return value: 3
   Actual return value:   3
PASS: get_sorted_run_length()
   List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
   Start index:           2
   Expected return value: 1
   Actual return value:   1
PASS: get_sorted_run_length()
   List: [64, 88, 91, 12, 21, 34, 43, 56, 65]
   Start index:           3
   Expected return value: 6
   Actual return value:   6
PASS: get_sorted_run_length()
   List: [-10, -20, -30, -40, -50]
   Start index:           0
   Expected return value: 1
   Actual return value:   1
PASS: get_sorted_run_length()
   List: [-10, -20, -30, -40, -50]
   Start index:           3
   Expected return value: 1
   Actual return value:   1
PASS: get_sorted_run_length()
   List: [-99, -99, -99, -99, -99, -99, -99, -99]
   Start index:           0
   Expected return value: 8
   Actual return value:   8
PASS: get_sorted_run_length()
   List: [-99, -99, -99, -99, -99, -99, -99, -99]
   Start index:           4
   Expected return value: 4
   Actual return value:   4
PASS: get_sorted_run_length()
   List: [-99, -99, -99, -99, -99, -99, -99, -99]
   Start index:           5
   Expected return value: 3
   Actual return value:   3

FAIL: NaturalMergeSort()
   List before calling natural_merge_sort(): [92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22]
   List after calling natural_merge_sort():  [10, 18, 26, 39, 54, 71, 73, 89, 92, 99, 22, 64]

谢谢

python mergesort

1赞 Codist 9/18/2023

您的缩进已损坏。坦率地说，你的实现很奇怪

答：

0赞 zilla 9/18/2023 #1

我认为这与这条线有关......如果合并操作后列表中的最后两个元素未完全排序，则它仍会将 i 重置为 0。

if i + r1 + r2 == len(integer_list):
   i = 0

0赞 pokemonmater940 9/18/2023

我将如何实现它不会重置？

上一个：我无法弄清楚这种合并排序算法的问题

下一个：java 中 2d 数组的第一个索引的 mergeSort

自然合并排序未正确排序列表的最后两个数字

Natural merge sort not correctly sorting the last two numbers of a list

评论

评论