버블정렬(BubbleSort) 이론과 파이썬 구현

버블정렬(BubbleSort)

 

버블정렬은 이웃하는 숫자를 비교하여 작은 수를 앞으로 이동시키는 과정을 반복합니다.

이를 한번 진행하면 가장 큰 수가 리스트의 오른쪽 끝으로 이동합니다. 그럼 오른쪽 리스트는 정렬된 상태가 됩니다.

이 과정을 리스트 크기- 1 까지 반복하면 전체를 정렬할 수 있습니다.

 

작은 수를 앞으로 이동시키는 과정이 물속에서 버블(거품)이 떠오르는 것과 유사하여 버블정렬이라는 이름을 사용합니다. 

 

버블정렬을 이용한 첫번째 과정 반복 결과

 

3 > 2 이기 때문에 3과 2를 교환해줍니다.

3 은 5보다 크지 않기 때문에 교환하지 않습니다.

5 > 4 이기 때문에 5와 4를 교환해줍니다.

5 > 1 이기 때문에 5와 1를 교환해줍니다.

 

첫번째 과정을 통해 5는 정렬 완료 되었습니다.

다음 반복때는 5를 제외하고 정렬합니다.

 

버블정렬을 이용한 전체 정렬 과정

 

버블정렬의 파이썬 코드입니다.

a = [3, 2, 5, 4, 1]

for i in range(len(a)-1):
    for j in range(len(a)-1-i):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
        
# 출력>>[1, 2, 3, 4, 5]
print(a)