CS50 4. 알고리즘(3) - 정렬 알고리즘의 실행시간, 재귀, 병합 정렬

실행시간의 상한

• O(n^2): 선택 정렬, 버블 정렬
• O(n log n) 병합 정렬
• O(n): 선형 검색
• O(log n): 이진 검색
• O(1)

실행시간의 하한

• Ω(n^2): 선택 정렬, 버블 정렬
• Ω(n log n) 병합 정렬
• Ω(n) 버블 정렬
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

 

버블 정렬을 좀 더 잘 할 수 있는 방법

만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면?

 

원래 의사 코드는 아래와 같다.

여기서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것

따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 다음과 같이 바꿀 수 있다.

 

따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 된다. 상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것

 

재귀

• 함수가 본인 스스로를 호출해서 사용할 수 있는지? 이에 대한 대답은 할 수 있다 이며, 이러한 것을 재귀(Recursion)라고 부른다.

 

아래와 같이 피라미드 모양을 출력하기 위해 다음과 같은 코드를 작성할 수 있다.

 

#

##

###

####

 

• 높이를 입력 받아 중첩 루프를 통해 피라미드를 출력해주는 draw 함수를 정의
• 여기서 꼭 중첩 루프를 써야만 할까? 사실 바깥 쪽 루프는 안 쪽 루프에서 수행하는 내용을 반복하도록 하는 것일 뿐
• 따라서 바깥 쪽 루프를 없앤 draw함수를 만들고, 이를 ‘재귀적으로’ 호출하도록 해서 똑같은 작업을 수행할 수 있다.
• 즉, draw 함수 안에서 draw 함수를 호출 하는 것. 아래 코드와 같이 수정할 수 있다.

 

• draw 함수 안에서 draw 함수를 다시 호출 하는 부분을 유의
• h라는 높이를 받았을 때, h-1 높이로 draw 함수를 먼저 호출하고, 그 후에 h 만큼의 #을 출력.
• 여기서 내부적으로 호출된 draw 함수를 따라가다 보면 h = 0인 상황이 오게 된다.
• 따라서 그 때는 아무것도 출력을 하지 않도록 하는 조건문을 추가해줘야 한다.
• 이렇게 재귀를 사용하면 중첩 루프를 사용하지 않고도 하나의 함수로 동일한 작업을 수행할 수 있다.

※ 반복문을 쓸 수 있는데도 재귀를 사용하는 이유는 ? 루프를 중첩하게 되면 가독성이 떨어질 수 있고 변수도 더 많이 선언 해줘야 한다. 하지만 재귀를 사용하면 변수도 줄일 수 있고 가독성도 늘어나 메모리 공간도 아끼고 심미적으로 보기 괜찮다. 코드를 좀 더 간결하게 만들 수 있다.

 

병합 정렬

• 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식
• 그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽다.

----------------------------------------------------------------------------------------------------------------------
마찬가지로 다음 숫자들을 오름차순으로 정렬해 보겠습니다.

 

7 4 5 2 6 3 8 1

 

먼저 숫자들을 반으로 나눕니다.

 

7 4 5 2 | 6 3 8 1

 

그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눠봅니다.

 

7 4 | 5 2 | 6 3 8 1

 

마지막으로 한 번 더 나눠봅니다.

 

7 | 4 | 5 2 | 6 3 8 1

 

이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합합니다.

단, 이 때 작은 숫자가 먼저 오도록 합니다. 4와 7의 순서를 바꿔서 병합하는 것이죠.

 

4 7 | 5 2 | 6 3 8 1

 

마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있습니다.

 

4 7 | 2 5 | 6 3 8 1

 

그럼 이제 4 7과 2 5 두 개의 부분들을 병합하겠습니다.

각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져옵니다.

즉, 4와 2를 먼저 비교해서 2를 가져옵니다. 그 후에 4와 5를 비교해서 4를 가져옵니다.

그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져옵니다.

 

2 4 5 7 | 6 3 8 1

 

이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 거칩니다. 

 

2 4 5 7 | 1 3 6 8

 

마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합합니다.

2와 1을 비교하고, 1을 가져옵니다. 2와 3을 비교하고, 2를 가져옵니다. 4와 3을 비교하고, 3을 가져옵니다.

4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료됩니다.

 

1 2 3 4 5 6 7 8

 

전체 과정을 요약해서 도식화해보면 아래와 같습니다.

 

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과입니다.

4   7 | 2   5 | 3   6 | 1   8 → 숫자 1개씩을 정렬하여 병합한 결과입니다.

2   4   5   7 | 1   3   6   8 → 숫자 2개씩을 정렬하여 병합한 결과입니다.

1   2   3   4   5   6   7   8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과입니다. 

 

이러한 방법을 ‘병합 정렬’ 이라고 합니다.

----------------------------------------------------------------------------------------------------------------------

 

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

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문! 

실행 시간의 하한도 역시 Ω(n log n). 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문.

 

※ 병합 정렬을 선택 정렬이나 버블 정렬과 비교했을 때 장점과 단점은 무엇이 있을까요? 가장큰 장점은 무엇보다 실행시간이 다른 두 정렬에 비해 빠르다는 것이고 단점이라면 이미 정렬이 되어있다면 버블정렬의 하한선이 병합정렬보다 더 빠르다는 것 즉, 더 빠르게는 할 수 없다는 얘기.