버블 정렬 Bubble Sort

Intro

• 버블 정렬의 이해

버블 정렬 Bubble Sort

버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다.

시간복잡도가 O(n²)로 느리지만, 단순하다. ¹

예제

버블 정렬의 시간 복잡도

비교 횟수

• 최상, 평균, 최악 모두 일정

• n-1, n-2, … ,2, 1 번 = n(n-1)/2

교환 횟수

• 역순으로 정렬되어 있는 최악의 경우, 한번 교환시 3번의 이동 필요 = 3n(n-1)/2

• 최상의 경우 이미 정렬되어 있으므로 교환 하지않음

T(n)=O(n²)

자바 구현

실행 결과

참고자료

Heee’s 블로그

1. 위키백과 ↩