거품 정렬(Bubble Sort)

거품 정렬이란?

거품 정렬은 간단하면서 기본적인 정렬 알고리즘 중 하나입니다.

이 알고리즘은 인접한 두 원소를 비교하여 순서가 잘못된 경우에 서로 교환하는 방식으로 정렬을 진행합니다.

이러한 교환 작업을 계속해서 반복하면서 가장 큰 원소가 배열의 마지막 위치로 이동하게 됩니다. 이 과정을 배열의 모든 원소가 정렬될 때까지 반복합니다.

 

거품 정렬은 하나의 원소를 정렬하는 과정에서 많은 교환(swap)과정이 일어날 수 있어서 하나의 원소에 대해 한 번의 교환 과정을 갖는 선택 정렬에 비해 평균적으로 더 많은 시간이 소요됩니다.

 

거품 정렬의 특징

1. stable 정렬: 동일한 값의 원소들 간에는 순서가 유지되므로 안정 정렬입니다.

2. in-place 정렬: 자료 구조를 그대로 두고 그 안에서 요소들의 위치를 바꾸어 정렬합니다.

3. 시간복잡도: 평균, 최악의 경우는 O(N^2)의 시간 복잡도를 갖습니다.

하지만, 이미 정렬된 배열이 주어지는 최선의 경우에는 O(N)의 시간 복잡도를 갖습니다. 이 경우는 한 번의 패스 동안 교환이

한 번도 이루어지지 않았을 경우에 더 이상의 패스를 수행하지 않고 정렬을 종료시키는 최적화를 통해 구현할 수 있습니다.

 

거품 정렬의 구현(Java)