[정렬] bubble sort

bubble sort는 '정렬' 하면 빠질 수 없는 가장 무지막지한(?) 방법이라고 생각한다.

방법은 첫 번째 원소부터 마지막 원소까지 비교해감으로써 한 개의 원소를 정렬하고,

이 과정을 마지막 원소까지 반복하는 것이다.

 

시간복잡도

- 비교 횟수

i=0일 때 n-1번, 1일때 n-2번, ... 이렇게 해서 n(n-1)/2

- 교환 횟수

최악의 경우는 원소가 역순으로 정렬된 경우이고, n(n-1)/2회가 발생한다.

(temp를 이용하는 swap()을 생각한다면, 3*n(n-1)/2회가 발생함)

최상의 경우는 원소가 정렬된 경우이고, 0회가 발생한다.

- T(n) = O(n^2)

 

def bubble_sort(arr):
    # 배열의 범위를 설정
    # last는 마지막 원소의 index
    for last in range(len(arr)-1, -1, -1):
        # 정렬할 배열의 비교 대상을 설정
        # i는 비교 대상 원소 중 왼쪽 원소의 인덱스
        for i in range(last):
            if arr[i] > arr[i+1]:
                arr[i], arr[i+1] = arr[i+1], arr[i]

arr = [2, 5, 3, 8, 6, 7, 1, 9, 4]

print(arr) # [2, 5, 3, 8, 6, 7, 1, 9, 4]
bubble_sort(arr)
print(arr) # [1, 2, 3, 4, 5, 6, 7, 8, 9]