[알고리즘] 버블정렬 (Bubble Sort)

* 버블정렬 (Bubble Sort) 알고리즘 개념

 - 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.

 - 2개를 비교해서 숫자 크기가 순서에 맞게 정렬이 되지 않을경우 서로 교환을 합니다.

 - 조금 더 구체적으로 이야기해서 첫번째 데이터는 두번째 데이터, 두번째 데이터는 세번째 데이터 이런 반복적인

  방법으로 해서 마지막 데이터까지 비교를 하면 됩니다.

 - 첫번째 원소를 시작으로 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리로 이동하는 모습이 물방울 모

  양 같다하여 버블정렬이라고 합니다.

 

 

 

* 버블정렬 알고리즘의 장단점

 1) 장점

 - 구현이 매우 간단합니다.

 2) 단점

 - 순서에 맞지 않은 요소를 인접한 요소와 교환합니다.

 - 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환해야 합니다.

 

 

 

* 버블정렬 알고리즘의 샘플예제

 

 

 

* 버블정렬 파이썬코드

* 실행결과

 

 

 

* 버블정렬의 시간복잡도

 1) 비교 횟수

  - 최상, 평균, 최악 모두 일정합니다.

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

 2) 빅오 표기법 

 

 

 

참조 1 : https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

참조 2 : https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

참조 3 : https://tctt.tistory.com/47