버블 정렬

📢

• 여기서 소개하는 정렬은 오름차순정렬을 기준으로 합니다.
• n개의 원소를 저장하는 배열A를 A[0 ⋯ n - 1]라고 표현하겠습니다.

개념

일반적으로 버블 정렬은 두 개의 포인터를 이용하여 이웃한 요소쌍(pair)을 비교해가면서 순서대로 되어 있지 않은 요소들의 자리를 바꿔나가는 방식으로 진행됩니다. 각 패스(pass)마다 이 과정을 거치며, 최대 n번의 패스를 수행합니다:

버블 정렬의 첫 번째 패스는 요소를 n-1번, 두 번째 패스는 n-2번, 세 번째는 n-3번, … 순회하여 마지막 패스는 1번 순회하게 됩니다. 따라서 버블 정렬의 총 순환 횟수는 (최대) (n-1)+(n-2)+…+1번 이므로 시간 복잡도는 $O(n^2)$이 됩니다.

구현 코드

구현 코드 보러가기