[알고리즘] 버블정렬

버블정렬(Bubble sort)

• 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘

설명	0	1	2	3	4	-
ex)	5	2	4	3	1
0자리의 5가 1자리의 2보다 크기 때문에 자리를 바꾼다	2	5	4	3	1
1자리의 5가 2자리의 4보다 크기 때문에 자리를 바꾼다	2	4	5	3	1
2자리의 5가 3자리의 3보다 크기 때문에 자리를 바꾼다	2	4	3	5	1
3자리의 5가 4자리의 1보다 크기 때문에 자리를 바꾼다	2	4	3	1	5
가장 큰 5가 맨 뒤에 온다	2	4	3	1	5	실행횟수 = 4번
다시 반복	-	-	-	-	-	반복횟수 = 1번
0자리의 2가 1자리의 4보다 크지 않기 때문에 자리를 바꾸지 않는다	2	4	3	1	5
1자리의 4가 2자리의 3보다 크기 때문에 자리를 바꾼다	2	3	4	1	5
2자리의 4가 3자리의 1보다 크기 때문에 자리를 바꾼다	2	3	1	4	5
3자리의 4와 4자리의 5는 비교할 필요가 없다	2	3	1	4	5	실행횟수 = 3번
다시 반복	-	-	-	-	-	반복횟수 = 2번
0자리의 2가 1자리의 3보다 크지 않기 때문에 자리를 바꾸지 않는다	2	3	1	4	5
1자리의 3이 2자리의 1보다 크기 때문에 자리를 바꾼다	2	1	3	4	5
2자리의 3과 3자리의 4는 비교할 필요가 없다	2	1	3	4	5	실행횟수 = 2번
다시 반복	-	-	-	-	-	반복횟수 = 3번
0자리의 2가 1자리의 1보다 크기 때문에 자리를 바꾼다	1	2	3	4	5
1자리의 2와 2자리의 3은 비교할 필요가 없다	1	2	3	4	5	실행횟수 = 1번
끝	1	2	3	4	5	반복횟수 = 4번

• 배열의 길이 = 5
• 실행횟수 = 4 -> 3 -> 2 -> 1
• 반복횟수 = 4

일반화

• 배열의 길이 = n
• 실행횟수 = n-1 -> n-2 -> n-3 -> ... -> 1
• 반복횟수 = n-1

특징

• 첫번째 반복에서 한번도 자리가 바뀌지 않았다면 모두 정렬되어있다는 의미
• swap이란 변수로 자리가 바꼈는지 확인

구현

1. for num in range(len(data)) 반복
2. swap = 0 (교환이 되었는지를 확인하는 변수를 두자)
3. 반복문 안에서, for index in range(len(data) - num - 1) n - 1번 반복해야 하므로
4. 반복문안의 반복문 안에서,
   if data[index] > data[index + 1] 이면
   data[index], data[index + 1] = data[index + 1], data[index]
swap += 1
5. 반복문 안에서, if swap == False 이면, break 끝

---

Python

def bubble_sort(data):
    for i in range(len(data)-1):
        swap = False
        for j in range(len(data)-i-1):
            if data[j] > data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                swap = True
        if swap == False:
            break
    return data

Swift

import Foundation

func bubbleSort(_ data: [Int]) -> [Int] {
    var data = data
    let lengthData = data.count
    for i in 0..<lengthData - 1 {
        var swap = false
        for j in 0..<lengthData - i - 1 {
            if data[j] > data[j+1] {
                data.swapAt(j, j+1)
                swap = true
            }
        }
        if swap == false {
            break
        }
    }

    return data
}

시간복잡도

• 반복문이 2개이므로 $O(n^2)$
  • 최악의 경우, ${n(n-1)\over 2}$
• 완전 정렬이 되어 있는 상태라면 최선의 경우, $O(n)$