버블 정렬(Bubble sort)

목차

1. 버블 정렬이란?
2. 사용 예시
3. 장점과 단점

1. 버블 정렬이란

인접한 두 원소를 비교하여 정렬하는 방식입니다.
내림차순으로 정렬해야 하는 경우 다음과 같은 코드로 나타낼 수 있습니다.

int n = v.length();
for (int i = n - 1; i > 0; i--)
	for (int j = 0; j < i; j++)
    		if (v[j] < v[j + 1])
            		swap(v[j], v[j + 1]);

2. 사용예시

위에 주어진 배열을 내림차순으로 정렬하겠습니다.

i = 3일때 아래와 같은 과정을 거칩니다.

이러한 위치 변환이 일어난 뒤에 i위치 즉 v[i]가 고정됩니다.

위 과정을 n - 1번만큼 반복합니다.
i = 2일때의 과정입니다.

i = 1일때의 과정입니다.

최종적으로 내림차순의 배열이 완성되었습니다.

3. 장점과 단점

3-1. 장점

앞서 설명했듯이 마주하고 있는 두 원소의 비교를 반복하기만 하면 됩니다.
구현 난이도가 매우 낮기 때문에 사용되는 곳이 많습니다.

3-2. 단점

버블 정렬의 시간 복잡도는 O(N^2)입니다.
후에 다른 정렬 알고리즘들을 살펴보겠지만 버블 정렬은 다른 알고리즘들에 비해 시간복잡도가 큰 편입니다.

3-3. 결론

시간 복잡도가 큰 대신 구현 난이도가 낮습니다.
시간 복잡도가 N^2이기 때문에 배열의 크기가 작을 때는 무리없이 사용할 수 있습니다.