제로베이스 데이터 파트타임 스쿨 학습 일지 [25.05.04]

[강의 요약]

[Part 03. 자료구조&알고리즘 with Python_ Ch 03. 알고리즘] 강의 수강

27_병합 정렬부터 30_퀵 정렬(실습)까지 강의 수강하였음

🐢 100일 챌린지 🔥 : [▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰▰░                                       ] 49/100일 (49%)

연휴에도 쉴 수 없다... 악으로 깡으로 버텨라

 

 

 

[27_병합 정렬]

▶ 병합 정렬(Merge Sort)이란?

리스트를 반으로 나눠서 각각 정렬한 후, 다시 합치는 정렬 알고리즘을 말한다.

대표적인 분할 정복 알고리즘이고, 시간복잡도는 O(n log n)이어서 효율적 + 안정적인 정렬 방식이다.

 

이해를 위해서 강의자료 이미지를 가져왔다.

 

 

▶ 코드 : 병합 정렬 알고리즘을 재귀적으로 구현

def mSort(ns):
    if len(ns) < 2:
        return ns

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

    mergedNums = []
    leftIdx = 0; rightIdx = 0

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

    mergedNums = mergedNums + leftNums[leftIdx:]
    mergedNums = mergedNums + rightNums[rightIdx:]
    print(f'mergedNums: {mergedNums}')
    return mergedNums


nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mergedNums: {mSort(nums)}')

[출력 결과]

중간중간 병합된 결과를 출력해서 과정을 추적할 수 있다.

mergedNums: [1, 8]
mergedNums: [3, 4]
mergedNums: [1, 3, 4, 8]
mergedNums: [2, 5]
mergedNums: [6, 10]
mergedNums: [2, 5, 6, 10]
mergedNums: [1, 2, 3, 4, 5, 6, 8, 10]
mergedNums: [1, 2, 3, 4, 5, 6, 8, 10]

 

 

 

[28_병합 정렬(실습)]

▶ 실습 문제

 

 

▶ sortMod.py : 병합 정렬 함수 모듈

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:], 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:]
    return mergedNums

 

 

▶ mergeEx.py : 메인 실행 파일

import random as rd
import sortMod as sm

rNums = rd.sample(range(1, 101), 10)
print(f'not sorted rNums: {sm.mSort(rNums)}')
print(f'merge sorted rNums by ASC: {sm.mSort(rNums)}')
print(f'merge sorted rNums by DESC: {sm.mSort(rNums, asc=False)}')

asc 매개변수 : True면 오름차순, False면 내림차순 정렬 수행

[출력 결과]

not sorted rNums: [57, 4, 90, 28, 33, 71, 12, 86, 1, 42]
merge sorted rNums by ASC: [1, 4, 12, 28, 33, 42, 57, 71, 86, 90]
merge sorted rNums by DESC: [90, 86, 71, 57, 42, 33, 28, 12, 4, 1]

 

 

 

[29_퀵 정렬]

▶ 퀵 정렬(Quick Sort)이란?

기준값(pivot)을 중심으로 작은 값, 같은 값, 큰 값으로 분리하고

이 과정을 재귀적으로 반복하는 정렬 방식

 

불안정 정렬이지만 평균 성능이 매우 우수하고

평균 시간복잡도는 O(n log n)이며

최악의 경우 시간복잡도는 O(n²)이다. (이미 정렬된 리스트 등의 경우)

 

 

▶ 코드

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)
    
    # 분할된 리스트에 대해 재귀적으로 qSort 수행        
	# 세 리스트를 순서대로 이어 붙여 리턴
    return qSort(smallNums) + sameNums + qSort(bigNums)


nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
print(qSort(nums))

피벗 중심 분할 → 재귀 호출 → 합치기

[출력 결과]

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

 

[30_퀵 정렬(실습)]

▶ 실습 문제

 

 

▶ sortMod.py : 퀵 정렬 함수

def qSort(ns, asc=True):
    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)

    if asc:
        return qSort(smallNums, asc=asc) + sameNums + qSort(bigNums, asc=asc)
    else:
        return qSort(bigNums, asc=asc) + sameNums + qSort(smallNums, asc=asc)

퀵 정렬 (분할 → 재귀 → 병합)

 

 

▶ quickEx.py : 실행 코드

import random as rd
import sortMod as sm

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

랜덤 숫자 10개 생성

qSort() 함수를 이용해 오름차순 / 내림차순 출력

[출력 결과]

not sorted rNums: [17, 3, 89, 52, 41, 26, 78, 8, 34, 60]
quick sorted rNums by ASC: [3, 8, 17, 26, 34, 41, 52, 60, 78, 89]
quick sorted rNums by DESC: [89, 78, 60, 52, 41, 34, 26, 17, 8, 3]

 

 

 

[나의 생각 정리]

병합 정렬과 퀵 정렬은 구조는 비슷해 보이지만, 동작 원리와 장단점은 달랐다.

두 정렬 모두 재귀 기반으로 작동하면서 병합 정렬은 일정한 성능, 퀵 정렬은 중앙값 기준으로 빠른 평균 성능을 보였다.

 

 

[적용점]

병합 정렬 = 안정적, 퀵 정렬 = 속도 중심. 이므로 데이터의 특성과 상황에 따라 선택해서 사용하면 된다.

 

 

“이 글은 제로베이스 데이터 스쿨 주 3일반 강의 자료 일부를 발췌하여 작성되었습니다.”