Day46. 알고리즘 (7)

병합 정렬 - 이론

• 병합정렬 이란?

• 자료구조를 분할하고 각각의 분할된 자료구조를 정렬한 후 다시 병합하여 정렬한다!
  
  
  8 1 4 3 2 5 10 6
  ↙ ↘
  [8 1 4 3][2 5 10 6]
  ↙ ↘ ↙ ↘
  [8 1][4 3] [2 5][10 6]
  ↓
  8 1 4 3 2 5 10 6
  나눴던 단계부터 서로서로서로 비교
  1 8 3 4 2 5 6 10
  ↓
  1 3 4 8 2 5 6 10
  ↓
  1 2 3 4 5 6 8 10
  
  
  분할하고 또 분할하고 => 재귀함수가 사용된다!

def mergeSort(ns):

    if len(ns) < 2: # len(ns)가 2보다 작다는 것은 수가 하나 남을 때까지 분할 했다는 것!
        return ns

    # 분할하는 부분
    midIdx = len(ns) // 2   # 중간 데이터의 인덱스 값 , 이걸 기준으로 나누기 시작!
    leftNums = mergeSort(ns[0:midIdx])  # 재귀함수 사용!
    rightNums = mergeSort(ns[midIdx:len(ns)])   # 재귀함수 사용!


    # 병합하는 부분

    mergeNums = []
    leftIdx = 0
    rightIdx = 0

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

        if leftNums[leftIdx] < rightNums[rightIdx]:   # 자리바꿈하는 부분
            mergeNums.append(leftNums[leftIdx])
            leftIdx += 1

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

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

    return mergeNums






nums = [8, 1, 4, 3, 2, 5, 10, 6]

print(f'mergeSort(nums) : {mergeSort(nums)}')

병합 정렬 - 실습

• 병합정렬(실습)

• 분할하고, 다시 합치자!
  
  
  실습
  1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자!
  
  
  요구 사항1) 병합정렬 알고리즘을 이용한 난수 정렬 모듈 구현
  요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

<실행파일코드>

import random as rd
import module_mergeSort as ms

rNums = rd.sample(range(1, 101), 10)    # 1~100까지의 난수 10개
print(f'not sorted rNums : {rNums}')
print(f'sorted rNums ASC : {ms.mergeSort(rNums)}')  # 오름차순!
print(f'sorted rNums DESC : {ms.mergeSort(rNums, asc=False)}')  # 내림차순!

<모듈파일코드>

def mergeSort(ns, asc = True):

    if len(ns) < 2: # 한자리수까지 쪼개기!
        return ns

    # 분할하는 단계
    midIdx = len(ns) // 2
    leftNums = mergeSort(ns[0:midIdx], asc = asc)  # 분할해서 왼쪽에 있는 숫자들    # asc = asc 재귀적으로 모두 적용하려면 매우 중요하다!!!
    rightNums = mergeSort(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 = mergeNums + leftNums[leftIdx:]
    mergeNums = mergeNums + rightNums[rightIdx:]

    return mergeNums

퀵 정렬 - 이론

• 퀵 정렬

• 기준보다 작은 값과 큰 값을 분리한다!
  
  
  기준 값보다 작은 값과 큰 값으로 분리한 후 다시 합친다!
  
  
  8 1 4 3 2 5 4 10 6 8
  ↓
  1 4 3 2 4 5 8 10 6 8
  ↓ ↓ ↓
  1 2 3 4 4 5 6 8 8 10

def qSort(ns):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2   # 기준값 인덱스
    midVal = ns[midIdx] # 기준값

    smallNums = []  # 기준값 보다 작은 수들 (왼쪽)
    sameNums = []   # 기준값이랑 같은 값
    bigNums = []    # 기준값 보다 큰 수들 (오른쪽)

    for n in ns:

        if n < midVal:
            smallNums.append(n)

        elif n == midVal:
            sameNums.append(n)

        else:
            bigNums.append(n)

    return qSort(smallNums) + sameNums + qSort(bigNums)


nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]

print(f'qSort(nums) : {qSort(nums)}')

퀵 정렬 - 실습

• 퀵 정렬(실습)

• 실습
  1부터 100까지의 난수 10개를 생성하고, 다음의 요구 사항을 만족하는 모듈을 만들어보자!
  
  
  요구 사항1) 병합정렬 알고리즘을 이용한 난수 정렬 모듈 구현
  요구 사항2) 위의 모듈에 오름차순과 내림차순을 선택할 수 있는 옵션 추가

<실행파일코드>

import random as rd
import module_quickSort as qs

rNums = rd.sample(range(1, 100), 10)
print(f'not sorted rNums : {rNums}')
print(f' sorted rNums ASC : {qs.qSort(rNums)}')
print(f' sorted rNums DESC : {qs.qSort(rNums, asc = False)}')

<모듈파일코드>

def qSort(ns, asc = True):

    if len(ns) < 2:
        return ns

    midIdx = len(ns) // 2
    midVal = ns[midIdx]

    smallNums = []
    sameNums = []
    bigNums = []

    for i in ns:

        if i < midVal:  # 작은수!
            smallNums.append(i)

        elif i == midVal:
            sameNums.append(i)

        else:
            bigNums.append(i)

    if asc:
        return qSort(smallNums, asc = asc) + sameNums + qSort(bigNums, asc = asc)   # asc = asc 매우 중요합니다!!!
    else:
        return qSort(bigNums, asc = asc) + sameNums + qSort(smallNums, asc = asc)   # asc = asc 매우 중요합니다!!!