[CS50] 알고리즘 - 정렬 알고리즘(Merge Sort)

재귀함수

• 내부에서 자기 자신을 호출하여 재참조하는 구조의 함수를 말한다.
• 피보나치 수열, 하노이의 탑 알고리즘이나 1부터 n까지의 숫자 합, 팩토리얼(!) 같은 연산을 할 때 사용한다.
• 특징
  1. 코드의 가독성이 좋다.
  2. 스택 메모리를 사용한다. (스택 오버플로우가 발생할 수 있다.)

 

합병 정렬은 버블 정렬이나 선택정렬보다 뛰어난 알고리즘으로 널리 알려져있다.

 

합병 정렬(Merge Sort)

• 병합 정렬 또는 합병 정렬이라고 한다.
• 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

 

합병 정렬 알고리즘 예시

어떤 알고리즘을 얘기할 때, 무언가를 절반으로 계속 나눈다면 로그(log)함수로 표현할 수 있다.
크기 8인 배열을 쪼개서 크기 1인 배열 8개로 만드는데 필요한 과정은 밑이 2인 log n이다.

 

 

 

합병 정렬 의사코드 

If only one item : 받은 입력에 항목이 하나라면 
    Return : 반환 
Else 
    Sort left half of items : 왼쪽 절반을 정렬
    Sort right half of items : 오른쪽 절반을 정렬
    Merge sorted halves : 병합! 하나의 배열로 합치기(정렬되도록)

=> 병합할 때마다 총 n개의 항목을 확인해야 한다. (ex. n=8, 4+4, 2+2+2+2 등) 

=> 나눌 수 있는 횟수는 log n번이다.

 

합병 정렬 시간 복잡도 

 

 

합병 정렬 실행 시간의 상한 : O(n log n)

 

합병 정렬 실행 시간의 하한 : Ω(n log n)

• 정렬이 되어 있는지 여부에 관계없이 반복문을 실행하며 비교를 해야 하므로 Ω(n log n)이다.
• 최선의 경우에서 버블 정렬처럼 더이상 교환이 일어나지 않을 때 멈추는 최적화 기법은 없다. 

버블 정렬과 비교해보기

• 장점 :  n²이 아니고 n log n 이므로 최악의 경우 훨씬 빠르다. 
• 단점 : 최선의 경우 시간 낭비를 한다. 

 

상한선을 개선하고 싶다면 하한선을 희생해야 할 수도 있다.

 

 

think about

1) 반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 무엇일까요?

재귀함수를 사용하면 반복문에 비해 코드 수를 줄일 수 있다.

 

 

David J. Malan의 강의

모두를 위한 컴퓨터 과학 (CS50 2019)

Comparison Sorting Visualization

정렬 알고리즘 비교