[ALGORITHM] 16. 버블 정렬 구현하기

버블 정렬(Bubble Sort)은 리스트를 반복적으로 훑어가며 인접한 두 원소를 비교 후,

조건에 맞게 원소를 재배치해 정렬하는 알고리즘이다.

이 과정은 리스트가 정렬될 때까지 반복되며 더 작은 원소가 리스트의 위쪽으로 "거품처럼" 올라가는 모습에서

버블정렬이라고 이름을 지었다고 한다.

 

template<typename T>
void bubble_sort(std::vector<T>& data) { // O(n^2)

	int n = data.size();

	for (int i = 0; i < (n - 1); i++) {

		for (int j = (n - 1); j > i; j--) {

			if (data[j] < data[j - 1]) {

				std::swap(data[j],data[j - 1]);
			}
		}
	}
}

 

 

특징

 

1. 간단한 구현 : 버블 정렬은 간단하게 구현할 수 있는 정렬 알고리즘 중 하나이다.

2. 안정적인 정렬 알고리즘 : 동일한 값의 원소 간의 순서가 정렬 전후에 유지된다.

 

 

장점

 

1. 정렬된 리스트에 대한 성능이 좋다 : 이미 정렬된 리스트에 대해서는 추가적인 교환이 발생하지 않아 성능이 좋다.

다만 이미 정렬된 리스트를 처리하는 데 효과적인 다른 정렬 알고리즘도 있다.

 

 

단점

 

1. 효율성이 낮다 : 평균 및 최악의 경우 시간 복잡도가 O(n²)이기 때문에 큰 데이터셋에 대해서는 효율성이 낮다.

2. 원소의 이동이 많다 : 원소를 교환하는 작업이 많이 발생하므로, 다른 알고리즘들에 비해서 비효율적이다.