[Python]버블정렬 알고리즘 코드 및 예시로 마스터 하기

 

이번 포스팅에서는 버블정렬 알고리즘을 파이썬으로 구현하는 것부터 시작하여 실제 예시를 통해 코딩 테스트까지 대비해보는 포스팅을 다루도록 할 것이다.

 

목차

1. 버블정렬의 기본 개념

2. 버블정렬(Bubble Sort) 알고리즘 원리 이해하기

3. 버블 정렬 Python 코드로 구현하기

4. 버블 정렬 시공간복잡도 계산하기

 

1. 버블정렬(Bubble Sort)의 기본 개념

 

버블정렬이란 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘을 말한다. 물론 정렬의 원칙에 따라서는 버블정렬을 내림차순으로 구현할 수도 있고, 오름차순으로 구현할 수도 있다. 이번 포스팅에서는 이 두 방법 모두 알아보고 코드로 구현해보고자 한다. 

 

버블 정렬의 원리 이해하기

 

 

2. 버블정렬(Bubble Sort) 알고리즘 원리 이해하기

 

앞뒤에 데이터를 계속 비교해서 데이터를 정리한다는 버블 정렬의 개념은 이해하기 편하다. 그러나 실제로 코드로 구현할 때는 막힐 수도 있다. 따라서 버블정렬의 예시를 통해 실제 어떤 원리를 통해서 정렬이 되는지 알아보고자 한다. 

 

적용 횟수	데이터의 형태	교환이 발생 여부	총 교환 횟수
원본 데이터	1, 9, 3, 2	0회	0회
1회 버블 정렬 로직 적용	1, 3, 2, 9	2회	2회
2회 버블 정렬 로직 적용	1, 2, 3, 9	1회	3회

 

• 버블 정렬의 원리 상세 설명
  • 1회 로직 적용시 발생하는 일
    • 시작하는 인접한 데이터는 1과 9 비교가 이루어진다. 그러나 이 부분은 정렬이 된 상태이기 때문에 아무런 일이 발생하지 않는다.
    • 다음 인접한 데이터는 9와 3이다. 이 9는 3보다 크기 때문에 뒤로 가야 하고, 1회 교환이 발생하였다. 
    • 다음 인접한 데이터는 9와 2이다. 동일한 이유로 교환이 1회 발생하며 9는 맨 뒤로 가게 된다.
    • 따라서 1회 로직에서는 총 2회의 교환이 이루어졌다.
  • 2회 로직 적용시 발생하는 일 상세 설명
    • 데이터는 현재 1, 3, 2, 9이고 시작하는 인접한 데이터는 1과 3이다. 그러나 이 부분에서는 정리할 필요가 없기 때문에 아무런 일이 발생하지 않는다.
    • 다음 인접한 데이터는 3과 2이이다. 여기서도 3은 2보다 큰 수이기 때문에 1회 교환이 발생한다. 
    • 다음 인접한 데이터는 3과 9인데, 이 부분에서는 아무런 일이 발생하지 않기에 교환횟수는 0회 이다. 
    • 따라서 2회 로직 적용시 기록되는 교환횟수는 1회가 된다. 

 

이 원리를 차근찬근 이해하고 위에 있는 그림 예시를 보면, 버블정렬 알고리즘의 원리를 완벽하게 이해하는데 도움이 될 것이다. 알고리즘의 핵심은 항상 효율적이고 논리적으로 구성하는데 있다. 따라서 버블 정렬를 코드로 구현할 때 반드시 알아두어야 할 원리를 집약하면 아래와 같다. 

 

• 버블 정렬의 원리 요약
  • 원리1. 총 비교 횟수는 데이터 길이 -1 회 발생한다. 
  • 원리2. 맨 뒤에 있는 수는 이미 정렬이 완료된 수이기에 다음 로직 적용시 제외 시켜서 반복문을 구성한다. 
  • 원리3. 정렬이 끝난 경우 무한 Loop를 돌지 않기 위해 확인할 수 있는 변수를 활용한다. 
  • 원리4. 총 몇 번 교환이 이루어졌는지 파악할 수 있도록 교환이 이루어졌을 때 데이터로 기록한다. 

 

 

3. 버블 정렬 Python 코드로 구현하기

 

 
def bubble_sort_ascending(data):
    ## 총 교환 횟수를 기록하는 변수 (버블 정렬 원리 4)
    n_swap = 0
 
    ## 총 비교 횟수는 데이터 길이보다 1회 작게 이루어져야 함 (버블정렬 원리1)
    for i in range(len(data) - 1):
        
        ## 정렬이 다 끝났는지 확인하는 변수
        swap = False
        
        
        ## 정리된 데이터는 반복할 필요가 없기 때문에 i회를 제외 시킨다.
        for i2 in range(len(data) - i - 1):
 
            ## 버블 정렬을 오름차순 혹은 내림차순으로 결정할 수 있는 영역
            if data[i2] > data[i2 + 1]:
                
                ## 순서를 바꿔 준 뒤에 교환이 이뤄졌음을 알린다.
                data[i2], data[i2 + 1] = data[i2 + 1], data[i2]
                swap = True
                n_swap += 1
 
        ## 1회 로직을 돌았음에도 불구하고 교환이 발생하지 않으면 Loop를 종료한다.        
        if swap == False:
            break
    return data , n_swap

 

• 버블정렬 Python 코드 상세 설명
  • 2번째 줄에 있는 코드는 버블 정렬 실행 중에 교환횟수를 기록하는 변수이다. 초기에는 아무런 교환이 발생하지 않았기 때문에 0회로 기록한다. 
    
    
  • 첫 번째 Loop(7번째 줄)에서 발생하는 반복 수는 총 n-1회이며, 이는 원리 1번을 구현한 코드이다. 
    
    
  • 10번째 줄은 n회 반복 중 교환이 이루어졌는지 안 이루어져는지 확인하는 변수이다. 만약 로직을 1회 다 돌았음에도 불구하고, 교환이 발생하지 않았다면 모든 정렬이 끝났음을 알 수 있다. 
    
    
  • 14번째 줄은 n회 로직 안에서 교환이 이루어지는 작업이다. 단, 이때 이미 끝난 데이터에 대해서 다시 비교할 필요가 없기 때문에 총 n-1에서 이미 로직이 발생한 횟수 i를 제외시켜주어야 한다. 
    
    
  • 17번째 줄은 버블 정렬이 오름차순 혹은 내림차순으로 결정하는 로직의 핵심이다. 위 코드에서는 인접한 두 데이터를 오름차순으로 정렬해주기 위해서 data[i2] > data[i2 + 1]로 설정하였다. 만약 내림차순으로 변경해주기 위해서는 부호를 반대로 설정해주면 된다. 
    
    또한 이 로직이 끝나면 교환이 1회 발생한 것이기 때문에 n_swap에 1을 더 해주고, 교환이 발생했음을 알려주도록 swap 변수를 True로 바꿔주어야 한다. 

 

이러한 코드가 실제로 잘 구현되어 작동하는지 예시를 통해서 확인해보도록 하겠다. 총 2가지 샘플 데이터를 생성하였고, 중간에 있는 코드는 위와 동일하기 때문에 참고하길 바란다. 랜덤 데이터가 생성되었을 때는 모두 정렬이 되지 않은 상태였다. 

 

버블정렬 코드 및 예시

각각의 버블 정렬 로직을 적용한 뒤에 결과는 오름차순과 내림차순으로 아주 깔끔하게 정리된 것을 볼 수 있다. 첫 번째 예시 데이터에서는 총 18회 교환이 발생하였으며, 두 번째 예시 데이터에서는 총 27회 교환이 발생한 것을 알 수 있었다. 여기까지 이해했으면 버블 정렬을 이해할 때 필요한 모든 것을 이해한 것이다. 

 

 

 

 

4. 버블 정렬 시공간복잡도 계산하기

 

 

빅오 표기법으로 계산을 해봤을 때 버블 정렬의 시공간 복잡도는 O(n^2)이 된다. 이러한 이유는 바로 버블정렬의 원리1번 및 2번으로 인해 발생한다. 

 

빅오표기법에서는 상수는 생략되고 변수만 살아남는다. 그렇기에 각 반복문에서 실시되는 횟수는 n으로 정의한다. 이때 for loop 안에 for loop이 또 들어가 있기 때문에 n x n의 구조가 된다. 결론적으로 빅오표기법에 따라 O(n^2)이라는 계산이 나오게 된다. 

 

• for i in range( n - 1) → 빅오 표기법에 따라 변수 n 으로 정의
  • for  i2 in range(n - i - 1) → 빅오 표기법에 따라 변수 n 으로 정의
  • 첫 번째와 두 번째는 곱하기 로직이기 때문에 결론적으로 시공간복잡도는 n 제곱