[정렬] 버블정렬 (Bubble Sort)

* 버블정렬 (Bubble Sort)

- 인접한 두개의 데이터를 비교하면서 정렬

- 최선, 최악의 경우가 따로 존재하지 않음

- 시간복잡도 O(n^2)

※ 오름차순 정렬에 대한 설명.

input = [3, 44, 38, 5, 47, 15]

- 다음과 같이 맨 처음의 숫자와 그다음의 숫자를 비교해 둘 중 더 큰 숫자를 오른쪽으로 이동한다.

- '3'과 '44' 중 44가 더 크므로 자리이동이 발생하지 않는다.

- 다음으로 두번째 숫자인 '44'와 '38'을 비교한 경우 '44'가 더 크므로 오른쪽으로 자리이동이 발생한다.

 

.

.

.

- 위처럼 계속해서 좌, 우 숫자를 계속해서 비교하면서 숫자를 정렬시켜 나간다.

- 이렇게 한번 모든 모든 숫자를 비교하게 되면 아래 그림처럼 제일 큰 숫자가 맨 뒤에 위치하게 된다.

- 이제 마지막 숫자를 제외한 5개의 숫자들에 대해 위의 작업을 반복해서 수행한다. 

- 모든 작업을 수행하고 나면 아래와 같이 오름차순으로 숫자들이 정렬된다.

참고 사이트 : http://visualgo.net/