[알고리즘] 정렬 | [5] 거품 정렬(버블 정렬) (Bubble Sort) - Python

[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [1] 정렬, 선택 정렬 (Selection Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [2] 삽입 정렬 (Insertion Sort) - Python

[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

 

[알고리즘] 정렬 | [3] 퀵 정렬 (Quick Sort) - Python

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

[알고리즘] 정렬 | [4] 계수 정렬 (Counting Sort) - Python

 

 

^ 다른 정렬들이 궁금하다면 ^

 

1. 거품 정렬/버블 정렬(Bubble Sort)이란?

- 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

 : 인접한 2개의 데이터를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. >> 자리를 바꾸는 정렬 알고리즘

- 선택 정렬과 기본 개념이 유사하다.

- 내림차순, 오름차순 모두 구현 가능

 

2. 거품 정렬 알고리즘의 상세 개념(1)

- 버블 정렬은 첫 번째 데이터와 두 번째 데이터를, 두 번째 데이터와 세 번째 데이터를, 세 번째와 네 번째를, …

  이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

 

- 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.

 

2. 거품 정렬 알고리즘의 상세 개념(2)

- 애매하게 이해가 되었을 것이라고 생각하여 다시 정리를 하였다.

- 거품정렬은 앞뒤에 데이터를 계속 비교해서 데이터를 정리한다는 개념이다. 이해는 되는데 코드로 구현을 할 때 어려움이 있을 수 있으므로 예시를 들며 다시 알아볼 것이다.

 

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

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

원리를 이해하고 위 애니메이션을 보면, 거품정렬을 이해하는데 도움이 될 것이다.

3. 요약

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

4. 거품 정렬 동작 예시

def bubble_sort_ascending(data):
    # 총 교환 횟수를 기록하는 변수
    n_swap = 0
 
    # 총 비교 횟수는 데이터 길이보다 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회 로직을 다 돌았음에도 불구하고 교환이 없으면 루프 종료       
        if swap == False:
            break
    return data , n_swap

내림차순으로 할 거면 data[i2] < data[i2 + 1] 이렇게 부등호 방향을 바꿔준다.