Bubble Sort

 거품정렬이란?

앞,뒤 인접한 숫자들을 비교하여 작은값을 앞으로, 큰 값을 뒤로 바꿔주는 정렬 방식이다(오름차순일 경우).

 

1. 시간복잡도

 1부터 N까지 N번 -> 2부터 N까지 N-1번 -> 3부터 N까지 N-2번 -> ........... -> N-1에서 N까지 1번

 즉, N*(N+1)/2 이므로 O(N^2)

 

2. stable

 앞에서부터 비교하여 쭉 올라가기 때문에 같은 숫자의 순서를 유지한다.

 

3. 코드