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

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

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

 

[ 시간복잡도 ]

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

 

[ 예시 ]

 

[ 코드 ]

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)