[알고리즘] - 버블 정렬 (bubble sort)

1. 버블 정렬(bubble sort)이란?

인접한 데이터끼리 비교, swap 연산을 수행하여 정렬하는 방법

버블 정렬이란 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다.

알고리즘은 간단하나, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 

---

2. 버블 정렬의 수행 방식

 

버블 정렬의 수행 과정

① 정렬할 범위의 앞부분부터 인접한 두 원소의 값을 비교한다.

② 앞 원소가 더 크다면 swap한다. /  뒤 원소가 더 크다면 continue

③ 정렬할 범위의 끝부분까지 반복한다.

     => 반복이 끝나면 정렬할 범위는 1 감소, 정렬된 범위는 1 증가한다.

④ 새로운 정렬할 범위를 얻었다. 다시 ①부터 반복한다.

 

---

3. 버블 정렬 구현 (C++)

#include <iostream>
using namespace std;

//버블 정렬 함수 (여기서 n은 배열의 크기)
void bubble_sort(int arr[], int n) {

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

		for (int j = 0; j < i; j++) {

			//인접한 두 원소 중 앞 원소가 더 크다면
			if (arr[j] > arr[j + 1]) {
				//swap 수행
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int list[10] = { 5, 2, 3, 1, 10, 7, 8, 9, 4, 6 };
	
	cout << "정렬 전" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}
	
	bubble_sort(list, 10);

	cout << "\n\n정렬 후" << "\n";
	for (int i = 0; i < 10; i++) {
		cout << list[i] << " ";
	}
}

실행 결과 정상적으로 정렬된 것을 확인할 수 있다.