정렬 알고리즘 1부 버블 정렬
Contents
- 시작하며...
- 버블 정렬의 이해와 구현
- 버블 정렬의 성능 분석
- 마치며...
시작하며...
구르미의 "Computer Science 정복하기 - 자료구조"의 열 세 번째 장입니다. 이 장의 대략적인 내용은 다음과 같습니다.
- 버블 정렬의 이해와 구현
- 버블 정렬의 성능 분석
이 장의 소스코드는 다음을 참고해주세요.
url: https://github.com/gurumee92/datastructure
branch: ch13
code directory: src/ch13
자 시작합시다!
버블 정렬의 이해와 구현
이번 장에서는 정렬 알고리즘 중 가장 쉬운 버블 정렬에 대해서 살펴보도록 하겠습니다. 버블 정렬은 정말 쉽습니다. 다음의 배열을 버블 정렬을 통해 오름차순으로 정렬해보겠습니다.
먼저, 배열의 첫번째 위치의 요소 8, 두 번째 위치의 요소 2를 비교합니다.
2 < 8 이고 우리는 오름차순 정렬이기 때문에, 8과 2의 위치를 바꿉니다.
이제 두 번째 위치의 요소 8과 세 번째 위치의 요소 3을 비교합니다.
3 < 8 이기 때문에 둘의 위치를 바꿉니다
이 과정을 배열의 끝까지, 순서대로 비교합니다. 8은 배열 중 가장 큰 요소이기 때문에, 맨 마지막으로 이동합니다.
이 과정을 계속 반복하면 됩니다. 근데 왜 버블 정렬이냐. 이는 두 번째 과정을 살펴보도록 하지요. 밑에 "비교 기준의 숫자"의 변화를 잘 살펴보세요.
이제 또 다시 첫 요소 2, 두번째 요소 3을 비교합니다.
2 < 3 이기 때문에, 위치 변화는 일어나지 않습니다. 대신 비교 기준 수가 2 -> 3으로 변화합니다.
이제 두 번째 요소 3, 세번 째 요소 6과 비교합니다.
3 < 6 이기 때문에 위치 변화는 일어나지 않습니다. 역시 비교 기준 수가 3 -> 6으로 변화합니다.
이제 세번째 요소 6, 네 번째 요소 5와 비교합니다.
5 < 6 이기 때문에 서로 위치를 바꿉니다.
이제 네 번째 요소 6과 다섯 번째 요소 7을 비교합니다.
6 < 7 이기 때문에 위치 변화는 일어나지 않습니다. 이 때 비교 기준 수가 6 -> 7 로 변화합니다.
이제 다섯 번째 요소 7과 여섯 번째 요소 4를 비교합니다.
4 < 7 이기 때문에 서로의 위치를 바꿉니다.
이제 여섯 번째 요소 7과 일곱 번째 요소 1을 비교합니다.
1 < 7 이기 때문에 서로의 위치를 바꿉니다.
이 일련의 과정, 비교 시, 비교 기준 보다 수가 크면 위치는 바꾸지 않고 비교 기준의 수가 변화합니다. 이 과정이 마치 "거품이 일어나는 모습과 유사하다"라는 점에서 버블 정렬이라고 부르게 되었습니다. 다음은 정렬되기까지의 과정을 표현합니다.
이를 토대로 만든 코드는 다음과 같습니다.
src/ch13/main.c
void BubbleSort(int arr[], int n) {
for (int i=0; i<n-1; i++) {
for (int j=0; j< (n-1); j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
버블 정렬의 성능 분석
이제 버블 정렬 알고리즘의 성능 분석을 해보겠습니다. 알고리즘에서 가장 중요한 연산은 비교 연산입니다.
실제, 위 코드에서 일어나는 비교 횟수는 처음에는 7번, 두 번째에는 6번 세 번째에는 5번, 결국에는 8번째에는 0번의 비교 연산이 일어납니다. 다음 그림처럼 말이죠.
총, 7 + 6 + 5 + .. + 1 + 0 번의 연산이 일어나죠. 이를 일반화했을 때, 크기 n에 대해서, 알고리즘에서 연산의 횟수는 다음과 같습니다.
(n-1) + (n-2) + (n-3) + ... + (1)
즉, 다음의 수식으로 표현할 수 있습니다.
n * (n-1) / 2
이를 빅-오 표현식으로 바꾸면 다음과 같습니다.
O(n ^ 2)
즉, 버블 정렬의 성능은 O(n ^ 2) 입니다.
마치며...
이번 시간에는 정렬 알고리즘 중 가장 쉬운 버블 정렬에 대해서 살펴보았습니다. 다음 장에서는 선택 정렬에 대해서 살펴보도록 하겠습니다.