Day48. 알고리즘 문풀 (2)

[연습문제] 정렬 알고리즘(01)

• [연습문제] 정렬 알고리즘(1)

• 버블정렬 알고리즘
  
  
  숫자로 이루어진 리스트를 버블정렬 알고리즘을 이용해서 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자!
  (단 정렬하는 과정도 출력하도록 한다!)

<실행파일코드>

import random
import module_bubbleAlgorithm as ba

if __name__ == '__main__':

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

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

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

<모듈파일코드>

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

[연습문제] 정렬 알고리즘(02)

• [연습문제] 정렬 알고리즘(2)

• 삽입정렬 알고리즘
  
  
  숫자로 이루어진 리스트를 삽입정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자!
  (단, 정렬하는 과정도 출력하도록 한다!)

<실행파일코드>

import random
import module_insertSort as mis

if __name__ == '__main__':

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

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

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

<모듈파일코드>

import copy

def sortInsertAlgorithim(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:   # 내림차순 decending
            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

[연습문제] 정렬 알고리즘(03)

• [연습문제] 정렬 알고리즘(3)

• 선택정렬 알고리즘
  
  
  숫자로 이루어진 리스트를 선택정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자!
  (단 정렬하는 과정도 출력하도록 한다!)

<실행파일코드>

import random
import module_selectSort as mss

if __name__ == '__main__':

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

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

    print('')

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

<모듈파일코드>

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: # ascending
                if c_ns[minIdx] > c_ns[j]:
                    minIdx = j

            else:   # descending
                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

[연습문제] 정렬 알고리즘(04)

• [연습문제] 정렬 알고리즘(4)

• 병합정렬 알고리즘
  
  
  숫자로 이루어진 리스트를 병합정렬 알고리즘을 이용해서 오름차순과
  내림차순으로 정렬하는 모듈을 만들어보자!
  (단, 정렬하는 과정도 출력하도록 한다!)
  
  
  중앙값으로 분할 분할 분할 한개까지 분할한 뒤 병합!
  (병합할 때 작은것을 앞으로 큰 것을 뒤로 하며 병합!)
  
  
  분할 , 병합이 반복 된다 -> 재귀함수를 사용한다

<실행파일코드>

import random
import module_mergeSort as mms

rNums = random.sample(range(1, 101), 20)
print(f'rNums : {rNums}')
print(f'mms.mSort(rNums) by ASC : {mms.mSort(rNums)}')
print(f'mms.mSort(rNums) by DESC : {mms.mSort(rNums, asc = False)}')

<모듈파일코드>

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)

    mergeNums = []
    leftIdx = 0
    rightIdx = 0

    while leftIdx < len(leftNums) and rightIdx < len(rightNums):

        if asc:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

        else:
            if leftNums[leftIdx] > rightNums[rightIdx]:
                mergeNums.append(leftNums[leftIdx])
                leftIdx += 1

            else:
                mergeNums.append(rightNums[rightIdx])
                rightIdx += 1

    mergeNums += leftNums[leftIdx:]
    mergeNums += rightNums[rightIdx:]

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