제로베이스 데이터사이언스 스쿨 - Part 05. 자료구조&알고리즘 with Python -25

Chapter 03. 알고리즘

버블 정렬(Bubble Sort) 정리

개념 정리

버블 정렬(Bubble Sort)은 인접한 두 원소를 비교하면서 정렬하는 가장 기본적인 정렬 알고리즘이다. 리스트의 앞에서부터 시작해 옆에 있는 값과 비교하고, 순서가 잘못되어 있으면 서로 자리를 바꾼다. 이 과정을 한 바퀴 돌면 가장 큰 값이 자연스럽게 맨 뒤로 이동하게 되는데, 이 모습이 마치 거품이 위로 올라가는 것과 같다고 해서 버블 정렬이라는 이름이 붙었다.

강의 자료에서는 새 학년이 되어 모인 20명의 학생을 키 순서로 정렬하는 예제를 통해 버블 정렬의 동작 원리를 설명한다. 학생들의 키는 random 모듈을 이용해 170~185 사이의 값으로 생성하고, 이를 버블 정렬 알고리즘으로 오름차순 정렬한다.

---

동작 원리

버블 정렬의 핵심 흐름은 다음과 같다.

1. 리스트의 처음부터 끝까지 인접한 두 값을 비교한다.
2. 앞의 값이 뒤의 값보다 크면 두 값을 교환(swap)한다.
3. 한 번의 반복이 끝나면 가장 큰 값이 리스트의 맨 뒤에 위치한다.
4. 정렬이 완료될 때까지 비교 범위를 하나씩 줄이며 반복한다.

이 방식은 구현이 직관적이고 이해하기 쉬운 대신, 데이터의 개수가 많아질수록 비교 횟수가 급격히 증가한다.

---

파이썬 구현 예시

import copy

def bubbleSort(ns, deepCopy=True):
    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns

    length = len(cns) - 1
    for i in range(length):
        for j in range(length - i):
            if cns[j] > cns[j + 1]:
                cns[j], cns[j + 1] = cns[j + 1], cns[j]
    return cns

• deepCopy=True 옵션을 사용하면 원본 리스트를 유지한 채 정렬 결과만 새 리스트로 반환한다.
• 바깥 반복문(i)는 전체 정렬 회차를 의미하고, 안쪽 반복문(j)은 실제 비교와 교환이 일어나는 부분이다.
• 이미 뒤쪽에 정렬된 값들은 다시 비교하지 않도록 length - i로 범위를 줄인다.

---

시간 복잡도

• 최선, 평균, 최악의 경우 모두 O(n²)
• 데이터가 이미 정렬되어 있어도 비교 연산은 그대로 수행되므로 효율적인 알고리즘은 아니다.

이 때문에 실무나 대규모 데이터 처리에서는 거의 사용되지 않으며, 정렬 알고리즘을 처음 학습할 때 구조를 이해하기 위한 용도로 주로 활용된다.

 

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

버블 정렬을 직접 구현해보면서 정렬 알고리즘의 핵심은 결국 "비교"와 "교환"이라는 점을 명확하게 체감할 수 있었다. 특히 실습 문제를 통해 반복문이 중첩되면서 비교 범위가 점점 줄어드는 구조를 눈으로 확인하니, 단순히 코드로만 볼 때보다 동작 과정이 훨씬 선명하게 이해되었다. 또한 deep copy 여부에 따라 원본 데이터가 유지되는지 달라진다는 점은, 알고리즘뿐 아니라 데이터 처리 전반에서 중요한 개념이라는 생각이 들었다.

---

🚀 적용점

• 정렬 알고리즘의 기본 구조를 이해하는 입문용 예제로 활용하기 좋다.
• 다른 정렬 알고리즘(선택 정렬, 삽입 정렬, 퀵 정렬 등)을 학습할 때 비교 기준점으로 삼기 좋다.
• 리스트 복사, 반복문 제어, swap 로직 등 파이썬 기본 문법 연습에 적합하다.
• 실무에서는 성능 문제로 사용을 지양하고, 내장 정렬 함수나 효율적인 알고리즘을 선택해야 한다.