버블 정렬 (Bubble Sort)

버블 정렬은 아주 기본적인 정렬 알고리즘이지만 시간 복잡도때문에 실제로는 잘 사용하지 않는 알고리즘이다.

 

시간 복잡도

Best - O(N^2)

Average - O(N^2)

Worst - O(N^2)

설명

출처 : https://www.cs.mtsu.edu/~xyang/2170/bubbleSort.html

버블정렬은 인접한 두 요소를 비교하여 큰 요소를 오른쪽으로 보내는 정렬 방법이다.

이렇게 배열을 한 바퀴 돌면 맨 끝에 제일 큰 요소가 하나 고정된다.

 

이를 길이가 n인 배열에서 고정된 요소들을 제외하고 n - 1 번 반복하면 최종적으로 모든 요소가 오름차순으로 정렬된다.

구현(파이썬)

arr = [5, 1, 4, 2, 8]

for i in range(len(arr) - 1, 0, -1):
    for j in range(i):
        # 오름차순 기준, 내림차순은 부호를 반대로
        if arr[j] > arr[j + 1]:
            arr[j], arr[j + 1] = arr[j + 1], arr[j]