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

버블 정렬(Bubble Sort)이란?

서로 인접한 두 원소를 검사하여 더 작거나 큰 값을 반복적으로 앞으로 보내는 방법으로

원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다.

버블 정렬(Bubble Sort)의 특징

1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다.

  //주어진 배열만으로 정렬을 할 수 있다.

  //메모리가 제한적인 경우에 이점이 있다.

 

2. 코드가 직관적이며 정렬 알고리즘 중 구현 방법이 가장 간단하다.

 

3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다.

 

4. 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(N^2)이며 모든 정렬 중에 가장 비효율적인 정렬 방법이다.

 

버블 정렬(Bubble Sort) 결과

주어진 배열을 오름차순 혹은 내림차순으로 정렬

 

버블 정렬(Bubble Sort) 구현 방법

1. 주어진 리스트의 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 

   세 번째 원소와, 네 번째 원소를, ~~~ 마지막-1번째 원소와 마지막 원소를 비교하여,

   작은 값을 앞으로, 큰 값을 뒤로 보낸다.

 

2. 버블 정렬의 1회전(1번 과정)이 끝나면 리스트의 가장 큰 값이 맨 뒤로 이동하게 되고,

   2회전은 정렬이 된 마지막 원소를 제외하고 다시 1번 과정을 진행한다.

 

3. 리스트의 원소의 개수가 10이라면, 총 9회전 만에 정렬이 종료되고, 1회전마다 맨 뒤에서부터

   한 자리씩 정렬된다. //10회전은 나머지 남은 한 개의 원소가 저장되어 있으니 할 필요 없다.

 

{3, 4, 2, 5, 1}

 

1.

{3, 4, 2, 5, 1}

첫 번째 원소와 두 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

{3, 2, 4, 5, 1}

두 번째 원소와 세 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

{3, 2, 4, 5, 1}

세 번째 원소와 네 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

{3, 2, 4, 1, 5}

네 번째 원소와 다섯 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

1회전 끝 -> 리스트의 가장 큰 값이 맨 뒤로 온다.

 

2.

{2, 3, 4, 1, 5}

첫 번째 원소와 두 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

{2, 3, 4, 1, 5}

두 번째 원소와 세 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

{2, 3, 1, 4, 5}

세 번째 원소와 네 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

2회전 끝 -> 정렬된 수와 자리를 제외한 리스트의 가장 큰 값이 맨 뒤로 온다.

 

3.

{2, 3, 1, 4, 5}

첫 번째 원소와 두 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

{2, 1, 3, 4, 5}

두 번째 원소와 세 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

3회전 끝 -> 정렬된 수와 자리를 제외한 리스트의 가장 큰 값이 맨 뒤로 온다.

 

4.

{1, 2, 3, 4, 5}

첫 번째 원소와 두 번째 원소를 비교하여 큰 값을 뒤로 보낸다.

4회전 끝 - > 정렬된 수와 자리를 제외한 리스트의 가장 큰 값이 맨 뒤로 온다.

 

5.

{1, 2, 3, 4, 5}

모든 수가 정렬되었다.

 

버블 정렬 vs 선택 정렬

선택 정렬에서는 2중 for문 안에서, 최솟값만 찾고, 찾은 최솟값을 바깥 for문에서 swap해 준다.

버블 정렬에서는 2중 for문 안에서, 인접값들을 비교하고, swap해주기 때문에 컴퓨터에 더 많은 동작을 요구한다.

따라서 선택 정렬과 버블 정렬은 best, avg, worst 모든 상황에서 O(N^2)의 동일한 시간 복잡도를 갖지만,

버블 정렬이 선택 정렬보다 더 비효율적이다.(실행 시간이 오래 걸린다.)

 

코드(c++)

#include <iostream>

using namespace std;

int main() {

	int arr[] = { 3, 4, 2, 5, 1 };
	int arrSize = 5;
	for (int i = 0; i < arrSize-1; i++) {
		//0부터 (마지막 원소-i)값까지 인접 원소들을 비교하여 교환한다 
		for (int j = 0; j < arrSize-1-i; j++) {
			if (arr[j] > arr[j + 1]) { //더 큰 값을 뒤로
				//swap
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
		for (int a = 0; a < arrSize; a++) 
			cout << arr[a] << ' ';
		cout << i+1<<"회전\n";
	}

}