정렬 알고리즘(Sorting Algorithm)의 모든 것 ① - 버블정렬

정렬 알고리즘은 알고리즘 중에서도 가장 기초적인 개념이다. 

정렬 알고리즘에는 다양한 것이 있는데 대표적으론 버블, 선택, 퀵, 힙, 병합정렬이 있다.

1. 정렬 알고리즘(Sorting Algorithm)의 모든 것 ① - 버블정렬

 : 버블정렬은 정렬 알고리즘 중에 가장 이해하기 쉬운 개념이지만 시간복잡도가 O(n^2)이기도 하고 실전에서 좋은 성능을 내지 못하기 때문에 잘 사용되지 않는다.

그러나 학부생이라면 과제할 때 정렬이 필요하다면 외워놓고 바로바로 쓸 수 있는 쉬운 정렬이기 때문에 한 번쯤은 봐주면 좋을 것이다.

<< 버블정렬 C++ 문법 기준 코드 >>

for문은 총 2번 돌기 때문에 시간 복잡도는 O(n^2)으로 굉장히 비효율적인 알고리즘이다.

<< 버블 정렬의 알고리즘 특징 >>

** 장점 

- 구현하기 쉽다

- 이해하기 쉽다

** 단점

- 특정 요소가 최종 정렬 위치에 있다고 하더라도 값 교환이 일어날 수 있어 굉장히 비효율적이다.

- 위의 예시 처럼, 맨 왼쪽에서 맨 오른쪽 혹은 맨 오른쪽에서 맨 왼쪽으로 이동하게 될 시 배열의 거의 모든 인덱스에 들어있는 값들과 교환이 일어나게 된다.

<< 버블 정렬 시간 복잡도 계산 >>

(이 버블정렬 같은 경우 학부 시험때 달달 외웠었기 때문에 아직도 기억난다.)

* 버블 정렬 같은 경우 최상, 평균, 최악 모두 동일하다

* n-1, n-2, n-3, ...., 3, 2, 1번 = n(n-1)/2

* T(n) = O(n^2)