버블 정렬 (Bubble Sort)

버블 정렬 알고리즘의 기본 개념

• 서로 인접한 두 원소를 검사해 정렬하는 알고리즘 
• 인접한 2개의 원소의 대소를 비교해 크기가 원하는 순서대로 되어있지 않다면 서로 교환
• 알고리즘의 과정 (총 N개일 때, 오름차순 정렬)
  
  • 1회전에 첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소, 세 번째 원소와 네 번째 원소, ... 이렇게 쭉 진행해 가며 (N-1)번째 원소와 N번째 원소를 비교하면서 조건에 맞지 않는다면 조건에 맞춰서 서로 위치 변경.
  • 1회전이 끝나면 가장 큰 원소가 맨 뒤로 이동 → 마지막 원소는 정렬 완료이므로 제외됨.
  • 2회전도 마찬가지로 진행 후 뒤에서 두 번째 원소까지 정렬 완료.
  • 정렬이 1회전 수행될 때 마다 정렬해야할 데이터가 하나씩 줄어듬.

파이썬으로 코드 구현

 

코드 구현

def bubblesort(list, N):              # N은 len(list)
    for i in range(N-1):              # 마지막으로 남는 원소는 자동으로 정렬되므로 N-1까지 
        for j in range(N-1-i):        # i가 한 바퀴 돌 때마다 정렬이 한 개씩 되므로 범위를 줄여나간다
            if list[j] <= list[j+1]:  # 오름차순을 위해 j와 j+1을 비교해서 앞의 원소가 더 작거나 같다면 패스
                continue
            else:
                list[j], list[j+1] = list[j+1], list[j] # 그 외의 경우는 앞의 원소가 큰 경우 밖에 없으므로 위치 교환

 

알고리즘 테스트 1

test = [2, 1, 9, 5, 3, 6, 2]
bubblesort(test, len(test))
print(test)

 

결과

[1, 2, 2, 3, 5, 6, 9]

 

알고리즘 테스트 2

 

아래의 네가지 데이터를 넣고 테스트도 진행해 보았다.

1. 정렬이 끝난 배열
2. 역순으로 정렬된 배열
3. 원소가 전부 같은 배열
4. 랜덤으로 구성된 배열

import time

def bubblesort(list, N):              
    for i in range(N-1):             
        for j in range(N-1-i):        
            if list[j] <= list[j+1]:  
                continue
            else:
                list[j], list[j+1] = list[j+1], list[j] 

test1 = [1, 2, 3, 4, 5, 6, 7]
test2 = [7, 6, 5, 4, 3, 2, 1]
test3 = [1, 1, 1, 1, 1, 1, 1, 1]
test4 = [0, 130, 26, 59, 556, 123, 2396, 16, 9801]

start_time1 = time.time()
bubblesort(test1, len(test1))
end_time1 = time.time()
total_time1 = (end_time1 - start_time1) * 1000

start_time2 = time.time()
bubblesort(test2, len(test2))
end_time2 = time.time()
total_time2 = (end_time2 - start_time2) * 1000

start_time3 = time.time()
bubblesort(test3, len(test3))
end_time3 = time.time()
total_time3 = (end_time3 - start_time3) * 1000

start_time4 = time.time()
bubblesort(test4, len(test4))
end_time4 = time.time()
total_time4 = (end_time4 - start_time4) * 1000

print(f'{total_time1:.4f}ms')
print(f'{total_time2:.4f}ms')
print(f'{total_time3:.4f}ms')
print(f'{total_time4:.4f}ms')

 

결과

0.0498ms
0.0446ms
0.0391ms
0.0403ms

 

random 데이터로 성능 테스트

 

성능 테스트를 위해 time 모듈과 random 모듈을 불러와서 알고리즘 코드에 붙여준다.

import random
import time

def bubblesort(list, N):
    for i in range(N-1):
        for j in range(N-1-i):
            if list[j] <= list[j+1]:
                continue
            else:
                list[j], list[j+1] = list[j+1], list[j]

data = [random.randint(1, 1000000) for _ in range(1000)]
start_time = time.time()
bubblesort(data, len(data))
print(data)
end_time = time.time()
total_time = end_time - start_time
print(f'{total_time:.4f}초')

• 데이터 1000개 일 때 : 0.0700초
• 데이터 2000개 일 때 : 0.1716초
• 데이터 4000개 일 때 : 0.6912초
• 데이터 5000개 일 때 : 1.0585초
• 데이터 10000개 일 때 : 4.2511초