[자료구조] 버블 정렬

버블 정렬

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하며 정렬

정렬 과정

• 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동
• 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬
• 교환하며 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬

시간 복잡도

: O(n**2)

---

예시

arr = [3, 4, 2, 1, 0]

N = len(arr)

# arr[0]부터 arr[i-1]까지 중 가장 큰 수를 맨 뒤로 보낼거야
for i in range(N-1, 0, -1):
    # arr[j]와 그 다음 값을 비교할 거야
    for j in range(i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

첫번째 i => arr[0]부터 arr[3]까지

두번째 for문 ⇂	arr[0]	arr[1]	arr[2]	arr[3]	arr[4]
첫번째 j	3 (j)	4 (j+1)	2	1	0
결과	3	4
두번째 j	3	4 (j)	2 (j+1)	1	0
결과		2	4
세번째 j	3	2	4(j)	1 (j+1)	0
결과			1	4
네번째 j	3	2	1	4 (j)	0 (j+1)
결과				0	4

두번째 i => arr[0]부터 arr[2]까지

두번째 for문 ⇂	arr[0]	arr[1]	arr[2]	arr[3]	arr[4]
첫번째 j	3 (j)	2 (j+1)	1	0	4
결과	2	3
두번째 j	2	3 (j)	1 (j+1)	0	4
결과		1	3
세번째 j	2	1	3 (j)	0 (j+1)	4
결과			0	3

세번째 i => arr[0]부터 arr[1]까지

두번째 for문 ⇂	arr[0]	arr[1]	arr[2]	arr[3]	arr[4]
첫번째 j	2 (j)	1 (j+1)	0	3	4
결과	1	2
두번째 j	1	2 (j)	0 (j+1)	3	4
결과		0	2

네번째 i => arr[0]부터 arr[1]까지

두번째 for문 ⇂	arr[0]	arr[1]	arr[2]	arr[3]	arr[4]
첫번째 j	1 (j)	0 (j+1)	2	3	4
결과	0	1

최종 결과

arr = [0, 1, 2, 3, 4]

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]
0	1	2	3	4