[CS50] 4.알고리즘, Algorithm (2)

버블정렬 알고리즘의 실행시간 단축

앞서 버블정렬의 알고리즘은 n개의 값을 정리할 때 인접한 값끼리 n-1번 비교하고 교환하는 작업을 총 n-1번 반복하도록 했고 그 결과 실행시간의 상한과 하한 모두 n² 가 되었다.

그런데 여기에서 조금이라도 시간을 줄일 방법으로, 매번 전체 값의 비교를 n-1번 하도록 하는대신 더이상 정렬을 하지 않아도 될 때까지만 반복하도록 하면 어떻게 될까?

Repeat until no swaps :  #교환이 일어나지 않을 때까지만 반복
	for i from 0 to n-2: #0번 자리부터 끝에서 두번째 자리까지
		if i'th and i+1th elements are out of order #i번째 자리와 그 옆의 값이 정렬이 안되어있다면
		swap places  #위치를 바꿔라

바깥쪽 루프의 조건을 ‘교환이 일어나지 않을 때까지’로 하게 되면 교환이 있을 때는 여전히 O(n²)이 되지만, 아무 교환도 일어나지 않는 최선의 상황에서는 값을 n-1회 확인만 하면 되므로 Ω(n)이 되고 상황에 따라서는 선택 정렬보다 더 빠른 방법이 될 수 있게 되었다.

재귀 (Recursion)

파이썬을 배우는 초기단계에서 for 문을 사용하여 삼각형을 출력하는 코드를 만들었을 때는 다음과 같은 코드를 이용했다.

height=int(input('삼각형 높이:'))

def draw(h):
    for i in range(1,h+1):
        for j in range(0,i):
            print('#',end='')
        print()
    print()

draw(height)

삼각형의 높이를 입력받아 중첩 루프를 통해 출력하도록 했었는데, 이 예시의 경우 비교적 간단한 내용이기 때문에 코드가 복잡해 보이지 않지만 만약 루프 안의 코드가 조금이라도 더 복잡했다면 반복해서 루프를 작성하기가 어려워졌을 것이다.

이런 경우 중첩 루프 대신 함수가 본인 스스로를 호출해서 사용하는 재귀 함수를 다음과 같이 작성할 수 있다.

height=int(input('삼각형 높이:'))

def draw(h):
    if h == 0:
        return
    draw(h-1)
    for i in range(0, h):
        print('#', end='')
    print()

draw(height)

물론 재귀함수를 사용하면 메모리 사용량이 많아지고 스택 오버플로우로 이어질 수 있지만 이렇게 내부적으로 반복되는 알고리즘은 아래 세 가지에 해당되는 경우라면 재귀함수의 사용을 고려해볼 수 있다.

1. 알고리즘 자체가 재귀적인 표현이 자연스러운 경우 (ex. 피보나치 수열)
2. 변수 사용을 줄여 변수의 변화로 프로그램에 오류가 생기는 경우를 줄이고 싶을 때
3. 코드 가독성을 향상시켜야 할 경우

병합정렬

병합정렬은 재귀를 활용한 정렬 알고리즘으로 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 의사코드로는 다음과 같다.

If only one item
	return
Else
	Sort left half of items
	Sort right half of items
	Merge sorted halves

먼저 배열을 왼쪽과 오른쪽으로 반씩 나누고, 나눠진 반에서 또다시 반으로 나누며 하나의 값만 남아 있는 상태까지 나눈다. 그 다음 왼쪽과 오른쪽의 값을 비교하여 정렬해서 합치고, 합친 배열끼리 다시 비교하여 합치는 것을 반복한다.

여기서 숫자를 반으로 나누는데 O(log n)의 시간이 들고, 반으로 나눈 부분들을 다시 병합하는데 O(n)의 시간이 걸리기 때문에 총 시간의 상한은 O(n log n)이 된다. 그리고 실행시간의 하한 역시 숫자들의 정렬여부와 상관없이 반복이 이루어지므로 Ω(n log n)이 된다.

+ 이렇게 시간의 상한과 하한이 같은 경우 θ(세타, theta)를 사용하여 표기한다. 병합정렬은 θ(n log n) 이고, 선택정렬은 θ(n²) 라고 할 수 있다.