[알고리즘] # 0. Big-O / 시간 복잡도(Time Complexity)와 거품 정렬 (Bubble Sort)

알고리즘 공부를 시작하다보면 가장 먼저 마주하는 용어가 '시간 복잡도' 입니다. 이 시간복잡도가 어떤 꼴로 나오냐에 따라 알고리즘의 좋고나쁨을 알 수 있기 때문입니다.

 

우리 모두 수학을 싫어하는건 알지만 그래프를 하나 보도록 하겠습니다.

시간복잡도 그래프

너무 잘 나와있어서 설명이 필요없는 그래프긴 하나, 살펴보겠습니다.

X축은 Example Scale이라 보시면 되겠습니다. 얼마나 많은 양을 처리해야하는지인데요. Y축을 보면 그 양을 처리하는데 걸리는 시간이 나와있습니다.

---

어? 그러면 똑같은 문제의 양이 주어졌어도 푸는데 걸리는 시간이 짧을수록 좋겠네?

맞습니다. 위 그래프에 따르면 지수 함수에 가까워질 때 비효율적이고  로그 함수에 가까워질 때 효율적임을 보입니다.

---

그러면 어떤 이유에서 각각의 알고리즘의 꼴이 지수함수가 되고 로그함수가 되는거죠?

이 질문에 대한 설명을 위해 오늘 처음으로 만나볼 알고리즘은 '거품 정렬 (Bubble Sort)' 입니다.

왜 이름이 거품 정렬이냐면 정렬을 위해 숫자들이 바쁘게 움직이며 자리를 찾아가는 모습이  비눗방울이 날아다니는것 같다해서 붙여진 이름입니다. 

거품 정렬 <출처 - 👨🏻‍💻 Tech Interview (gyoogle.dev) 김규석님>

저는 봐도 잘 와닿진 않는데, 암튼 그렇게 이름이 붙여졌답니다.

거품 정렬은 가장 간단한 알고리즘입니다. 이 알고리즘은 주어진 데이터들을 짝지어서 모두 한번씩 비교를 해서 크고작음을 판단합니다. 여기까지만 읽어봐도 거품 정렬이 비효율적이구나라는 것이 느껴지실겁니다. 

만약 방대한 데이터를 다루게 될 때, 거품 정렬을 쓴다면 언제 그걸 다 일일이 비교하며 정렬해갈까요.

 

그래서 거품 정렬은 현업에서는 절대 안씁니다. 그러면 거품 정렬에 대한 시간복잡도 형태를 구해보도록 하겠습니다.

1부터 10까지 무작위로 나열된 데이터가 주어졌다고 생각합시다. 이를 오름차순 정렬하려고 해요. 만약 거품 정렬을 적용한다면  왼쪽에서 오른쪽으로 진행하면  내 오른쪽에 있는 숫자가 나보다 작다! 하면 자리를 바꿉니다.  이걸 오른쪽 끝까지 도달할 때까지 계속 반복하구요. 다시 왼쪽에서부터 시작해서 정렬을 또 반복합니다.

 

그러면 3 1 5 7 9 10 6 2 4 8 이라는 데이터에서 좀 더 우리가 진행해보면

3 1 5 7 9 6 10 2 4 8

3 1 5 7 9 6 2 10 4 8

3 1 5 7 9 6 2 4 10 8

3 1 5 7 9 6 2 4 8 10  으로 됩니다.  그러면 이제 다시 3으로 돌아가서 또 정렬을 반복하는겁니다.

 

즉, 데이터의 개수가 N개라 할 때 한번의 반복이 끝나더라도 또 N-1.. N-2... N-3... N-4...  마지막 1번의 반복.  이렇게가야 1 2 3 4 5 6 7 8 9 10 으로 정렬이 완성될 것입니다.

그림판 크기가 작아서 여기선 7개의 데이터 (민트색) 까지만 그려놨는데요. 7개의 데이터들이 자기 자신을 제외한 남은 데이터 모두와 비교분석을 하는데까지 걸리는 횟수는 총 21번입니다. 즉,  N(N-1)/2의 공식이 나오게 됩니다. N에다가 7을 넣으면  7개의 데이터를 분석하는데 걸린 횟수가 21. 라고 나오는거죠.

 

즉, 데이터 개수에 '제곱' 꼴이 되는 것입니다. 따라서 거품 정렬의 시간복잡도는 N^2입니다.

	Best	Average	Worst
1. Bubble Sort (New!)	N^2	N^2	N^2

 

그러면 이제 소스코드를 한번 보겠습니다.

정렬된 모습 (거품 정렬) / 사용 언어 : C

// # 0. Bubble Sort

#include <stdio.h>  // 사용 언어 : C


int main()

{
	int i,j,change;
	int num[10] = {3,9,1,4,10,7,8,2,5,6};
	
	for (i=0; i<10; i++)
	{
		for (j=0; j<i; j++)
		{
			if (num[i]<num[j])
			{
				change = num[i];
				num[i] = num[j];
				num[j] = change;
			}
		}
	}
	
	for (i=0; i<10; i++)
	{
		printf("%d ",num[i]);
	}
	
	
	return 0;
}

눈여겨 볼 점은 이중 for문과 if함수 블록에 있는 Swap구문입니다.

 

1) Outer Loop의 for문은 데이터가 총 10개이므로 10번 반복을 한다고 보시면 되구요.

2) Inner Loop의 for문은 두 수를 묶어서 비교를 해가는 것이므로 조건식을 j<i라고 해두었습니다.

 

i = 0인 경우엔 두 숫자가 아니므로 실행이 안되고,  i=1인 경우엔 j=0이 실행됩니다. 그러면 

num[i]는 -> num[1] / num[j]는 -> num[0]가 되니까  num[i]<num[j]인 경우는  왼쪽에 있는 숫자가 오른쪽에 있는 숫자보다 클 경우를 의미합니다.

 

즉, 오름차순 정렬을 원할 경우 num[i]<num[j]에 해당하는 애들을 swap시켜라! 라는 겁니다.

swap을 시키기 위해서는 두 수도 있지만 이 두 수를 swap시켜줄 매개체가 필요합니다. 그게 change 변수입니다.

change = num[i];
num[i] = num[j];
num[j] = change;

swap구문의 가장 기초적인 틀입니다. 어려울게 없이 매개체를 이용해서 두 수의 자리를 바꿔준 것입니다.