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

0. 목차

 

1. 버블정렬의 개념
2. 버블정렬의 과정 정리
3. 버블정렬의 시간복잡도
4. 버블정렬 코드

---

1.버블정렬의 개념

 

버블정렬은 거품이 위로 올라가는것과 유사하다는 의미에서 버블정렬이라는 이름이 붙여졌다.

버블정렬은 인접한 두 데이터를 비교해가며, 조건을 만족하면 SWAP을 하며 정렬하는 방식이다.

 

말로는 어려울테니 아래의 그림을 보며 이해해보자.

5 1 4 7 2 의 데이터를 버블정렬을 이용하여 오름차순으로 정렬하는 과정을 보여준다.

 

 

 

1. 5와 1을 비교했을 때, 5>1 이므로 교환

2. 5와 4를 비교했을 때, 5>4 이므로 교환

3. 5와 7을 비교했을 때, 5<7 이므로 교환 X

4. 7과 2를 비교했을 때, 7>2 이므로 교환

=>이렇게 1페이즈에서 정렬되지않은 데이터중 가장 큰 수인 7이 맨 위(맨 뒤) 로 떠올랐다.

 

 

 

그럼 다음으로 정렬되지않은 데이터중에서 가장큰 수를 거품처럼 올려보자

1. 1과 4를 비교했을 때, 1<4 이므로 교환 X

2. 4와 5를 비교했을 때, 4<5 이므로 교환 X

3. 5와 2를 비교했을 때, 5>2 이므로 교환

=>2페이즈에선 정렬되지 않은 데이터중 가장 큰 수인 5가 떠올랐다.

 

 

 

다음 페이즈도 마찬가지로 해준다.

1. 1과 4를 비교했을 때, 1<4 이므로 교환 X

2. 4와 2를 비교했을 때, 4>2 이므로 교환

=>정렬되지 않은 데이터중 가장 큰 수 인 4가 맨 위로 떠올랐다.

 

마지막 페이즈를 실행시켜준다.

1. 1과 2를 비교했을 때, 1<2 이므로 교환 X

=> 정렬되지않은 데이터중 가장 큰 수인 2가 떠올랐다.

 

마지막은 할 필요가 없이 데이터가 1개가 남았으므로, 비교대상이 없다. 이 의미는 뒤에가 정렬이 완료되었으니, 남은 데이터 하나는 당연히 정렬이 된 상태가 된다.

---

2.버블정렬 과정 정리

 

1. 정렬되지않은 데이터중, 맨 앞의 위치를 선정한다.
2. 정렬되지않은 데이터와 그 뒤의 데이터(정렬되지 않은 데이터)를 비교하여, 조건에 부합하다면 SWAP을 해준다.
3. 2번을 수행하며 정렬되지않은 데이터의 맨 끝까지 왔으면, 비교할것이 없으므로 1번으로 되돌아간다.

---

3.버블정렬 시간복잡도

 

 N개의 데이터를 정렬한다고 한다면,

버블을 올려주는 행동의 시간복잡도는 정렬되지않은 데이터들을 모두 탐색해야하므로 O(N)이 된다.

이 버블을 올려주는 행동을 N-1번 해야하므로

버블정렬의 시간복잡도는 총 O(N²)이 된다.

---

4.버블정렬 코드

 

#include<iostream>
using namespace std;

int main() {
	int arr[5] = { 5,1,4,7,2 };
	int size = 5;
	int temp;

	cout << "정렬 전 :\t";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";

	for (int i = 0; i < size - 1; i++) {
		for (int j = 0; j < size - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}

		//중간결과
		cout << i + 1 << "번째 결과 :\t";
		for (int j = 0; j < 5; j++) {
			cout << arr[j] << " ";
		}
		cout << "\n";
	}

	cout << "정렬 결과:\t";
	for (int i = 0; i < 5; i++) {
		cout << arr[i] << " ";
	}
	cout << "\n";
	return 0;
}