버블 정렬
집합 안에서 가장 큰 값이 뒤(오른쪽)로 이동하는 방식입니다. 값이 클수록 풍선처럼 높이(뒤쪽으로) 올라간다고 생각해주시면 됩니다.
원리
⓵ 앞(왼쪽)에서부터 인접한 두 수를 비교합니다.
⓶ 앞(왼쪽) 원소가 뒤(오른쪽) 원소보다 크면 자리를 변경합니다.
⓷ 기준 원소를 다음 원소로 옮겨서 두 수 비교를 반복합니다.
⓸ 최댓값(오른쪽으로 다 옮겨진 원소)을 제외하고 위의 과정을 반복합니다.
*정렬할 원소가 없을 때까지 반복
예시
버블 정렬을 그림으로 나타내봤습니다. 주어진 배열 [9, 7, 2, 13, 10] 를 버블 정렬을 사용해서 정렬해보겠습니다.
버블 정렬 영상
만약, 앞 원소가 뒤 원소보다 크다면 두 숫자의 자리를 변경합니다. 뒤 원소가 크다면 자리를 바꾸지 않습니다.
최댓값이 된 원소는 정렬이 필요하지 않기 때문에 더이상 두 수 비교를 진행하지 않습니다.
BubbleSort.swift
저는 버블 정렬 코드를 이렇게 구현해봤습니다. 밑에서 자세하게 설명해보겠습니다.
func bubbleSort(arr: [Int]) {
var arr = arr
for i in 0..<arr.count - 1 {
for j in 0..<arr.count - i - 1 {
if arr[j] > arr[j+1] { arr.swapAt(j, j+1) }
}
}
}
Swift
복사
⓵ 0개부터 전체 배열에서 2개의 원소를 뺀 값까지 for문을 돌릴겁니다. i로 인해서 점점 비교할 원소의 수가 줄어들겁니다. i가 하나씩 늘수록 ⓶에서 비교해야할 원소가 줄어듭니다. 줄어드는 원소의 수는 뒷(오른)쪽에 쌓이는 최댓값을 의미합니다. 최댓값이 늘어나면서 두 수 비교를 해야하는 수가 줄어드는거죠.
⓶ 전체 중에서 최댓값을 제외하고 두 수 비교를 진행해야하는 인덱스들입니다. 전체 배열 수(arr.count)에서 최댓값의 수(i)를 제외하고나서도 -1를 하는 이유는 최댓값 비교를 n과 n+1한 값을 비교하기 때문입니다. n+1한 값이 out of range가 되지 않으려면 맨 끝 값에서 -1한 값까지만 for문을 돌려야 하기 때문이죠.
⓷ 2에서 두 수 비교를 진행하는 인덱스를 설정해주었으니 두 수 비교를 진행합니다. 만약 앞 원소가 뒤 원소보다 크다면 두 원소를 swap 해줍니다. 저번 [알고리즘] 선택 정렬(Selection sort) 에서 봤던 swapAt 메소드를 사용해줬어요.
func bubbleSort(arr: [Int]) {
var arr = arr
for i in 0..<arr.count - 1 { // ⓵
for j in 0..<arr.count - i - 1 { // ⓶
if arr[j] > arr[j+1] { arr.swapAt(j, j+1) } // ⓷
}
}
}
Swift
복사
시간 복잡도
위의 코드에서 볼 수 있듯, 버블 정렬의 시간 복잡도는 입니다. 선택 정렬과 동일하네요.
func bubbleSort(arr: [Int]) {
var arr = arr
for i in 0..<arr.count - 1 { // ⓵
for j in 0..<arr.count - i - 1 { // ⓶
if arr[j] > arr[j+1] { arr.swapAt(j, j+1) }
}
}
}
Swift
복사
⓵ 0부터 n-1까지 원소를 한 개씩 탐색하기 때문에,
⓶ 0부터 n-2까지 원소를 한 개씩 탐색하기 때문에,
● 결론적으로, 가 걸리게 됩니다. 선택 정렬처럼 좋은 성능의 알고리즘은 아닙니다.
저번 선택 정렬처럼 버블 정렬이 어느정도의 시간이 걸리는지 궁금해졌습니다. 성능을 확인하기 위해서, 저는 10000부터 1까지 거꾸로 들어있는 배열을 하나 만들었습니다.
var arr: [Int] = []
stride(from: 10000, through: 1, by: -1).forEach {
arr.append($0)
}
Swift
복사
그리고 버블 정렬을 사용해서 정렬을 진행했습니다.
•
버블 정렬
•
•
sort()
저번에 작성했던 선택 정렬보다 5초정도 더 걸렸네요. 둘 다 좋지 않은 알고리즘인건 맞는것 같군요..
+⍺
선택 정렬처럼 버블 정렬도 완전히 정렬된 배열을 넣어보았습니다. 선택 정렬과 다른 점은 버블 정렬은 정렬이 잘 되어 있다면 swap 메소드를 사용하지 않는다는 점입니다. 앞 원소가 뒤 원소보다 클 일이 없으니깐요.
최악의 정렬 상태보다는 최선일 때 5초정도 빠르네요. 하지만 최악이긴 마찬가지네요..
코드는 깃허브에 올려뒀습니다!
