거품 정렬(Bubble Sort)

개념

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다.
• 선택 정렬과 기본 개념이 유사하다.
• 거품이 물위로 떠오르는 모습과 흡사하다 하여 거품정렬

구체적인 개념

• 첫 번째와 두 번째, 두 번째와 세 번째, 세 번째와 네 번째 ... 이런식으로 (마지막-1), 마지막을 비교하고 교환하면서 정렬함
• 1회전 수행하고 나면 가장 큰 자료가 맨 뒤로 이동
• 2회전에서는 맨 끝에 있는 자료 제외
• 3회전에서는 끝에서 두 번째까지 제외
• 이런식으로 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.
  
  

예시

배열에 7, 4, 5, 1, 3이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

코드

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

arr = [7,4,5,1,3]
bubbleSort(arr, len(arr))
print(arr)

특징

• 장점
  - 구현이 매우 간단하다.
• 단점
  - 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
  - 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  - 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

시간복잡도

비교 횟수

• 최상, 평균, 최악 모두 일정
• n-1, n-2, … , 2, 1 번 = n(n-1)/2

교환 횟수

• 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
• 입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.

T(n) = O(n^2)

---

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