[java] 버블 정렬 알고리즘의 최선/최악/평균 시간 복잡도
버블 정렬은 간단하고 이해하기 쉬운 정렬 알고리즘으로, 이웃한 두 원소의 크기를 비교하여 필요에 따라 교환하는 방식으로 동작합니다. 하지만, 이 알고리즘은 효율성 면에서는 떨어지는 편입니다.
최선, 최악, 평균 시간 복잡도
- 최선 시간 복잡도: O(n)
- 최악 시간 복잡도: O(n^2)
- 평균 시간 복잡도: O(n^2)
버블 정렬은 이웃한 두 원소를 비교하고 필요에 따라 교환하는 과정을 배열의 크기만큼 반복하기 때문에 최선, 최악, 평균 시간 복잡도가 모두 O(n^2)입니다. 이러한 성능으로 인해 대부분의 실전 상황에서는 다른 더 효율적인 정렬 알고리즘을 선택하는 것이 좋습니다.
참고 자료
- Bubble sort algorithm
- Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein