[알고리즘] 정렬 : 버블정렬

버블 정렬은 오름차순 기준일 때 인접한 두 개의 인접한 원소를 비교하여 더 큰 원소를 뒤로 보내는 방식을 취하고 있다. 두 개의 인접한 원소를 비교해 나가는 모습이 버블 같기 때문에 버블 정렬이라는 이름이 붙었다.

---

개념

• 오름차순 기준으로 설명한다.
• 첫 번째 원소와 두 번째 원소를 비교했을 때 첫 번째 원소가 크다면 두 번째 원소와 자리를 바꾼다. 이어서 두 번째 원소와 세 번째 원소를 비교한다.
• 위와 같은 과정을 거치면 마지막부터 가장 큰 원소들이 정렬될 것이다. 즉, N개의 원소가 있다고 가정했을 때 한 번의 순환을 통해 N번째 자리에 가장 큰 숫자가 저장되고 이제 첫 번째 원소부터 N-1까지의 수들을 비교하여 N-1번째 자리를 채운다.

구현

• 10개의 숫자가 나열되어 있다고 가정한다.
• 2중 for문을 사용해야 할 것이다. 첫 번째 for문은 탐색의 범위를 조절하고 두 번째 for문은 탐색의 범위 내에서 수들을 비교하여 자리를 스왑하도록 한다.

N = 10
numbers = [3, 1, 10, 6, 4, 7, 8, 2, 5, 9]

for i in range(1, N):
    for j in range(N-i):
        if numbers[j] > numbers[j+1]:
            numbers[j], numbers[j+1] = numbers[j+1], numbers[j]

print(*numbers)

 

특징

장점

- 구현이 간단하다.

 

단점

- 이미 정렬되어 있는 위치라도 교환이 일어날 수 있다.

- 만약 첫 번째에 가장 큰 수가 위치해 있다면 다른 모든 원소들과 교환이 일어난다.

 

시간 복잡도

이미 정렬되어 있든 되어있지 않든 2중 for문을 통해 범위를 좁히고 탐색을 진행하기 때문에 최선, 최악, 평균의 경우에 O(N^2)의 시간 복잡도를 갖게된다.