버블정렬(Bubble sort)

Goal

- Bubble Sort 에 대해 설명할 수 있다.

- Bubble Sort 과정에 대해 설명할 수 있다.

- Bubble Sort를 구현할 수 있다.

- Bubble Sort의 시간 복잡도를 계산 할 수 있다.

1. Bubble Sort Summary

'옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내기'

'알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘'

2. Bubble Sort Processing

1. 첫번째 원소와 두번째 원소를 , 두번째 원소와 세번째 원소를.... 마지막-1 번째 원소와 마지막 원소 비교

2. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 1회전 수행할 때마다 정렬에서 제외되는 데이터가 늘어난다.

3. Bubble Sort Coding

4. Bubble Sort 시간 복잡도

데이터의 개수가 n개라고 했을때

- 첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1

- 두 번째 회전에서의 비교횟수 : 2 ~ (n-2) => n-2

....

- (n-1) + (n-2) ..... + 2 + 1 => N * (N-1) /2 (등차수열)

=> 컴퓨터에서는 가장 큰 차수인 n^2만 보고 0(N^2) 라고 표현

시간 복잡도는 선택정렬과 동일하지만,

내부적인 연산이 가장 비효율적으로 일어나게 되어 실제 수행시간이 가장 느린 안좋은 알고리즘

1Sang