버블 정렬(Bubble Sort) 쉽게 이해하기

정렬되지 않은 데이터를 검색하는 것보다 정렬된 데이터를 검색하는 것이 더 효율적이다. 그래서 데이터를 정렬하는 여러 알고리즘이 있는데, 그중 하나가 바로 버블 정렬(Bubble Sort)이다.

버블 정렬이란?

버블 정렬은 서로 인접한 두 개의 값을 비교하면서 위치를 바꿔가며 정렬하는 방식이다. 마치 물속의 거품이 위로 올라가는 것처럼 큰 값이 점점 뒤로 밀려나는 모습과 비슷해서 '버블 정렬'이라는 이름이 붙었다.

 

버블 정렬이 작동하는 방식

예를 들어, 정렬되지 않은 숫자 목록이 있다고 가정해보자.

6 3 8 5 2 7 4 1

 

첫 번째 패스 (1회전)

• 6과 3을 비교 → 6이 더 크므로 교환 → 3 6 8 5 2 7 4 1
• 6과 8을 비교 → 교환 없음 → 3 6 8 5 2 7 4 1
• 8과 5를 비교 → 8이 더 크므로 교환 → 3 6 5 8 2 7 4 1
• 이런 방식으로 마지막까지 진행하면 가장 큰 수 8이 맨 뒤로 이동한다.

 

3 6 5 2 7 4 1 8

 

두 번째 패스 (2회전)

• 같은 방식으로 다시 처음부터 비교를 반복하면 두 번째로 큰 숫자가 뒤로 이동한다.

 

3 5 6 2 7 4 1 8

 

이 과정을 반복하면 점점 정렬된 상태가 된다.

 

1 2 3 4 5 6 7 8

 

최종적으로 리스트가 완전히 정렬된다.

 

 

버블 정렬의 시간 복잡도

버블 정렬은 모든 요소를 비교하고 교환하는 과정이 필요하기 때문에 시간 복잡도는 O(n²)이다. 즉, 데이터 개수가 많아질수록 정렬 속도가 급격히 느려진다.

 

버블 정렬이 얼마나 느린가?

버블 정렬은 두 개의 숫자를 비교하고 교환하는 방식이므로, 전체 리스트를 정렬하려면 여러 번 반복해야 한다. 리스트의 크기가 n이라면:

• 첫 번째 패스에서 n-1번 비교
• 두 번째 패스에서 n-2번 비교
• ...
• 마지막 패스에서 1번 비교

 

이 과정을 수식으로 나타내면:

(n-1) + (n-2) + (n-3) + ... + 2 + 1 = n(n-1)/2

즉, 최악의 경우 약 n²/2번의 비교가 필요하다. 여기서 가장 크기가 큰 항인 n²을 기준으로 시간 복잡도는 O(n²)이라고 표현한다.

또한, 정렬이 되어 있는지 여부에 관계없이 모든 요소를 비교해야 하므로 최선의 경우에도 Ω(n²)의 시간이 걸린다.

 

버블 정렬이 효율적인 경우 vs 비효율적인 경우

✅ 효율적인 경우

• 정렬할 데이터 개수가 적을 때 (예: 10개 이하)
• 데이터가 이미 거의 정렬된 상태일 때
  → 이 경우에는 불필요한 교환이 거의 없어서 비교적 빠르게 동작한다.

❌ 비효율적인 경우

• 정렬해야 할 데이터 개수가 많을 때 (예: 수천 개 이상)
• 데이터가 완전히 무작위이거나 역순으로 정렬되어 있을 때
• 빠른 정렬이 필요한 경우
  → 데이터가 많으면 비교 횟수가 급격히 증가하여 실행 속도가 느려진다.

 

버블 정렬 의사 코드 (Pseudo Code)

아래와 같이 의사 코드로 나타낼 수 있다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

 

의사 코드 설명

• Repeat n-1 times: 리스트 전체를 정렬하려면 총 n-1번 반복해야 한다.
• For i from 0 to n-2: 각 반복에서 인접한 두 요소를 비교하며 정렬하므로, 마지막 요소는 비교할 필요가 없다.
• If i'th and i+1'th elements out of order: i번째와 i+1번째 요소가 정렬 순서에 맞지 않으면
• Swap them: 두 요소의 위치를 바꾼다.

여기서 i'th와 i+1'th의 'th는 영어에서 순서를 나타내는 접미사이다. 예를 들어:

• 1번째 → 1st
• 2번째 → 2nd
• 3번째 → 3rd
• 4번째 이상 → 4th, 5th, ...

따라서, i'th는 i번째 요소, i+1'th는 i+1번째 요소를 의미한다.

 

---

 

버블 정렬은 이해하기 쉬운 정렬 알고리즘이지만, 속도가 느려서 실전에서는 잘 사용되지 않는다. 다만, 알고리즘의 기초 개념을 배우기에 적합하며, 작은 데이터셋에서는 사용할 수 있다.

"버블 정렬을 배우면서 정렬의 기본 원리를 익히고, 더 효율적인 정렬 알고리즘도 공부해봐야겠다🥰"