Bubble Sort (버블정렬)

Bubble Sort (버블정렬)

버블소트는 인접한 요소들을 비교하여 정렬하는 알고리즘입니다.

인접한 두개의 요소들을 비교하여 크기가 순서대로 되어있지 않으면 서로 변경합니다.

O(n^2)의 시간복잡도를 가지지만 코드가 단순하여 자주 사용됩니다.

Bubble Sort 정렬과정

초기상태: (5 3 4 2 1)

1. 1회전(3 5 4 2 1) -> (3 4 5 2 1) : 5 > 4, 교환(3 4 2 5 1) -> (3 4 2 1 5) : 5 > 1, 교환
2. 결과: (3 4 2 1 5)
3. (3 4 5 2 1) -> (3 4 2 5 1) : 5 > 2, 교환
4. (5 3 4 2 1) -> (3 5 4 2 1) : 5 > 3, 교환
5. 2회전(3 4 2 1 5) -> (3 2 4 1 5) : 4 > 2, 교환결과: (3 2 1 4 5)
6. (3 2 4 1 5) -> (3 2 1 4 5) : 4 > 1, 교환
7. (3 4 2 1 5) -> (3 4 2 1 5)
8. 3회전(2 3 1 4 5) -> (2 1 3 4 5) : 3 > 1, 교환
9. 결과: (2 1 3 4 5)
10. (3 2 1 4 5) -> (2 3 1 4 5) : 3 > 2, 교환
11. 4회전결과: (1 2 3 4 5)
12. (2 1 3 4 5) -> (1 2 3 4 5) : 2 > 1, 교환

Bubble Sort 코드 (Python)

def bubble_sort(arr):
    length = len(arr)
    for i in range(length-1):
        for j in range(length-1-i):
            if arr[j] > arr[j+1]:
                tmp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = tmp
    return arr