基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

アルゴリズムの勉強のためpython(googlecolab)を使い始めました。
試しに過去問をpythonへ書き起こしをしていますがうまくいきません、どこが悪いのか教えてください。平成22年春、午後問8で書き起こしをしています。

＜自分なりに書いたプログラム＞
nums = [7,4,3,5,6,1,2]


n = len(nums)
def merge(nums,num1,num2,slist1,slist2):
    merge_sort(nums, slist1, num1)
    merge_sort(nums, slist2, num2)
    merge(nums,num1,num2,)


def merge_sort(nums):

    if len(nums) > 1:
        return nums

num1 = len(nums) //2
num2 = len(nums) - num1

slist1 = [0] * (num1)
slist2 = [0] * (num2)

for i in range(0 , num1):
        slist1[i] = nums[i]

for j in range(0 , num2):
        slist2[j] = nums[num1 + j]

i = 0
j = 0
k = 1

while i < num1 and j < num2 :
        if slist1[i] < slist2[j]:
            nums[i + j] = slist1[i]
            i += 1
        else:
            nums[i + j] = slist2[j]
            j += 1
        k += 1



while i < num1 or j < num2:
        if i < num1:
           nums[i + j] = slist1[i]
           i += 1
           k += 1
        else:
           nums[i + j] = slist2[j]
           j += 1
           k += 1


print(nums)

細かいところが…とかではなく大きく違っているところがあるのでもう少し注意深く見てみてください。

いろいろヒントを置いておきますね。

・プログラムSortは再帰関数だが、副プログラムMergeは再帰関数ではない。

・merge_sort(nums, slist1, num1)という関数を呼び出しているが、定義されているのはmerge_sort(nums)

・インデントを確認すること。
一番重大なのがここ

def merge_sort(nums):

    if len(nums) > 1:
        return nums

merge_sortの定義がこれで終わりとみなされます。

ありがとうございます。いろいろ試してみます。

考えてみても分からなかったら聞いてください。

なんとかできたがこれじゃない感があります。

def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    nums1 = len(nums) // 2
    slist1 = nums[:nums1]          #ここをfor文にしたい
    slist2 = nums[nums1:]



    slist1 = merge_sort(slist1)
    slist2 = merge_sort(slist2)



    i, j, k= 0, 0, 0
    while i < len(slist1) and j < len(slist2):
        if slist1[i] <= slist2[j]:
            nums[k] = slist1[i]
            i += 1
        else:
            nums[k] = slist2[j]
            j += 1
        k += 1

    while i < len(slist1) or j < len(slist2):
        if i < len(slist1):
            nums[k] = slist1[i]
            i += 1
            k += 1
        else:
            nums[k] = slist2[j]
            j += 1
            k += 1

    return nums

if __name__ == '__main__':
    nums = [7,4,3,5,6,1,2]
    print(merge_sort(nums))

こんな感じじゃないですかね。スライス使ってもいいですけど。

ありがとうございます。無理に問題文の順番通りにしようとすると余計に難しく感じるには自分だけでしょうか？また別の問題にも挑戦します。

あくまで私はですが、問題の通りの方が整理されていて理解しやすいと思います。