[파이썬][알고리즘] 버블 정렬 (bubble sort)

버블 정렬 (bubble sort)

• 버블 정렬: 인접한 두 데이터를 이용하여 대소 관계를 비교하여 순서대로 정렬하는 알고리즘이다.
  • 참조 (visualgo.net/en/sorting)

데이터가 2개일 때

데이터가 3개일 때

• 이런 식으로 규칙을 찾아 나가면 총데이터가 n개일 때 최악의 경우 데이터를 1번 시행에서 총 n-1번 대소 검사를 하고 n-1번 반복을 한다.
  • 1번 시행을 하면 가장 큰 데이터가 가장 뒤로 이동한다.
  • 이때 굳이 가장 마지막 데이터를 비교할 필요가 없어지므로 데이터의 길이를 시행 횟수만큼 빼준다.
  • 1번 시행했을 때 자리바꿈이 일어나지 않으면 중지를 한다.

def bubblesort(data):
    for trial in range(len(data) - 1):
        change = False # 자리바꿈이 일어났는지 아닌지 확인
        for i in range(len(data) - trial - 1):
            if data[i] > data[i + 1]:
                data[i], data[i + 1] = data[i + 1], data[i]
                change = True

        if change == False: # 자리바꿈 없으면 중지
            break

    return data

import random

num = random.sample(range(100), 50) # 0 ~ 99까지 수에서 랜덤으로 50개
print(num)
print(bubblesort(num))

[50, 49, 30, 78, 74, 27, 2, 34, 56, 37, 13, 46, 4, 22, 9, 44, 36, 92, 41, 45, 19, 12, 88, 86, 81, 48, 66, 3, 29, 89, 47, 82, 11, 51, 85, 95, 69, 61, 70, 72, 93, 26, 80, 0, 42, 38, 76, 20, 35, 25]
[0, 2, 3, 4, 9, 11, 12, 13, 19, 20, 22, 25, 26, 27, 29, 30, 34, 35, 36, 37, 38, 41, 42, 44, 45, 46, 47, 48, 49, 50, 51, 56, 61, 66, 69, 70, 72, 74, 76, 78, 80, 81, 82, 85, 86, 88, 89, 92, 93, 95]

시간 복잡도

• 데이터 길이 n일 때 반복문이 2개
  • O($n^2$)
• 처음에 정렬이 된 상태이면 O(n)