버블 정렬(Bubble Sort)

1. 버블 정렬이란?

 
버블 정렬은 인접한 두 데이터를 비교해서
앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 두 데이터의 자리를 바꿔서 정렬하는 방식!
 
[5, 6, 3, 10, 7] 이라는 배열이 있을 때를 가정.
 
1. 5와 6 비교 (뒤에 있는 데이터가 크니까 자리 변경 없음)
2. 6과 3 비교 (두 데이터 자리 교환)

---

 

이렇게 스캔을 하다보면 끝까지 정렬을 했을 때
[5, 3, 6, 7, 10]이 1차적으로 나오게 됨.
 
???
정렬이 안됐는데?
 
맞음. 모두 정렬이 될 때 까지 똑같은 행위를 반복함 ㅎㅎ
여기서 2차 시작을 하게되면 처음 5와 3만 바꾸면 정렬이 완료!
[3, 5, 6, 7, 10]
 
이렇게 반복을 했을 때 정렬이 완료되면 끝!
 

2. 코드로 구현

1. 배열 요소의 갯수 - 1 만큼 반복하면 스캔 작업 한 번이 완료된다.
2. 스캔을 한 번 하게되면 무조건 가장 마지막 요소는 가장 큰 값이다.
3. 스캔을 할 때 마다 끝에서부터 가장 큰 요소로 정렬되니까 탐색 횟수에 따라 탐색해야 하는 요소의 갯수가 줄어든다.
4. 배열의 요소가 5개 라고 하면, 스캔을 최대 4회 하게 되면 0번 인덱스는 무조건 가장 작은 값이다. (count - 1)
 

func bubbleSort(array: inout [Int]) {
    for i in 0..<(array.count - 1) { // 스캔 반복 for문
        var isSwap = false
        for j in 0..<(array.count - i - 1) { // 인접 인덱스 비교 for문
            if array[j] > array[j + 1] {
                array.swapAt(j, j + 1)
                isSwap = true
            }
        }
        if isSwap == false { return }
    }
}

 
isSwap은 input으로 들어온 배열이 애초에 정렬이 되어있으면 isSwap이 true가 되지 않기 때문에!
 

3. 시간 복잡도

반복문 안에 반복문이 도는 구조(2중 for문)이기 때문에
O(n^2)이며, 효율적이지 못한 정렬 알고리즘이다!