[Algorithm] 버블 정렬

1. 버블정렬 개념
2. 구현 코드
3. 시간복잡도

---

개념

인접한 두 원소를 검사하여 정렬하는 알고리즘

뒤에서부터 앞으로 정렬해나가는 구조

 

구현 코드

def bubble_sort(arr):
        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]

 

시간 복잡도 : O(N*2)

루프문으로 맨 뒤부터 맨 앞까지 모든 인덱스에 접근 -> O(N)

하나의 루프에서는 인접한 값들의 대소 비교 및 자리 교대 -> O(N)

=> O(N^2)

 

최적화

이전 패스에서 앞뒤 자리비교(swap)이 한 번도 일어나지 않았다면 정렬되지 않는 값이 하나도 없었다고 간주할 수 있다.

이럴 경우, 이후 패스를 수행하지 않아도 된다.

def bubble_sort(arr):
	for i in range(len(arr)-1, 0, -1):
            swapped = False
            for j in range(i):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
                    swapped = True
            if not swapped:
                break