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

*오름차순을 기준으로 정렬한다.

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

버블 정렬(bubble sort) 알고리즘의 개념 요약

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.

버블 정렬(bubble sort) 알고리즘의 수행 과정

• 버블 정렬은 첫번째 자료와 두번째 자료를, 두번째 자료와 세번째 자료를, 세번째와 네번째,.. 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하면서 자료를 정렬한다.
• 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두번째 자료까지 정렬에서 제외된다.
• 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

버블 정렬(bubble sort) 알고리즘 예제

• 배열에 7,4,5,1,3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해보자.
  

버블 정렬(bubble sort) 알고리즘의 C++ 코드

#include <iostream>
using namespace std;

void bubble_sort(int list[], int size) {
	int temp;

	//맨 마지막 요소를 제외하고 반복, (size-1)번
	for (int i = size - 1; i > 0; i--) {
		// 0~(i-1)까지 반복
		for (int j = 0; j < i; j++) {
			//j번쨰와 j+1번쨰의 요소가 크기순이 아니면 교환
			if (list[j] > list[j + 1]) {
				temp = list[j + 1];
				list[j + 1] = list[j];
				list[j] = temp;
			}

		}
	}
}

void main() {
	int list[5] = { 7,4,5,1,3 };

	bubble_sort(list, 5);

	for (int i = 0; i < 5; i++) {
		cout << list[i] << endl;
	}
}

버블 정렬(bubble sort) 알고리즘의 특징

• 장점
  - 구현이 매우 간단하다.
• 단점
  - 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  • 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
• 일반적으로 자료의 교환작업이 자료의 이동작업보다 더 복잡하기 때문에 버블정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

버블 정렬(bubble sort) 알고리즘의 시간 복잡도

• 비교 횟수
  - 최상, 평균, 최악 모두 일정
  - n-1, n-2, … , 2, 1 번 = n(n-1)/2
• 교환 횟수
  - 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
  - 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
• T(n) = O(n^2)