[알고리즘 개념] 버블 정렬 (bubble sort) c++

버블 정렬

 

버블정렬 (bubble sort)란 두 인접한 원소를 검사하여 정렬하는 방법이다.
시간복잡도가 O(n^2)로 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다.

(출처 위키백과)

 

 

GIF 으로 개념이해

 

버블정렬 GIF

 

오름차순정렬을 하게되면
첫번째 원소와 두번째 원소를 비교하여 첫번째 원소가 두번째 원소보다 크면 두 원소를 교환하고
두번째 원소와 세번째 원소를 비교하고, 세번째 원소와 네번째 원소를 비교하고 이런식으로
(마지막-1) 번째 원소와 마지막 원소를 비교하여 정렬한다.

 

이런식으로  1번 처음부터 끝까지 수행하게 되면(1회전 후) 배열의 가장 큰 원소가 맨 뒤로 이동하므로 
2회전을 수행할때는 맨 끝에 있는 원소는 정렬에서 제외된다.

 

1회전을 할때 교환이 이루어지지 않으면 정렬이 된 상태라고 볼 수 있는거다.

 

 

c++로 구현

 

#include<iostream>
using namespace std;
int a[10] = { 3,6,7,1,4,2,9,0,5,8 };

void bubble_sort(int a[])
{
	int tmp;
	for (int i = 0; i < 10; i++) {  // 1
		for (int j = 0; j < 9 - i; j++) {  // 2
			if (a[j] > a[j + 1]) {
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
		}
	}
}


int main()
{
	bubble_sort(a);

	for (int i = 0; i < 10; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

 

출력: 0 1 2 3 4 5 6 7 8 9

 

1.  제외될 원소의 개수!!  1회전이 끝난 후, 배열의 마지막 위치에는 가장 큰 원소가 위치하기 때문에 마지막 원소는 검토해줄 필요가 없으므로 검토할 필요가 없는 원소의 개수를 하나씩 증가시켜준다.
2.  비교해줄 원소의 index!!  i = 0,  j가 0일땐 0,1 번째 원소를 비교해주고, 1,2 번째 원소를 비교하고 ... 8,9 번째 index 에 있는 원소를 비교해주고 i = 1 일때는 i, 즉 1을 빼줘서 검토할 필요가 없는 원소는 검토를 안한다.