All Articles

알고리즘 - 버블 정렬(Bubble sort)

정렬(Sorting)이란

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것이다. 정렬을 하는 데에도 다양한 방식(알고리즘)이 있기 때문에 각 알고리즘간 성능 비교를 통해 알고리즘 성능에 대해 이해하기도 좋다.

버블 정렬(Bubble sort)이란

두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘이다. 리스트로 생각하면 인접한 인덱스 값을 비교해서 작은 값이 큰 값보다 뒤에 있으면 두 인덱스를 바꿔주는 것이다.

버블 정렬 예시

요소가 4개일 때

nums = [2, 4, 1, 3]

  1. 2, 4 비교, 자리 바꿈 없음 [2, 4, 1, 3]
  2. 4, 1 비교, 자리 바꿈 [2, 1, 4, 3]
  3. 4, 3 비교, 자리 바꿈 [2, 1, 3, 4] - 1턴 완료
  4. 2, 1 비교, 자리 바꿈 [1, 2, 3, 4]
  5. 2, 3 비교, 자리 바꿈 없음 [1, 2, 3, 4]
  6. 3, 4 비교, 자리 바꿈 없음 [1, 2, 3, 4] - 2턴 완료

요소가 5개일 때 1

nums = [5, 1, 2, 8, 7]

  1. 5, 1 비교, 자리 바꿈 [1, 5, 2, 8, 7]
  2. 5, 2 비교, 자리 바꿈 [1, 2, 5, 8, 7]
  3. 5, 8 비교, 자리 바꿈 없음 [1, 2, 5, 8, 7]
  4. 8, 7 비교, 자리 바꿈 [1, 2, 5, 7, 8] - 1턴 완료
  5. 1, 2 비교, 자리 바꿈 없음 [1, 2, 5, 7, 8]
  6. 2, 5 비교, 자리 바꿈 없음 [1, 2, 5, 7, 8]
  7. 5, 7 비교, 자리 바꿈 없음 [1, 2, 5, 7, 8]
  8. 7, 8 비교, 바리 바꿈 없음 [1, 2, 5, 7, 8] - 2턴 완료

요소가 5개일 때 2

nums = [7, 3, 2, 4, 1]

  1. 7, 3 비교, 자리 바꿈 [3, 7, 2, 4, 1]
  2. 7, 2 비교, 자리 바꿈 [3, 2, 7, 4, 1]
  3. 7, 4 비교, 자리 바꿈 [3, 2, 4, 7, 1]
  4. 7, 1 비교, 자리 바꿈 [3, 2, 4, 1, 7] - 1턴 완료
  5. 3, 2 비교, 자리 바꿈 [2, 3, 4, 1, 7]
  6. 3, 4 비교, 자리 바꿈 없음 [2, 3, 4, 1, 7]
  7. 4, 1 비교, 자리 바꿈 [2, 3, 1, 4, 7]
  8. 4, 7 비교, 자리 바꿈 없음 [2, 3, 1, 4, 7] - 2턴 완료
  9. 2, 3 비교, 자리 바꿈 없음 [2, 3, 1, 4, 7]
  10. 3, 1 비교, 자리 바꿈 [2, 1, 3, 4, 7]
  11. 3, 4 비교, 자리 바꿈 없음 [2, 1, 3, 4, 7]
  12. 4, 7 비교, 자리 바꿈 없음 [2, 1, 3, 4, 7] - 3턴 완료
  13. 2, 1 비교, 자리 바꿈 [1, 2, 3, 4, 7]
  14. 2, 3 비교, 자리 바꿈 없음 [1, 2, 3, 4, 7]
  15. 3, 4 비교, 자리 바꿈 없음 [1, 2, 3, 4, 7]
  16. 4, 7 비교, 자리 바꿈 없음 [1, 2, 3, 4, 7] - 4턴 완료

귀납적 판단

  • 1턴 당 비교 횟수는 리스트 길이에서 1을 뺀 값이다.
  • 1턴을 돌 때마다 정렬되지 않은 값 중 제일 큰 값이 가장 뒤에 위치한다.
  • 전체 턴 수는 리스트 길이를 넘지 않는다.
  • 자리 바꿈이 한 번도 일어나지 않으면 이미 정렬이 되어있다는 이야기이므로 1턴 후에 반복문을 종료해도 된다. (성능 문제)

버블 정렬 알고리즘 시나리오

  1. 리스트 길이에서 1을 뺀만큼 반복한다. - 턴 수 지정
  2. 리스트 길이에서 1을 뺀만큼 값끼리 비교한다. - 비교 횟수 지정
  3. 앞에 있는 값이 뒤에 있는 값보다 크면 위치를 바꾼다.
  4. 위치를 바꾼 횟수가 0이면 그대로 반복문을 종료한다.

코드 작성

def bubblesort(nums):
  is_swapped = False
  for i in range(len(nums)-1):
    for idx in range(len(nums)-1):
      if nums[idx] > nums[idx+1]:
        nums[idx], nums[idx+1] = nums[idx+1], nums[idx]
        is_swapped = True
    if is_swapped = False:
      break
  return nums

검증

import random

# 0부터 99까지 숫자 중 50개를 무작위로 뽑아서 리스트 생성
nums = random.sample(range(100), 50)
print(bubblesort(nums))

복잡도

이중 for문이므로 O(n2)

기억해두기

리스트 내 두 요소 위치 바꾸는 법
nums[idx], nums[idx+1] = nums[idx+1], nums[idx]

Published 20 Aug 2020