[정렬] 버블 정렬 (Bubble Sort)

소개

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.
• 다른 정렬 알고리즘에 비해 느린 편이지만, 코드가 간단하다.

---

정렬 과정

---

첫 번째 탐색

1. 5와 3을 비교 

2. 앞에 있는 5가 더 크므로 5와 3의 위치를 바꾼다.

3. 5와 1을 비교

4. 앞에 있는 5가 더 크므로 5와 1의 위치를 바꾼다.

5. 5와 9를 비교

6. 뒤에 있는 9가 더 크므로 위치를 변경하지 않는다.

7. 9와 7을 비교

8. 앞에 있는 9가 더 크므로 9와 7의 위치를 바꾼다.

9. 첫 번째 순회가 끝난 배열

---

첫 번째 탐색의 과정을 보면 가장 큰 수가 맨 뒤로 이동하게 된다. 

즉, 매 순회마다 정렬된 수를 제외한 가장 큰 수가 맨 뒤로 가 뒤에서부터 정렬이 된다.

그러므로 맨 순회마다 배열의 전체를 탐색할 필요 없이 정렬된 부분을 제외한 부분만 탐색하면 된다.

 

 

두 번째 탐색 결과

세 번째 탐색 결과

네 번째 탐색 결과

다섯 번째 탐색 결과

---

코드 구현

#include <stdio.h>

void PrintArray(int* arr, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void BubbleSort(int* arr, int size)
{

	int tmp;
	for (int i = 0; i < size ; i++)
	{
		for (int j = 0; j < size - (1 + i); j++)
		{
			if (arr[j] > arr[j + 1])
			{
				tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
			}
		}
		printf("%d번째 순회: ", i + 1);
		PrintArray(arr, size);
	}
}
int main(void)
{
	int arr[5] = { 5 , 3, 1, 9, 7 };

	printf("정렬 전: ");
	PrintArray(arr, 5);

	BubbleSort(arr, 5);

	printf("정렬 후: ");
	PrintArray(arr, 5);

	return 0;

}

정렬 전: 5 3 1 9 7
1번째 순회: 3 1 5 7 9
2번째 순회: 1 3 5 7 9
3번째 순회: 1 3 5 7 9
4번째 순회: 1 3 5 7 9
5번째 순회: 1 3 5 7 9
정렬 후: 1 3 5 7 9

정리

• 시간 복잡도: (n - 1) + (n - 2) + ...... + 1 = n(n-1)/2 = O(n^2)
• 코드가 간결하며 이해하기 쉽지만, 시간 복잡도가 O(n^2)인 만큼 데이터의 양이 많을수록 성능이 저하된다.
• 뒤에서부터 정렬이 된다는 특징이 있다.