요약 설명

이름의 유래 :

정렬 과정에서의 원소 이동이 거품이 수면 위로 올라오는 것과 유사한 모습을 보인 점에서 착안하였다고 합니다.

요약:

Bubble Sort는 기본적으로 Selection Sort와 유사한 알고리즘입니다.

본 알고리즘은 아래와 같은 과정에 의해 정렬을 실행하는 알고리즘입니다.

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬

알고리즘 설명

1. 첫 번째 반복을 통해 첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소, …. 마지막 이전 원소와 마지막 원소와의 비교(인접한 원소 간의 비교)를 통하여 조건을 통해 교환(swap) 과정을 행합니다.
2. 첫 번째 반복이 종료되면 리스트 내의 가장 큰 원소가 맨 뒤로 이동하기 때문에 두 번째 반복에서는 마지막 원소를 제외하여 첫 번재 반복과 동일한 과정을 거칩니다.
3. 이러한 반복을 통해 순차적으로 큰 원소들은 반복에서 제외되며 마지막 반복까지 행하게 되면 오름차순으로 데이터가 정렬되게 됩니다.

Source Code(Python)

def bubble_sort(arr):
  	# arr 내의 원소의 수 만큼 반복
    for i in range(len(arr) - 1, 0, -1):
      	# 마지막 원소를 i의 값의 감소를 통해 제외하나가며 비교
        for j in range(i):
          	# 가장 큰 원소를 맨 뒤로 이동시키기 위한 비교(Swap)
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

시간 복잡도

각 반복별로 n-1, n-2, n-3, …. , 2, 1 회 반복이 이루어지기 때문에 n(n-1)/2,

즉, O(n^2)의 시간 복잡도를 가지게 됩니다.

공간 복잡도

주어진 배열(같은 메모리 공간) 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 입니다.

장점

• 구현이 용이하며, 코드가 직관적입니다.
• 2020주어진 메모리 공간 내에서 수행되기 때문에 공간 효율성이 뛰어납니다.
• 안정 정렬(stable sort)에 속하는 정렬 알고리즘입니다.

단점

• 최악, 최선, 평균 시간복잡도가 모두 O(n^2)으로 비효율적인 편에 속합니다.
• 각 반복 내에서 잦은 원소 간 교환(Swap)이 발생합니다.