[정렬 알고리즘] 버블정렬 (Bubble Sort)

버블정렬 (Bubble Sort)

: 인접한 두 원소를 비교하여 순서가 잘못된 경우 교환하는 방식 

 

 

동작 방식

1. 배열의 첫 번째 원소부터 인접한 다음 원소 비교
2. 원소의 순서가 잘못되었으면 교환
3. 1, 2 과정을 배열 끝까지 반복 
   → 마지막 원소는 가장 큰 값이므로 정렬 확정된 수가 됨
4. 반복할(Loop) 때마다 마지막 원소는 정렬되므로 다음 반복은 마지막 원소를 제외한 범위만 비교
5. 위 과정을 반복

 

시간 복잡도 

• 최악의 경우 : 모든 값을 비교하고 교환해야 하기 때문에 시간이 입력 데이터 크기의 제곱만큼 늘어남 →  O(n^2)
• 최선의 경우 : 배열이 이미 정렬되어 있는 경우 한 번 순회만으로 정렬이 끝 → O(n)

 

 

 

예제 

C언어

#define _CRT_SECURE_NO_WARNINGS
#define SIZE 5
#include <stdio.h>
#include <stdlib.h>

int main(void) {

	// 버블 정렬
	int iArr[SIZE] = { 3, 4, 2, 5, 1 };

	for (int i = 0; i < SIZE - 1; ++i) {
		// 정렬 범위는 끝값을 `end` 변수로 설정
		int end = (SIZE - i) - 1;
		for (int j = 0; j < end; ++j) {
			// 현재 인덱스의 숫자와 다음 인덱스의 숫자를 비교
			if (iArr[j] > iArr[j + 1]) {
				int tmp = iArr[j];
				iArr[j] = iArr[j + 1];
				iArr[j + 1] = tmp;
			}
		}
	}

	printf("\n정렬 후 ");
	for (int i = 0; i < SIZE; ++i) {
		printf("%d\t", iArr[i]);
	}

	return 0;
}

 

정렬 시 아래와 같이 순회하며 정렬

i	j	end	iArr[j] ↔ iArr[j+1]	배열 상태
0	0	4	3 ↔ 4	{3, 4, 2, 5, 1}
0	1	4	4 ↔ 2 (swap)	{3, 2, 4, 5, 1}
0	2	4	4 ↔ 5	{3, 2, 4, 5, 1}
0	3	4	5 ↔ 1 (swap)	{3, 2, 4, 1, 5}
1	0	3	3 ↔ 2 (swap)	{2, 3, 4, 1, 5}
1	1	3	3 ↔ 4	{2, 3, 4, 1, 5}
1	2	3	4 ↔ 1 (swap)	{2, 3, 1, 4, 5}
2	0	2	2 ↔ 3	{2, 3, 1, 4, 5}
2	1	2	3 ↔ 1 (swap)	{2, 1, 3, 4, 5}
3	0	1	2 ↔ 1 (swap)	{1, 2, 3, 4, 5}