버블 정렬(Bubble Sort) 이란?

버블 정렬은 인접한 두 요소를 비교하여 정렬 순서에 맞지 않으면 서로 자리를 바꾸는 과정을 반복한다.

이 과정을 배열의 끝까지 반복하면 가장 큰 요소(오름차순 기준)가 맨 뒤로 이동하게 된다.

그 다음에는 이 과정을 정렬된 부분을 제외한 나머지 배열에 대해 반복하여, 점차적으로 전체 배열을 정렬한다.

<aside> 💡

Tip. 마치 물 속의 거품(Bubble)이 위로 떠오르듯이, 가장 큰(또는 가장 작은) 요소가 배열의 끝으로

   이동하며 정렬되는 방식이라 “버블 정렬”이라는 이름이 붙었다.

</aside>

작동 방식

  1. 첫 번째 순회

: 배열의 첫 번째 요소부터 인접한 두 요소를 비교한다.

만약 왼쪽 요소가 오른쪽 요소보다 크다면(오름차순 정렬 기준), 두 요소의 위치를 바꾼다.

이 과정을 배열의 끝까지 반복하면, 가장 큰 요소가 배열의 마지막 위치로 이동하게 된다.

  1. 두 번째 순회

: 이제 가장 큰 요소는 이미 정렬되었으므로, 그 다음으로 큰 요소를 찾기 위해

마지막 요소를 제외한 나머지 배열에 대해 1번 과정을 다시 반복한다.

그러면 두 번째로 큰 요소가 마지막에서 두 번째 위치로 이동한다.