-1

具体的には次の 2 つのケースでのマージ ソートの実装に疑問があり

ます。

2.リストがその中の要素の数の外側をチェックしようとするときのマージ機能では、最大の数（9999）を割り当てたので、それと比較すると常にfalseになります。
私のマージソートの実装が正しいかどうか、誰か教えてもらえますか? 並べ替えは完了しましたが、マージ並べ替えの実装は正確ですか、それとも場合によっては間違っていますか?

これが私のコードです： 

# unsorted LIST
u_list = [3, 6, 8, 1, 4, 7, 2, 12, 45];

# Size of the unsorted list
global_size = len(u_list)

def foo(temp_list):
    size_of_list = len(temp_list)
    # If the size of the list is 1
    if size_of_list == 1:
        return temp_list

    # If the size of the list is 2
    if size_of_list == 2:
        if temp_list[0] > temp_list[1]:
            temp_list[0],temp_list[1] = temp_list[1],temp_list[0]
            return temp_list
        else: 
            return temp_list

    # If the size of the list is greater than 2                
    if size_of_list > 2:
        count = 1
        i = 0
        if size_of_list % 2 == 0:
            mid1 = size_of_list / 2
        else:
            mid1 = (size_of_list / 2) + 1

        mid2 = size_of_list - mid1

        newlist1 = list()
        newlist2 = list()

        for e in temp_list:
            if count >= mid1 + 1:
                newlist2.append(e)
            else:
                newlist1.append(e)
            if count == size_of_list:
                break
            count = count + 1
        sorted_list = list()
        return merge(foo(newlist1), foo(newlist2))

# Merging all the sorted components
def merge(list1, list2):
    i = 0
    j = 0
    k = 0
    size_of_list = len(list1) + len(list2)
    sorted_list = list()
    while k <= size_of_list - 1:
        if i == len(list1):
            list1.append(9999)
        if j == len(list2):
            list2.append(9999)

        if list1[i] < list2[j]:
            sorted_list.append(list1[i])
            i = i + 1
        elif list2[j] < list1[i]:
            sorted_list.append(list2[j])
            j = j + 1
        k = k + 1
    return sorted_list

print foo(u_list)
4

3 に答える 3

19

正直なところ、このようなコードを見ると非常に不安になります;)。それは正しいかもしれませんが、私の直感ではそうではありません (> 9999 の数字がある場合はどうなるでしょうか?)。必要以上に複雑です。構文は Python ですが、Python の機能を使用していません。

Pythonでマージソートを実装する方法は次のとおりです。

def merge_sort(sequence):
    if len(sequence) < 2: 
        return sequence

    mid = int(len(sequence) / 2)
    left_sequence = merge_sort(sequence[:mid])
    right_sequence = merge_sort(sequence[mid:])
    return merge(left_sequence, right_sequence)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1 
    result += left[i:]
    result += right[j:]

    return result
于 2012-06-20T05:09:33.963 に答える
2

最もきれいなコードではありませんが、マージソートメソッドによって仕事が完了します。

方法 1:

def merge_sorted(list1,list2):

    sorted = []

    i = 0

    k = 0

    while True:
        if i >= len(list1):                                                     
            sorted.extend(list2[k:])
            return sorted

        if k >= len(list2):
            sorted.extend(list1[i:])                                   
            return sorted

        if list1[i] <= list2[k]:
            sorted.append(list1[i])
            i += 1
        else:
            sorted.append(list2[k])
            k += 1

方法 2:

def sort_method2(list0):

    unsorted_list = list0[:]

    if (len(unsorted_list) == 1 or len(unsorted_list) == 0): 

        return(unsorted_list)

    elif(len(unsorted_list) == 2): 

        if (unsorted_list[0] > unsorted_list[1]):

            temp = unsorted_list[0]

            unsorted_list[0] = unsorted_list[1]

            unsorted_list[1] = temp

        return(unsorted_list)
    else:
        length = len(unsorted_list)//2   

        first_list = sort_method2(unsorted_list[length:])   

        second_list = sort_method2(unsorted_list[:length]) 

        return(merge_sorted(first_list,second_list))

list3 = [8,8,2,63,2,6,3,4,2,6,2,6,8,5,4,3,6,-1,21,0,1,23,623,4, 0.001,5,4,256,4,0]

sort_method2(リスト3)

于 2013-04-12T20:58:57.423 に答える