알고리즘 | 버블 정렬 / 거품 정렬 (Bubble Sort)

버블 정렬 / 거품 정렬 (Bubble Sort)

1. 개요

버블 정렬은 서로 인접한 두 원소를 검사해서 정렬하는 알고리즘이다. 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, ..., 마지막-1 번째 자료와 마지막 자료의 대소를 비교해 교환한다. 1회전 할 때 마다 마지막 자료는 가장 큰 값이 되기 때문에 (조건이 오름차순일 경우) 정렬에서 제외한다.

2. 예시

3. 시간복잡도

(n-1)+(n-2)+...+2+1 => n(n-1)/2 = O(n^2)

4. 코드 (Python)

size = int(input())
arr = []

for i in range(size):
    arr.append(int(input()))

for i in reversed(range(size)):
    for j in range(i):
        if arr[j] > arr[j+1]:
            temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp

for i in arr:
    print(i)