정렬 알고리즘 : 버블 정렬

버블정렬은 정렬의 대명사로 알려져 있는 이미 많은 사람들이 알고 있을만한 정렬 방법입니다. 버블정렬이라는 단어는 잘 모르더라도 알고리즘 내용을 보면 아! 이거! 라고 바로 알아 차릴 수 있을 것입니다. 버블정렬은 많은 사람들이 이해하기도 구현하고 상대적으로 쉬운데 하지만 그만큼 성능 면에선 아쉬운 부분이 있습니다. 이제 오름차순으로 버블정렬의 과정을 설명하겠습니다.

1.1 버블 정렬 : 이해와 구현

버블정렬은 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유 되어 버블정렬이라고 합니다. 자 이제 정렬되지 않은 숫자 3 2 4 1 이 있다고 가정하고 이것을 버블정렬로 정렬해봅시다.

 

숫자 3을 인덱스 0번이라고 하고 숫자 1은 인덱스 3이라고 합시다. 배열처럼 말이죠. 이제 단계 별로 설명하겠습니다.

1단계

1-1단계 : 인덱스 0과 1을 비교합니다. 인덱스 0이 더 크죠? 따라서 두 개의 값을 바꿔 줍니다. 그럼 2 3 4 1 이렇게 순서가 되겠군요.

1-2 단계 : 이번에는 인덱스 1과 인덱스 2를 또 비교합니다. 인덱스 2가 더 크므로 변동 없습니다.

1-3 단계 : 마지막으로 인덱스 2와 3을 비교합니다. 인덱스 2가 더 크므로 두 개의 값을 바꿔 줍니다. 그럼 결과적으로 2 3 1 4 가 되겠군요

자 이제 1단계가 끝났습니다. 1단계를 그림으로 표현하면 다음과 같습니다. 1단계의 결과는 2 3 1 4 입니다.

2단계

2-1단계 : 다시 1단계처럼 처음부터 비교합니다. 인덱스 0과 1를 비교했을 때 인덱스 1이 더 크므로 변동 없습니다.

2-2단계 : 인덱스 1과 2를 비교합니다. 인덱스 1이 더 크므로 값을 바꿔 줍니다. 그럼 2 1 3 4 가 되겠군요

자 2단계를 마쳤습니다. 2단계를 그림으로 표현하면 다음과 같습니다. 2단계의 최종 결과는 2 1 3 4 입니다.

3단계

3-1단계 : 다시 시작합니다. 2단계의 최종 결과는 2 1 3 4입니다. 인덱스 0과 1를 비교합니다. 이는 인덱스 0의 값이 더 크므로 값을 바꿔 줍니다. 

 그럼 1 2 3 4가 되겠군요.

마지막 3단계를 그림으로 표현하면 다음과 같습니다.

자 이렇게 총 3단계를 거쳐서 버블 정렬이 끝났습니다. 다음의 알고리즘을 C로 코딩해보면 다음과 같습니다.

구현한 함수의 이름은 BubbleSort입니다. 매개변수로는 ary배열과 배열의 크기인 size 변수가 있습니다. tmp변수는 값을 변경할 때 임시로 저장할 버퍼입니다. 

자 시작합시다. !!

일단 for문 두 개가 있습니다. 잘 생각해 봅시다. 처음에 3 2 4 1 이 네 개의 숫자가 있고 인덱스 0번과 1번을 비교하고 그다음 1번과 2번 마지막으로 2 번과 3번을 비교합니다. 총 3번이죠 이게 아까 설명한 1단계입니다.

 1단계를 거치고 나면 맨 우측에 있는 값을 이 값들 중 가장 큰 값이겠죠? 따라서 첫 번째 수행에서 총 3번 비교를 했다면 그다음 수행에서는 맨 마지막 인덱스를 고려안해도 되니 총 2번만 수행하면 됩니다. 이러한 이유를 근거로 첫 번 째 for문은 총 3번을 돌아야 합니다.

여기서 size는 4입니다. 배열은 인덱스가 0부터 시작하기 때문에 I는 0부터 3까지 반복 되야 하므로 for(i=0;i<size-1;i++)이러한 조건이 나온 것입니다. 

자 이제 그 안에 있는 for는 봅시다. 첫 번 째 for문은 아까 설명한 1,2,3 단계를 위한 조건이고 그 안에 있는 for문은 각 단계 안의 세부 조건입니다. 

1-1, 1-2, 1-3, 2-1, 2-2, 3-1 이런 걸 말이죠. 1단계에서 총 3번의 비교 연산을 하였고 그 결과 맨 마지막 인덱스의 값이 제일 큰 값으로 도출 되었습니다. 따라서 그다음 연산에서는 그 인덱스를 고려 안해도 되죠. 따라서 I가 1일 때는 총 2번만 수행하면 됩니다. 인덱스 0,1 인덱스 1,2, 이렇게 말이죠.

그다음 i가 2일 때는 인덱스 0과1 만 비교하면 됩니다. 따라서 한번 for문이 돌 때마다 비교하는 횟수가 감소하기 때문에 j<(n-i)-1 이라는 조건이 나오게 된 것입니다.

정리를 하자면 j<(n-i)-1에서 I가 0일 때는 4-0-1=3 즉 j는 0, 1 2 총 세 번의 비교 연산을 하고 1단계 연산이 끝납니다. 그다음 i가 하나 증가하여 1이 되면 4-1-1=2 즉 j는 0,1 총 두 번 연산을 하고 2단계 연산이 끝납니다. 마지막으로 i가 하나 더 증가하여 2가 되면 4-2-1=1 즉 j는 0가 되어 한번만 연산을 하고 끝나게 됩니다. 이때가 마지막 3단계죠. 

전체적인 코드 설명은 이렇게 마치고 데이터 교환이 일어나는 부분을 설명 드리겠습니다.

ary[j]>ary[j+1]를 만족하면 조건문 안으로 들어오고 왼쪽 의 값이 더 크기 때문에 오른쪽으로 변경시켜야 합니다. 따라서

1. ary[j]값을 버퍼에 잠깐 저장하고

2. ary[j+1]의 값을 ary[j]에 저장 한 뒤

3. 아까 버퍼에 저장한 값을 ary[j+1] 에다가 저장합니다.

 

그럼 최종적으로 ary[j] 와 ary[j+1] 의 값이 변경되게 됩니다.

---

1-2 버블 정렬 : 성능 평가

정렬 알고리즘의 성능은 다음 두가지를 근거로 판단하는 것이 일반적입니다.

 

1.비교의 횟수 : 두 데이터간의 비교연산의 횟수

2.이동의 횟수 : 위치의 변경을 위한 데이터의 이동횟수

 

데이터의 비교연산이 일어나는 경우는

if(ary[j]>ary[J+1]) {.....} 이 부분입니다. 우리는 아까 배열 4개를 총 3단계에 걸쳐서 정렬하였습니다. 그리고 각 단계 별로의 비교 횟수는 3+2+1 입니다. 이렇듯 버블 정렬에서 데이터의 개수가 n개 일 때 진행 되는 비교 횟수는 n-1 + n-2 + n-3 + ..... + 1 입니다. 이는 등차수열 공식을 활용하여 계산하면

 (n^2-n)/2 이고 따라서 버블 정렬의 비교연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 O(n^2)이 됩니다. 단순히 보면 반복문이 중첩되어 있을 뿐인데 이렇듯 실제 활용하기 부담스러운 정도의 성능을 보입니다. 그렇다면 데이터의 이동횟수는 어떨까? 

이는 최악의 경우와 최선의 경우로 나뉩니다. 만약 운 좋게 데이터가 이미 정렬되어 있는 상태라면 데이터의 이동이 한 번도 일어나지 않지만, 반대로 정렬 기준의 역순으로 저장된 상태 4,3,2,1, 이런 식이라면 비교의 횟수와 이동의 횟수가 일치하기 때문입니다. 따라서 데이터 이동 연산에 대한 빅-오는 최악의 경우를 기준으로 하면 O(n^2)과 같습니다.