알고리즘 – 버블정렬 (Bubble Sort)

• 버블정렬(Bubble Sort) 이란?
  • 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘
    • 비교 정렬에 속함
  • 버블 정렬 특징
    • 선택 정렬과 마찬가지로 구현이 쉬움
    • 잦은 비교와 교환으로 성능이 나쁨
  • 버블 정렬 알고리즘의 시간복잡도
    • 최악, 최선, 평균 – O(N²)
    • 참고 – 각 정렬 알고리즘의 시간복잡도

• 예제 – 버블 정렬 (오름차순)

# Python Code

arr = [3,1,6,0,1,9,4]
N = len(arr)

for _ in range(N):
    for i in range(N-1):
        if arr[i] > arr[i+1]:
            temp = arr[i]
            arr[i] = arr[i+1]
            arr[i+1] = temp

print(arr)
# [0, 1, 1, 3, 4, 6, 9]

• 과정 – 오름차순

첫 번째 배열부터 마지막 배열까지 자신의 인접한 배열과 순차적으로 비교를 통해 교환하여 정렬합니다.

현재까지 진행된 1번째 ~ 마지막 배열 비교를 배열을 수만큼 반복 작업을 하게 되면 아래와 같은 정렬이 완성됩니다.

이상으로 버블 정렬에 대한 설명을 마칩니다! 😀