[알고리즘] Bubble Sort(버블 정렬)

Bubble Sort

bubble sort란 배열 정렬 시 바로 옆의 수와 비교하여 자신이 옆의 수 보다 클 경우 위치를 바꾸는 정렬입니다. 선택 정렬과 마찬가지로 비효율적인 정렬 방식인데요. 실제 어떻게 작동하는지 한 사이클만 그림으로 확인해보면 다음과 같습니다.

 

 

3

2

5

7

1

 

2

3

5

7

1

 

2

3

5

7

1

 

2

3

5

7

1

 

2

3

5

1

7

 

1. 우선 첫 번째 인덱스부터 시작합니다. 첫 번째 인덱스에 있는 숫자 3이 2보다 크므로 서로 위치를 바꿉니다.

2. 그리고 두 번째 인덱스와 세 번째 인덱스를 비교합니다. 두 번째 인덱스에는 1번에서 위치가 바뀌었으므로 3을 5와 비교합니다. 3이 5보다 작으므로 바꾸지 않습니다.

3. 위치 변화와 상관없이 세번째 인덱스와 네 번째 인덱스를 비교합니다. 이번에도 5의 크기가 7보다 작으므로 위치는 변하지 않습니다.

4. 네번째 인덱스와 다섯 번째 인덱스를 비교하고 7의 크기가 1보다 큼으로 바꿉니다.

 

위 과정이 한사이클입니다. 사이클 진행 시마다 최댓값이 마지막 인덱스로 가게 됩니다. 따라서 사이클이 반복될 때 마지막 인덱스는 포함할 필요가 없습니다. 마지막 인덱스를 제외하고 진행하여 비교 횟수는 다음과 같습니다. 한 사이클 진행 시 전 사이클보다 1씩 적게 비교하므로 (n-1, n-2, n-3 ... 1) 선택 정렬과 같이 공차가 -1인 등차수열의 형태이고 수열의 합은 n(n+1)/2의 공식을 가지므로 O(N^2)를 가지게 됩니다. 시간 복잡도는 선택 정렬과 같지만 실제 버블 정렬이 선택 정렬보다는 수행 시간이 오래 걸립니다. 왜냐하면 선택 정렬은 최솟값을 구하고 위치를 바꾸는 연산을 한 번만 수행하지만 버블 정렬은 조건을 만족할 시 매 회 위치를 바꾸기 때문입니다.

 

다음은 파이썬 코드입니다.

 

import sys

numbers = list(map(int,sys.stdin.readline().split()))

length = len(numbers)-1         #총 길이에서 -1 만큼 연산시 모두 정렬되기 때문에 -1을 

for i in range(length):
    for index,value in enumerate(numbers[:length-i]):
        if value > numbers[index + 1]:
            numbers[index],numbers[index + 1] = numbers[index + 1],numbers[index]

print(numbers)

 

 

입출력