[알고리즘] 병합 정렬, 퀵 정렬 (with 재귀 함수)

1. 재귀함수란

 

2. 분할 정복이란

 

3. 병합 정렬

• 병합 정렬이란
• 시간복잡도와 공간복잡도
• 구현

3. 퀵 정렬

• 퀵 정렬이란
• 시간복잡도와 공간복잡도
• 구현

---

1. 재귀 함수 Recursive Function

• 함수 내부에서 자기 자신을 다시 호출하여 작업을 수행하는 프로그래밍 기법 (예: 팩토리얼(Factorial))
• 구성요소
  1. 기본 사례(Base Case) : 재귀호출을 멈추고 값을 반환하는 종료 조건
     -> 종료 조건이 없으면 무한 루프에 빠지거나 스택 오버플로우가 발생할 수 있음
     
  2. 재귀 사례(Recursive Case) : 함수가 자기 자신을 호출하는 조건 및 연산
• 장점 : 코드 간결. 가독성 굳. 복잡한 알고리즘을 단순한 논리로 표현
• 단점 :
  • 함수 호출될 때마다 호출 정보가 메모리 스택에 쌓임
  • 종료 조건이 잘못되거나 데이터가 너무 크면 스택 오버플로우 에러가 발생할 수 있음
• 일반함수와 재귀함수 차이점

	일반 함수	재귀 함수
메모리	변수 재사용. 추가 메모리 할당 없음	호출마다 메모리 새로 할당
속도	상대적으로 빠름	함수 호출 오버헤드로 상대적으로 느림
위험성	무한 루프 시 CPU 점유율이 올라갈 수 있으나 메모리 에러는 드묾	종료 조건이 없으면 스택 오버플로우(메모리 부족)

---

2. 분할 정복 Divide and Conquer

1. 분할(Divide) : 해결하기 힘든 거대한 문제를 유사한 형태의 여러 하위 문제로 쪼개고
   
   
2. 정복(Conquer) : 각각을 재귀적으로 해결한 뒤
   
   
3. 결합(Combine) : 그 결과를 합쳐
   
   
4. 최종 해답을 얻어내는 알고리즘 설계 기법

• 분할 정복을 활용한 알고리즘 : 병합 정렬(합병 정렬), 퀵 정렬, 이진 탐색, 거듭제곱 연산
  
  
• 장점 : 복잡하고 거대한 문제를 효율적으로 해결 가능
  
  
• 단점 : 재귀 함수 사용으로 스택 오버플로우가 발생할 수 있음

 

---

3. 병합 정렬 Merge Sort

병합 정렬

1. 병합 정렬이란

• 하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤 각자 계산하고 나중에 합치는 방법
• 동작 방식
  1. 배열의 길이는 최소 1보다 커야 한다.
     (= 배열 길이가 1 이하이면 이미 정렬된 것으로 본다.)
     
     
  2. 분할(Divide) : 정렬되지 않은 배열을 절반으로 잘라 비슷한 크기의 두 파티션으로 나눈다. (원소가 2개가 남을 때까지 분할)
     
     
  3. 정복(Conquer) : 분할이 완료되면 나눈 각 파티션을 재귀적으로 호출해 정렬한다.
     
     
  4. 결합(Combine) : 정렬이 완료되면 나누었던 두 파티션을 하나의 정렬된 배열로 병합한다. (이 때 정렬된 배열이 임시 배열에 저장된다)
     
     
  5. 복사(Copy) : 임시 배열에 저장된 결과를 원래 배열에 복사한다.
• 장점 :
  • 연결리스트를 사용할 경우, 링크 인덱스만 변경하면 되므로 이동 연산이 줄어듦 (추가 메모리가 필요하지 않음)
  • 퀵 정렬과 비교했을 때 데이터 분포에 영향을 받지 않음
• 단점 : 
  • 배열을 사용할 경우, 추가적인 메모리(임시 배열)이 필요
  • 이동 연산이 많아, 레코드 개수가 클 경우에는 비효율적

 

2. 시간복잡도와 공간복잡도

• 시간복잡도 : O(n log n)
  • 배열의 개수가 1개가 될 때까지 분할 하므로 n번의 합병
  • 각 합병 단계마다 원소 개수 만큼의 비교와 이동이 이루어짐
  • 배열을 반씩 분할해가며 정렬
• 공간복잡도 : O(n) 
  • 데이터 개수가 n일 때, 정렬과정에서 추가적 메모리(임시 배열) 필요

 

3. 구현

1. 크게 분할 및 정복을 수행하는 함수(merge_sort)와 결합(merge)을 수행하는 함수로 나눈다
2. merge_sort를 먼저 만든다
3. 배열의 길이가 1이 될 때까지 재귀함수를 호출한다
4. 비슷한 크기로 나누기 위해 mid 변수를 생성한다
5. mid를 기준으로 배열을 left, right로 나눠 임시 저장한다
6. left와 right를 계속 분할한다
7. merge 함수를 사용해 최종 정렬을 해준다
8. 배열의 길이가 1이라면 배열 그대로 반환한다
9. merge를 만든다
10. 마지막으로 최종 정렬된 결과를 담을 리스트 변수(result)를 하나 생성한다
11. left, right의 각 배열의 현재 위치를 가리키는 인덱스를 생성한다
12. left 배열의 인덱스가 배열 길이보다 작고, right 배열의 인덱스도 배열 길이보다 작은 동안 반복한다
13. left, right 배열의 값을 비교하고 더 작은  값을 result에 넣고 인덱스에 1을 더한다 (다음 데이터로)
14. result에 나머지 배열을 모두 담고 반환한다

# 합병 정렬
# 1. 분할 및 정복 함수
def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2

        left = arr[:mid]
        right = arr[mid:]

        return merge(merge_sort(left), merge_sort(right))
    return arr

# 2. 결합 함수
def merge(left, right):
    result = []     # 최종 정렬된 결과를 담을 리스트
    i, j = 0, 0     # 각 배열의 현재 위치를 가리키는 인덱스

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result = result + left[i:]      # if문으로 만들어도 좋음
    result = result + right[j:]

    return result

# 합병 정렬 수행
print(merge_sort([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]
print(merge_sort([5, 4, 3, 2, 1]))  # [1, 2, 3, 4, 5]
print(merge_sort([1]))              # [1]

---

4. 퀵 정렬 Quick Sort

1. 퀵 정렬이란

• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 매우 빠르게 정렬을 수행하는 알고리즘
• 동작방식
  1. 피벗을 지정한다.
     (첫 번째 원소, 마지막 원소, 중간값, 무작위, 듀얼 피벗)
     
     
  2. 분할(Divide) : 배열을 피벗 기준으로 비균등하게 2개의 부분 배열로 분할한다.
     -> 피벗을 중심으로 왼쪽: 피벗보다 작은 요소들 / 오른쪽: 피벗보다 큰 요소들
     
     
  3. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
     
     
  4. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열로 합병한다.
  5. 배열 크기가 0이나 1이 될 때까지 반복한다.
• 장점 : 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않음
• 단점 : 정렬된 배열에 대해서는 불균형 분할로 인해 더 오랜 시간이 소요됨

2. 시간복잡도와 공간복잡도

• 시간복잡도 : 평균 O(n log n)    /    최악 O(n²)  
  • 배열의 개수가 1이 될 때까지 분할하므로 log(n)번 분할
    또한 분할할 때마다 피벗 기준으로 정렬되기 때문에, n번의 비교 연산이 이루어짐 -> 평균 O(n log n)
  • 이미 정렬된 배열일 경우 분할이 n번만큼 이루어짐 ->  최악 O(n²)
• 공간복잡도 : O(n) 
  • 데이터 개수가 n일 때, 주어진 배열 내에서 교환이 이루어짐

3. 구현

1. 병합 정렬과 마찬가지로 배열의 길이가 1이 될 때까지 반복한다
2. 배열의 첫 요소를 피벗으로 선택하고 저장할 변수(p)를 생성한다
3. 리스트 컴프리헨션을 사용하여 left 배열에는 p보다 작은 수들을, middle에는 p와 같은 수들을, right 배열에는 p보다 큰 수들을 담는다
4. 이를 반복한다
5. left, middle, right를 병합하여 리턴한다

# 퀵 정렬
def quick_sort(arr):
    if len(arr) > 1:
        p = arr[0]      # 배열의 첫 요소를 피벗으로 선택

        left = [x for x in arr if x < p]
        middle = [x for x in arr if x == p]
        right = [x for x in arr if x > p]

        return quick_sort(left) + middle + quick_sort(right)
    return arr

print(quick_sort([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]

---

* 정렬 알고리즘들은 코드를 읽어보기만 했지 직접 구현해보는 것은 처음이었다. 이번 과제도 시간이 꽤 소요되었지만 그만큼 분명 얻어가는 것은 있다. 재귀 함수는 당연히 종료 조건이 있어야 한다. 알고리즘 수업에서 종료 조건을 채우는 문제를 틀렸던 기억 덕분에 잘 기억하고 있었다. 분할 정복이라는 개념도 알고 있었지만 한 번 더 정리하여 어떤 알고리즘에 쓰이는지 확실하게 알게 되었다.