개념

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다.

1. 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가 오른쪽에 가도록 교환한다.
2. 맨 끝까지 가면 가장 큰 원소를 찾은 것이므로, 이 과정을 다시 나머지 n-1개 수에 대해서 반복한다.

시간복잡도

처음 가장 큰 원소를 구할 때 n-1번 비교

두 번째 큰 원소를 구할 때 n-2번 비교

$(n-1) + (n-2) + … + 1= n(n-1)/2$ ⇒ $O(n^2)$

공간복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되기 때문에 $O(1)$이다.

예시코드

import random

def bubble_sort(A):
    for i in range(len(A)-1): #base는 마지막 하나 전까지
        for j in range(len(A)-1-i): #i를 빼주는 이유는 뒷쪽은 이미 오름차순으로 정렬된 상태이기 때문
            if(A[j]>A[j+1]):
                A[j],A[j+1]=A[j+1],A[j]
    return A

if __name__=="__main__":
    num_list=list(range(1,21))
    random.shuffle(num_list)
    print("정렬 전 :",num_list)
    print("정렬 후 :", bubble_sort(num_list))

정렬 전 : [13, 7, 15, 9, 3, 6, 18, 2, 5, 10, 1, 12, 11, 8, 20, 16, 4, 19, 17, 14]
정렬 후 : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

장점