Python 알고리즘 문제풀이 2

버블정렬 알고리즘

• 숫자로 이루어진 리스트를 버블정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자.

코드1

import copy
def sortByBubbleAlgorithm(ns, asc = True):

    c_ns = copy.copy(ns)

    length = len(c_ns) - 1
    for i in range(length):
        for j in range(length -i):

            if asc:
                if c_ns[j] > c_ns[j+1]:
                    c_ns[j],c_ns[j+1] = c_ns[j+1],c_ns[j]
            else:
                if c_ns[j] < c_ns[j+1]:
                    c_ns[j],c_ns[j+1] = c_ns[j+1],c_ns[j]

            print(f'ns: {c_ns}')
        print()

    return c_ns

코드2

import random
import bubbleMod

if __name__ == '__main__':

    nums = random.sample(range(1,21), 10)
    print(f'not sorted nums: {nums}')

    result = bubbleMod.sortByBubbleAlgorithm(nums)
    print(f'sorted nums by ASC: {result}')

    result = bubbleMod.sortByBubbleAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC: {result}')

출력

---

삼입정렬 알고리즘

• 숫자로 이루어진 리스트를 삽입정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자.

코드1

import copy
def sortInsertAlgorithm(ns, asc=True):

    c_ns = copy.copy(ns)

    for i1 in range(1, len(c_ns)):
        i2 = i1 - 1
        c_Num = c_ns[i1]

        if asc:     # ascending
            while c_ns[i2] > c_Num and i2 >= 0:
                c_ns[i2 + 1] = c_ns[i2]
                i2 -= 1

        else:       # descending
            while c_ns[i2] < c_Num and i2 >= 0:
                c_ns[i2 + 1] = c_ns[i2]
                i2 -= 1

        c_ns[i2 + 1] = c_Num
        print(f'c_ns: {c_ns}')

    return c_ns

코드2

import random
import insertMod

if __name__ == '__main__':
    nums = random.sample(range(1,21), 10)

    print(f'not sorted nums: {nums}')
    result = insertMod.sortInsertAlgorithm(nums)
    print(f'sorted nums by ASC: \n {result}')

    print(f'not sorted nums: {nums}')
    result = insertMod.sortInsertAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC: \n {result}')

출력

---

선택정렬 알고리즘

• 숫자로 이루어진 리스트를 선택정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자.

코드1

import copy

def sortSelectAlgorithm(ns, asc = True):
    c_ns = copy.copy(ns)

    for i in range(len(c_ns)-1):
        minIdx = i

        for j in range(i+1, len(c_ns)):

            if asc:
                if c_ns[minIdx] > c_ns[j]:
                    minIdx = j
            else:
                if c_ns[minIdx] < c_ns[j]:
                    minIdx = j

        c_ns[i],c_ns[minIdx] = c_ns[minIdx],c_ns[i]
        # print(f'nums: {c_ns}')

    return c_ns

코드2

import random
import selectMod

if __name__ == '__main__':

    nums = random.sample(range(1, 21), 10)

    print(f'not sorted nums: \t {nums}')
    result = selectMod.sortSelectAlgorithm(nums)
    print(f'sorted nums by ASC: {result}')

    print(f'not sorted nums: \t {nums}')
    result = selectMod.sortSelectAlgorithm(nums, asc=False)
    print(f'sorted nums by DESC: {result}')

출력

---

병합정렬 알고리즘

• 숫자로 이루어진 리스트를 병합정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자.

코드1

def mSort(ns, asc=True):
    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    leftNums = mSort(ns[0:midIdx], asc=asc)
    rightNums = mSort(ns[midIdx:len(ns)], asc=asc)

    mergedNums = []
    leftIdx = 0; rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):
        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1
        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergedNums.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                mergedNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergedNums += leftNums[leftIdx]
    mergedNums += rightNums[rightIdx]

    print(f'mergeNums: {mergedNums}')
    return mergedNums

코드2

import random
import mergeAlgorithm

rNums = random.sample(range(1,101), 20)
print(f'rNums: {rNums}')
print(f'mergeAlgorithm.mSort(rNums): {mergeAlgorithm.mSort(rNums)}')

---