[Algorithm] 정렬 알고리즘_2(버블 정렬)

06-2 버블 정렬

버블 정렬(bubble sort): 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘으로, 단순 교환 정렬이라고도 합니다.

버블 정렬 알아보기

버블 정렬의 첫 번째 패스

위 그림은 이웃한 원소를 비교하고, 필요하면 교환하는 전체 작업 과정입니다. 이때 원소 수가 n인 배열에서 n -1번 비교·교환을 하면 가장 작은 원소 1이 맨 앞으로 이동합니다. 이러한 일련의 비교·교환하는 과정을 패스(pass)라고 합니다.

---

버블 정렬 프로그램

실습 6-1 버블 정렬 알고리즘 구현하기

이 프로그램은 n개의 원소 수와 각각의 원솟값을 입력받습니다. i값을 0부터 n - 2까지 1씩 증가시키고, 패스를 n - 1번 수행합니다.

# 버블 정렬 알고리즘 구현하기

from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
  """버블 정렬"""

  n = len(a)
  for i in range(n - 1):
    for j in range(n - 1, i, -1):
      if a[j - 1] > a[j]:
        a[j - 1], a[j] = a[j], a[j - 1]


if __name__ == '__main__':
  print('버블 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num    # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  bubble_sort(x)      # 배열 x를 버블 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

버블 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 7
x[4]: 1
x[5]: 9
x[6]: 8
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

교환 과정 출력

# 버블 정렬 알고리즘 구현하기(정렬 과정을 출력)

from typing import MutableSequence

def bubble_sort_verbose(a: MutableSequence) -> None:
  """버블 정렬(정렬 과정을 출력)"""
  ccnt = 0           # 비교 횟수
  scnt = 0           # 교환 횟수
  n = len(a)
  for i in range(n - 1):
    print(f'패스 {i + 1}')
    for j in range(n - 1, i, -1):
      for m in range(0, n - 1):
        print(f'{a[m]:2}' + ('  ' if m != j - 1 else
                             ' +' if a[j - 1] > a[j] else ' -'),
                             end = '')
        print(f'{a[n - 1]:2}')
        ccnt += 1
        if a[j - 1] > a[j]:
          scnt += 1
          a[j - 1], a[j] = a[j], a[j - 1]
    for m in range(0, n - 1):
      print(f'{a[m]:2}',end=' ')
    print(f'{a[n - 1]:2}')
  print(f'비교를 {ccnt}번 했습니다.')
  print(f'교환을 {scnt}번 했습니다.')
  
if __name__ == '__main__':
  print('버블 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num    # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  bubble_sort_verbose(x)      # 배열 x를 버블 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

---

알고리즘의 개선 1

이미 정렬을 마친 상태라면 그 이후의 패스는 원소 교환을 하지 않습니다. 즉, 어떤 패스의 원소 교환 횟수가 0이면 모든 원소가 정렬을 완료한 경우이므로 그 이후의 패스는 불필요하다고 판단하여 정렬을 중단합니다. 이러한 중단 방식을 적용하면 정렬을 모두 마쳤거나 정렬이 거의 다 된 배열에서는 비교 연산이 크게 줄어 실행 시간을 단축할 수 있습니다.

실습 6-3 버블 정렬 알고리즘 구현하기(알고리즘의 개선 1)

# 버블 정렬 알고리즘 구현하기(알고리즘의 개선 1)

from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
  """버블 정렬(교환 횟수에 따른 중단)"""
  n = len(a)
  for i in range(n - 1):
    exchng = 0        # 패스에서 교환 횟수
    for j in range(n - 1, i, -1):
      if a[j - 1] > a[j]:
        a[j -1], a[j] = a[j], a[j - 1]
        exchng += 1
      if exchng == 0:
        break

if __name__ == '__main__':
  print('버블 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num    # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  bubble_sort(x)      # 배열 x를 버블 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

새로 추가한 변수 exchng는 패스를 시작하기 전에 0으로 초기화하고, 원소를 교환할 때마다 1씩 증가시킵니다. 따라서 하나의 패스를 마친(10행의 for 문을 완료한) 시점에서 exchng 값은 패스에서의 교환 횟수와 같습니다.

마지막 패스를 종료한 시점에서 exchng값이 0이면 정렬을 마친 것이므로, break 문에 의해 바깥쪽 for 문을 강제로 탕출하고 함수 실행을 종료합니다.

---

알고리즘의 개선 2

 각각의 패스에서 비교·교환을 하다가 어떤 특정한 원소 이후에 교환하지 않는다면 그 원소보다 앞쪽에 있는 원소는 이미 정렬을 마친 것입니다. 따라서 두 번째 패스는 위 그림처럼 첫 번째 원소를 제외한 6개가 아니라 4개로 좁혀서 비교·교환하면 됩니다.

실습 6-4 버블 정렬 알고리즘 구현하기(알고리즘의 개선 2)

# 버블 정렬 알고리즘 구현하기(알고리즘의 개선 2)

from typing import MutableSequence

def bubble_sort(a: MutableSequence) -> None:
  """버블 정렬(스캔 범위를 제한)"""
  n = len(a)
  k = 0
  while k < n - 1:
    last = n - 1
    for j in range(n - 1, k, -1):
      if a[j - 1] > a[j]:
        a[j - 1], a[j] = a[j], a[j - 1]
        last = j
    k = last

if __name__ == '__main__':
  print('버블 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num    # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  bubble_sort(x)      # 배열 x를 버블 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

새로운 변수 last는 각 패스에서 마지막으로 교환한 두 원소 가운데 오른쪽 원소인 a[j] 인덱스를 저장합니다. 교환할 때마다 오른쪽 원소의 인덱스값을 last에 대입합니다. 하나의 패스를 마친 시점에 last의 값을 k에 대입하여 다음에 수행할 패스의 스캔 범위를 a[k]로 제한합니다. 

그러면 다음 패스에서 마지막으로 비교할 두 원소는 a[k]와 a[k + 1]입니다.

---

셰이커 정렬 알아보기

홀수 패스에서는 가장 작은 원소를 맨 앞으로 이동시키고, 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동시켜 패스의 스캔 방향을 번갈아 바꾸어 보겠습니다. 그러면 앞의 실행 결과보다 적은 비교 횟수로 정렬할 수 있습니다.

버블 정렬을 개선한 알고리즘을 셰이커 정렬(shaker sort)이라고 하며, 양방향 버블 정렬(bidirectional bubble sort), 칵테일 정렬(cocktail sort), 칵테일 셰이커 정렬(cocktail shaker sort)이라고도 합니다.

실습 6-5 셰이커 정렬 알고리즘 구현하기

# 셰이커 정렬 알고리즘 구현하기

from typing import MutableSequence

def shaker_sort(a: MutableSequence) -> None:
  """셰이커 정렬"""
  left = 0
  right = len(a) - 1
  last = right
  while left < right:
    for j in range(right, left, -1):
      if a[j - 1] > a[j]:
        a[j - 1], a[j] = a[j], a[j - 1]
        last = j
    left = last

    for j in range(left, right):
      if a[j] > a[j + 1]:
        a[j], a[j + 1] = a[j + 1], a[j]
        last = j
    right = last

if __name__ == '__main__':
  print('셰이커 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num    # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  shaker_sort(x)      # 배열 x를 버블 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

위 프로그램은 while 문 안에 for문이 2개 들어 있는 구조입니다.. 첫 번째 for문은 실습 6-4의 버블 정렬과 마찬가지로 나열된 원소를 맨 뒤에서 맨 앞으로 스캔합니다. 그리고 두번째 for문에서는 원소를 맨 앞에서 맨 뒤로 스캔합니다.

여기에서 선언한 변수 left는 스캔 범위의 첫 원소 인데스이며, right는 스캔 범위의 마지막 원소 인덱스입니다.

 

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file:
https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습