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

이번 글에서는 정렬 알고리즘의 가장 기본이 되는 버블 정렬, 선택 정렬, 삽입 정렬에 대해서 알아보고 세 알고리즘의 복잡도에 대해서 비교해 보겠습니다.

버블 정렬 (Buble Sort)

버블 정렬은 인접한 두 요소를 비교하여 의도한 순서가 될 때까지 교체하는 정렬 알고리즘입니다.

 

마치 운동시합 중에 파도응원을 하는 것처럼 배열의 각 요소들은 인접한 요소와 비교를 반복하며 끝까지 이동합니다. 마치 이 모습이 수면 위로 올라오는 물속 기포의 움직임 같다고 해서 버블 정렬이라고 이름이 붙여졌습니다.

버블 정렬의 작동 원리

각 맴버들을 오름차순(ascending order)으로 정렬하려고 한다고 가정해 봅시다.

1. 첫번째 반복 (비교하고 교체하기)

1. 첫 번째 인덱스에서 시작하여 첫 번째 요소와 두 번째 요소를 비교합니다.
2. 첫 번째 요소가 두 번째 요소보다 크면 교체합니다.
3. 이제 두 번째 요소와 세 번째 요소를 비교합니다. 순서가 맞지 않으면 교체합니다.
4. 위의 과정을 마지막 요소까지 반복합니다.

위의 과정이 끝난 후 위 그림과 같이 배열의 맨 마지막 요소는 이 배열의 가장 큰 요소가 됩니다.

2. 남은 반복

위의 스탭을 나머지 스탭에서도 반복합니다. 예를 들어 두번째 반복에서는 위의 스탭을 반복해서 두번째로 큰 요소가 이 배열의 맨 위에서 두번째에 배치되게 됩니다.

이런 식으로 위의 과정을 마지막 요소까지 반복합니다.

매 반복문마다 아직 정렬되지 않은 요소를 만날 때까지 비교합니다.

반복문을 요소의 갯수만큼 반복하면 모든 요소가 최종적으로 정렬되게 됩니다.

버블 정렬 알고리즘

def bubble_sort(arr): 
  n = len(arr)
  for i in range(n): 
    for j in range(0, n-i-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
  return arr

버블 정렬 최적화 알고리즘

위의 알고리즘에서는 배열이 이미 정렬된 경우에도 모든 비교가 수행됩니다.

따라서 실행 시간이 늘어납니다.

이 문제를 해결하기 위해 swapped라는 변수를 추가로 도입할 수 있습니다. 요소의 스왑이 발생하면 swapped의 값은 참으로 설정됩니다. 그렇지 않으면 false로 설정됩니다.

반복 후 스왑이 발생하지 않으면 swapped의 값은 거짓이 됩니다. 이는 요소가 이미 정렬되었으므로 더 이상 반복할 필요가 없음을 의미합니다.

이렇게 하면 실행 시간이 단축되고 버블 정렬을 최적화하는 데 도움이 됩니다.

def bubble_sort(arr):   
  n = len(arr)
  for i in range(n): 
    swapped = False
    for j in range(0, n-i-1):
      if arr[j] > arr[j+1]:
        arr[j], arr[j+1] = arr[j+1], arr[j]
        swapped = True
    if not swapped:
      break
  return arr

버블 정렬 복잡도

시간 복잡도
Best	O(n)
Worst	O(n^2)
Average	O(n^2)
공간 복잡도	O(1)
안정성	예

버블 정렬의 장점

• 버블 정렬은 이해하고 구현하기 쉽습니다.
• 추가적인 메모리 공간을 요구하지 않습니다. (공간 복잡도 O(1))
• 이것은 안정성을 보장하는 정렬입니다. 즉 같은 값의 요소들의 전후 배치가 정렬된 이후에도 유지가 됩니다.

버블 정렬의단점

• 버블 정렬은 시간 복잡도가 O(n^2) 입니다. 이것은 정렬할 데이터가 클 경우 매우 느린 성능을 보여줍니다.

버블 정렬의 활용

버블 정렬은 알고리즘이 간단하기 때문에 보통 정렬 알고리즘에 대한 개념을 소개할 때 사용됩니다. 또한 데이터의 크기가 크지 않을 때나 성능 보다는 안정성이 중요한 요소일 때 알고리즘이 간단하기 때문에 사용할 수 있습니다.