버블 정렬(Bubble Sort)

버블 정렬

0. 버블 정렬(Bubble Sort)이란?

서로 인접한 두 원소의 선후관계를 확인하여 정렬하는 알고리즘 방법

1. 버블 정렬(Bubble Sort) 알고리즘 예제

[5, 1, 9, 7, 2, 3]의 배열

• 1회차
  5와 1을 비교하여 작은 값을 앞으로 이동
  입력값: 5 1 9 7 2 3
  출력값: 1 5 9 7 2 3

• 2회차
  5와 9를 비교하여 작은 값을 앞으로 이동
  입력값: 1 5 9 7 2 3
  출력값: 1 5 9 7 2 3

• 3회차
  9와 7을 비교하여 작은 값을 앞으로 이동
  입력값: 1 5 9 7 2 3
  출력값: 1 5 7 9 2 3

• 4회차
  9와 2를 비교하여 작은 값을 앞으로 이동
  입력값: 1 5 7 9 2 3
  출력값: 1 5 7 2 9 3

• 4회차
  9와 3을 비교하여 작은 값을 앞으로 이동
  입력값: 1 5 7 2 9 3
  출력값: 1 5 7 2 3 9

• 최종
  1 5 7 2 3 9로 정렬을 완성

---

# Bubble Sort
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Bubble Sort - pseudo code
for i ← 0 to n-i-1 do{
    for j ← 0 to n-i-2 do{
        if arr[j] > arr[j+1]
    }
    Swap (arr[j], arr[j+1])
}

2. 버블 정렬(bubble sort)의 특징

• 장점
  • 구현이 매우 간단하다.
• 단점
  • 순서에 맞지 앉은 요소를 인접한 요소와 교환한다.
  • 배열에서 모든 배열과 비교하여 계산한다.
  • 최종 정렬 위치에 있더라도 교환되는 경우가 발생한다.
  • 단순함에도 불구하고 이동 작업이 복잡하기때문에 잘 사용하지 않는다.

---

3. 버블 정렬(Bubble sort)의 시간복잡도

• 비교 횟수

  • 최상, 최악, 평균이 모두 일정하다.

• 교환 횟수

  • 정렬이 역순으로 되어 있는 경우(최악의 경우) 한 번 교환을 위해 3번의 움직임(SWAP)이 필요하다.
  • 정렬이 정렬되어져 있는 경우(최상의 경우) 움직임이 필요하지 않다.

• T(N) = O(N²)

References

Blog