[정렬] 거품 정렬(Bubble Sort)

1. 개념

서로 인접한 두 원소의 대소를 비교하여 조건에 부합하지 않다면 자리를 교환하는 알고리즘

 

2. Process

총 N - 1 번동안 N - i ( 진행한 횟수 )번의 비교를 수행 O(n^2)

1 회전 :

N-1 과 N을 비교 

N-2 과 N-1을 비교

N-3 과 N-2을 비교

....

1과 2를 비교

 

2 회전 :

N-1 과 N을 비교 

N-2 과 N-1을 비교

N-3 과 N-2을 비교

....

2와 3를 비교 // 1번째 수는 가장 작은 수로 이미 정렬 되어짐.

 

위 과정을 N번 반복

 

 

3. GIF로 이해하기

출처 : http://algorithm.wiki/en/app/

4. 시간 복잡도와 공간 복잡도

시간 복잡도는 (n-1) + (n-2) + (n-3) + ... + 2 + 1 => n(n-1)/2

이므로 O(n^2)

공간 복잡도는 주어진 배열안에서 스왑이 진행 되기 때문에 O(n)