거품 정렬 (Bubble Sort)

버블정렬이란?

---

물에서 거품이 위로 올라가는 것처럼 큰 값이 뒤로 이동하는 방식이다. 그 다음에는 확정된 큰 값을 제외하고 나머지 중에서 큰값을 뒤로 보낸다.

버블정렬 과정

---

1. 배열의 가장 앞에서부터 서로 인접한 두 원소의 대소를 비교해서 큰 값을 뒤로 보낸다.
2. 그렇게 가장 큰 값을 뒤로 보내고 이미 정렬된 큰 값을 제외하고 다시 1~2번 과정을 반복한다.

버블정렬 코드

---

def bubbleSort(arr):
    for i in range(len(arr)):
        for j in range(1, len(arr) - i):
            if arr[j] < arr[j-1]:
                arr[j-1], arr[j] = arr[j], arr[j-1]
    return arr

print(bubbleSort([3, 2, 6, 8, 1]))

파이썬으로 작성하였다.

시간복잡도

---

처음 반복할때는 n번 반복하여서 최대 값을 뒤로 보내었고 그 값을 제외한 배열의 크기가 점점 줄어드니 n + (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2라서 O(N^2)의 시간복잡도를 갖는다. 거품정렬은 정렬 여부는 따지지 않고 무조건 2가지 원소를 비교하는 방식이라서 최선, 평균, 최악의 시간복잡도가 O(N^2)으로 동일하다.

공간복잡도

---

배열 내부에서 2가지의 원소를 비교, swap하는 방식이라서 공간 복잡도는 O(N)이다.

장점

---

• 구현이 직관적으로 잘 와닿는다.
• 주어진 배열 내부에서 위치를 바꾸는 방식이라서 추가로 메모리가 필요하지 않다.
  • 이러한 방식을 제자리정렬 (in-place sorting)이라고 한다.

단점

---

• 시간 복잡도가 O(N^2)이라는 것은 굉장히 안좋다는 뜻이다.