데이터 구조 및 분석 ch_4_2 Merge Sort and Problems in Recursions

Jul 25, 2021 » writing

KAIST 산업및시스템공학과 문일철_ 데이터 구조 및 분석 수업을 참고하여 작성하였습니다

ch_4_2 Merge Sort and Problems in Recursions

정의

Merge Sort and Problems in Recursions

1. Merge Sort
   : One example of recursive programming
   : Decompose into two smaller lists (분해)
   : Aggregate to one larger and sorted list (합치기)

import random

def performMergeSort(lstElementToSort) :
    if len(lstElementToSort) ==1:
        return lstElementToSort

    lstSubElementToSort1 = []
    lstSubElementToSort2 = []
    for itr in range(len(lstElementToSort)) :
        if len(lstElementToSort)/2 > itr:
            lstSubElementToSort1.append(lstElementToSort[itr])
        else:
            lstSubElementToSort2.append(lstElementToSort[itr])
    lstSubElementToSort1 = performMergeSort(lstSubElementToSort1)
    lstSubElementToSort2 = performMergeSort(lstSubElementToSort2)

    idxCount1 = 0
    idxCount2 = 0
    for itr in range(len(lstElementToSort)):
        if idxCount1 == len(lstSubElementToSort1) :
            lstElementToSort[itr] = lstSubElementToSort2[idxCount2]
            idxCount2 = idxCount2 + 1
        elif idxCount2 == len(lstSubElementToSort2) :
            lstElementToSort[itr] = lstSubElementToSort1[idxCount1]
            idxCount1 = idxCount1 + 1
        elif lstSubElementToSort1[idxCount1] > lstSubElementToSort2[idxCount2] :
            lstElementToSort[itr] = lstSubElementToSort2[idxCount2]
            idxCount2 = idxCount2 + 1
        else:
            lstElementToSort[itr] = lstSubElementToSort1[idxCount1]
            idxCount1 = idxCount1 + 1
    return lstElementToSort

lstRandom = []
for itr in range(0,10):
    lstRandom.append(random.randrange(0,100))
print(lstRandom)
lstRandom = performMergeSort(lstRandom)
print(lstRandom)

# [27, 19, 26, 99, 50, 56, 2, 18, 55, 21]
# [2, 18, 19, 21, 26, 27, 50, 55, 56, 99]

2. Problems in Recursions of Fibonacci Sequence
    : Problems in recursions
    : Excessive functions again and again (same parameters)