알고리즘 첫걸음 C&자바편 - 챕터 8. 재귀 호출과 퀵 정렬

요즘 인프런과 유튜브에서 '널널한 개발자'님의 강의를 듣고 있는데

코딩이 어렵다고 하는 사람들은 문법공부와 동시에 이 문법을 적용해

로직 구현까지 한번에 해내려고 해서 힘들어하는 거라고 한다. 

 

그래서 강사님이 추천하시는 프로그래밍 공부법은 무작정 코드부터 적으려고 하지말고

'생각'을 많이 해보고 이를 단순 무식할 정도로 세세하게 글로 작성해보는 거다.

그래서 나도 이번 챕터를 공부할 때부터는 글로 많이 적으면서 정리해보려고 노력 중이다.

 

챕터 8은 '재귀 호출' 과 '퀵 정렬'에 대해 다룬다.

 

재귀 호출(Recursive call)은 '함수 안에서 자기 자신을 호출하여 반복 처리한다'는 프로그래밍 기법이다.

while이나 for 문을 통한 반복과는 전혀 다른 방식이다.

 

재귀 호출에서 주의해야 할 점은 반드시 '재귀 호출을 종료하는 조건'을 준비해야 한다는 것이다.

그렇지 않으면 영원히 반복하는 코드를 작성하게 된다.

 

이 재취호출의 단골 주제가 바로 'factorial 함수'인데

은근 코드로 나타내면 단순하다.

 

#include <stdio.h>

int factorial (int n) {
	if(n == 0) {
    	return 1;
    } else {
    	return n * factorial(n-1)
    }
}

int main() {
	int ans;
    
    ans = factorial(5);
    printf("%d\n", ans);
    
    return 0;
    
}

출력결과는 5 펙토리얼의 값인 5x4x3x2x1x1=120이 나온다.

if (n == 0) 이 부분은 0의 계승은 1로 정해져 있기 때문에 조건을 추가한 것이다.

 

main 함수에서 factorial(5)를 ans 변수에 넣었는데

연산과정은 factorial 함수에 계속해서 5부터 1까지 쭉 들어갈 것이고

n이 0일 때는 1이 반환될 것이다.

 

이제 이 재귀호출의 개념을 적용해 '퀵 정렬'을 구현해야 한다.

 

이 책 전반에 걸쳐 '선택 정렬,' '버블 정렬,' '삽입 정렬' 등 여러 정렬 알고리즘을 배웠는데

이번 퀵 정렬이 가장 복잡한 것 같다.

 

우선 퀵 정렬은 이름에서부터 quick(빠른) 느낌이 든다.

실제로 선택 정렬은 시간 복잡도가 O(N^2)인데 비해

퀵 정렬은 평균적으로 O(nlogn)이다.

 

퀵 정렬의 작동 방식은 다음과 같다.

 

1. 기준값이 되는 요소를 하나 선택

2. 기준값보다 작은 값과 큰 값, 이렇게 두 그룹으로 나누기를 반복

3. 두 그룹이 하나가 될 때까지 1,2번 과정을 반복

 

이때 보통 기준값을 pivot이라고 하는데

이 기준값을 중심으로 분할된 양쪽 배열에서

재귀적으로 sorting하는 함수가 작동하기 때문에 앞서 재귀 호출을 배운 것이다.

 

퀵 정렬에서 최악의 경우는 이 기준값이 배열의 최솟값이나 최댓값일 경우다.

이때는 선택 정렬과 동일한 시간 복잡도를 가진다.

이를 방지하기 위해 '임의로 선택한 3개 요소의 중간값'을 기준값으로 설정하는 알고리즘도 있다.

이를 활용할 경우 정렬의 성능을 높일 수 있다.