C++ 간단한 버블 소트 (Bubble Sort) 배우기

버블 소트(Bubble sort)는 비록 O(n^2)급의 시간복잡도를 가지고 있지만

정말 간단한 코드를 가지고 있어 heavy-load(무거운 작업)이 아닌 이상 간단히 쓰일 수 있다.

정렬 방식이 마치 거품이 떠오르는 것과 유사하다 하여 붙여진 이름 "bubble sort".

 

Bubble Sort

위 예제에서는 샘플의 크기가 n=8인 자료를 정렬한다.

i가 룹을 한 번 돌 때마다 j는 0부터 n-i까지 룹을 도는데, n-i까지 지정해 준 이유는, 오름차순의 경우, 밖의 룹이 한 번 돌 때마다 n-i까지는 정렬이 완료되어서 더 이상 불필요하기 때문이다.

 

정렬 방식은 j의 interation이 돌면서 바로 다음 index값과 비교/swap하는 방식이다.

 

여기서 change는 정렬이 완료되었을 때 더 이상 작업반복을 하지 않기 위해 있는 flag이다.

 

 

또, swap은 algorithm 헤더를 쓰거나 직접 작성할 수도 있다.

 

    예시)  swap(int x, int y){ int t=x; x=y; y=t; }