[422] 버블 정렬(Bubble Sort)

1. 버블 정렬 개념

맨 앞에서부터 맨 뒤까지 인접한 두 원소를 차례대로 비교합니다.

비교한 결과 더 큰 원소가 앞에 있을 경우, 비교한 두 원소의 자리를 바꿔줍니다.(제자리 정렬)

이 과정을 한 번 마치면 배열의 맨 뒤에는 가장 큰 원소가 위치합니다.

따라서 이 과정을 범위를 한 칸씩 줄여가며 계속해서 반복합니다.

2. 버블 정렬 예제

3. 버블 정렬 코드

nums = [5, 3, 4, 1, 2]

def bubble_sort(nums):
    for i in range(1, len(nums)):
        for j in range(len(nums)-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]

bubble_sort(nums)
print(nums)
# [1, 2, 3, 4, 5]

4. 버블 정렬 장점

버블 정렬은 매우 간단하고 이해하기 쉬운 정렬 알고리즘입니다.

게다가 코드 구현이 직관적이어서 초보자들이 배우기에 좋습니다.

추가 메모리 공간을 거의 사용하지 않기 때문에 메모리 사용이 제한적인 환경에서도 사용할 수 있습니다.

동일한 값을 가진 원소들의 상대적 위치가 변하지 않아 안정적인 정렬 알고리즘입니다.

5. 버블 정렬 단점

버블 정렬의 시간 복잡도는 최악과 평균 모두 $O(n^2)$입니다.

원소의 개수가 많아지면 성능이 급격히 저하됩니다.

많은 비교와 교환이 필요하여 실제 실행 시간에서 더 비효율적입니다.

6. 정렬 알고리즘 시간 복잡도 비교

정렬 알고리즘	최악(Worst)	최선(Best)	평균(Average)
버블 정렬(Bubble Sort)	$O(n^2)$	$O(n^2)$	$O(n^2)$
선택 정렬(Selection Sort)	$O(n^2)$	$O(n^2)$	$O(n^2)$
삽입 정렬(Insertion Sort)	$O(n^2)$	$O(n)$	$O(n^2)$
퀵 정렬(Quick Sort)	$O(n^2)$	$O(n\log n)$	$O(n\log n)$
병합 정렬(Merge Sort)	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
힙 정렬(Heap Sort)	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$
기수 정렬(Radix Sort)	$O(n)$	$O(n)$	$O(n)$
계수 정렬(Counting Sort)	$O(n)$	$O(n)$	$O(n)$