• 버블 정렬, 거품(bubble)정렬은 정렬 알고리즘 중 하나임.
  • 원소의 이동시 거품이 수면으로 올라오는 듯한 모습을 보여지기 때문에 지어진 이름임.
• 시간 복잡도가 O(n^2)로 상당히 느리지만, 코드가 단순하여 자주 사용됨.
• 배열 자료구조를 사용함.

알고리즘

• 배열의 두 수(a, b)를 선택한 뒤, 두 수가 정렬되지 않았다면 두 수를 바꾸는 방식으로 진행됨.
  • 정렬되어있다면 연산X
• 오름차순으로 정렬할 땐 a < b, 내림차순 이라면 a > b을 만족해야 정렬된 것으로 판단.
• 이를 배열의 처음부터 끝까지 반복함.

예시

정렬되지 않은 배열로 가정하고, 오름차순으로 정렬 프로세스로 가정. → [8, 5, 3, 1, 4, 7, 9]

1. 배열의 첫 두 원소(8, 5)를 비교함. 8 > 5 → [5, 8, 3, 1, 4, 7, 9]
2. (8, 3) 을 비교함. 8 > 3 → [5, 3, 8, 1, 4, 7, 9]
3. (8, 1)을 비교함. 8 > 1 → [5, 3, 1, 8, 4, 7, 9]
4. 위 작업을 배열의 처음부터 끝까지 수행한다면 다음이 됨. → [5, 3, 1, 4, 7, 8, 9]
   1. 이 작업을 배열에 아무 변화가 없을 때 까지 반복.

결과를 정리해 보자면

• cycle1 : [5, 3, 1, 4, 7, 8, 9]
• cycle2 : [3, 1, 4, 5, 7, 8, 9]
• cycle3 : [1, 3, 4, 5, 7, 8, 9]
• cycle4 : [1, 3, 4, 5, 7, 8, 9]

cycle4부터 아무 변화가 없으니 모두 정렬된 것으로 정의함.