Swift) 버블 정렬 해보기 (Bubble Sort)

Swift) 버블 정렬 해보기 (Bubble Sort)

 

알고리즘에서 버블 정렬을 swift를 사용해서 구현해보겠습니다.

 

 

버블정렬이란?

 

정렬을 가장 간단하게 구현하는 방법중에서 하나로,

 

인접한 두 데이터를 비교한 후,

 

앞에 있는 데이터가 뒤에 데이터보다 값이 크다면 자리를 바꿔주는것입니다.

 

예를 들어서 표현하자면 아래와 같은 데이터가 있을 때 한번의 스캔으로 한번 모든 자리를 정렬시켜줍니다.

 

 

1). 4 > 3 -> 순서 변경

2) 4 < 9  -> 순서 변경 x

3) 9 > 1 -> 순서 변경

4) 9 > 6 -> 순서 변경

5) 1 ~ 4번을 걸쳐 한번 스캔

 

 

 

자 이렇게 한번의 스캔이 완료됐는데 아직 정렬이 이쁘게 되지 않았습니다.

 

저희가 원하는 이쁜 데이터 정렬은

이렇게 되어주어야 하는데요

 

왜냐하면 버블정렬로 정렬할 때에는 배열의 요소의 수를 N이라고 한다면

 

최대 N - 1 만큼 스캔을 진행해야 모든 배열이 완벽하게 정렬됩니다.

 

왜일까요?

 

위에 1~4 번과정을 다시 한번 보시면 이해할 수 있습니다.

 

배열에서 3,4,9,1,6 중에서 9가 가장 큰 수 입니다.

 

따라서 9는 매번 인접한 요소와 값을 비교할 때마다 크기 때문에 항상 뒷자리로 밀려날 수 밖에 없습니다.

 

그 결과 가장 큰 수인 9가 가장 마지막 요소에 위치하게 되었습니다.

 

이게 첫번째 스캔에서의 결과입니다.

 

그럼 두번째 스캔하게되면 두번째로 큰 수인 6이 마지막에서 두번째 요소로 들어가게되고,

 

이런 과정을 반복하여 N - 1번의 스캔과정이 필요한것입니다.

 

물론 지금 예제에서는 첫번째 스캔에서 6이 4번째 요소에 위치해있기 때문에

 

3번의 스캔과정만 걸쳐도 됩니다.

 

이런 루프를 도는 과정을 버블정렬이라고 합니다.

 

이러한 버블정렬은 정말 기본적인 정렬 방법이지만 요소갯수만큼 반복문이 계속 돌기 때문에

 

시간복잡도가 O(n^2)로 상당히 느린 정렬 방법입니다.

 

 

코드로 구현하기

 

func bubbleSort(_ array: inout [Int]) {
    for index1 in 0..<(array.count - 1) {  // 스캔 반복
        var isSwap = false  // 배열이 다 정렬돼었는지 알려줘서 무의미한 반복을 줄임
        for index2 in 0..<((array.count - index1) - 1) { 
            if array[index2] > array[index2 + 1] {
               array.swapAt(index2, (index2 + 1))
                isSwap = true
            }
        }
        if isSwap == false { return }
    }
}