[버블 정렬] Bubble Sort - Python

버블 정렬 Bubble Sort

Bubble Sort

버블 정렬

• 버블 정렬의 시간복잡도는 Worst case - O(n^2), Best case - O(n^2), Average acse - O(n^2)이다.

• 인접한 값과 계속 비교해나가며 루프를 1번 수행할때마다 1개의 값이 자리를 찾아간다.

• 앞의 값이 뒤의 값보다 클 경우 위치를 계속 바꿔나가며 마지막 index에 도달하므로 버블정렬이라 부른다.

• n개의 원소가 주어졌을 때, n*(n-1)/2만큼의 비교를 진행한다.

def bubble_sort(data):
  # 비교 횟수를 저장할 변수
  compare_count = 0
  # 총 N(N+1)/2번만큼 계산
  for j in range(len(data)-1):
    for i in range(0, len(data)-1-j):
      compare_count = compare_count + 1
      # 인접한 값 중 앞의 값이 클 경우 위치 변경
      if data[i] > data[i+1]:
        data[i], data[i+1] = data[i+1], data[i]

  print('비교 횟수는 = ', compare_count)
  return data

data = [8,5,6,2,3,4]
print(bubble_sort(data))

• 버블 정렬 작동 과정

버블 정렬 - 첫 번째 iteration 과정

버블 정렬 - 두 번째 iteration 과정

• i=0 ~ i=4 (5회)
• i=0 ~ i=3 (4회)
• i=0 ~ i=2 (3회)
• i=0 ~ i=1 (2회)
• i=0 (1회)
• 6*5/2 = 15, 시간복잡도는 O(n^2)이다.