swift 알고리즘 - 버블정렬 쉽게 이해하기

swift 알고리즘 - 버블정렬 쉽게 이해하기

 

버블 정렬이란

버블정렬은 서로 인접한 두 요소를 비교하면서 정렬해 나가는 알고리즘입니다.

인접한 두 요소를 비교해서 크기가 순서대로 정렬이 안되어 있다고 판단되면 크기가 큰 데이터를 오른쪽으로 위치시키면서 정렬을 진행하고, 가장 큰 데이터가 가장 뒤로 가게 됩니다.

 

예를 들어 [7,4,5,1,3]이라는 정렬되지 않은 배열이 주어졌다고 가정해 보겠습니다.

 

여기서는 무엇과 무엇을 비교해야 할까요?

 

먼저 대상이 되는 숫자를 정해야 합니다. 

위 배열에서는 첫번째 대상 숫자는 7입니다.

(대상숫자는 비교의 시작이 되는 숫자라고 생각하시면됩니다.)

 

비교의 시작이 되는 숫자 = 대상숫자

 

그러면 7과 무엇을 비교해야 할까요?

 

버블정렬의 정의를 보면 서로 인접한 숫자와 비교를해서 정렬을 해준다고 되어 있습니다.

 

그럼 7의 인접숫자가 비교 숫자가 됩니다.

 

[7,4,5,1,3] 에서 7을 대상 숫자로 지정해봅니다. 

 

[1회전]

대상숫자(비교의 시작이되는숫자) : 7

 

인접숫자와 비교를 하나씩 진행합니다.

 

7 과 4를 비교 = > 7이 더 크므로 위치 변경!

결과 : 4,7,5,1,3

 

이번엔 7의 인접숫자는 5임

7과 5를 비교 = > 7이 더 크므로 위치 변경!

결과 4,5,7,1,3

 

이번에 7의 인접숫자는 1임

7과 1을 비교 = > 7이 더 크므로 위치 변경!

결과 4,5,1,7,3

 

이번에는 7의 인접숫자는 3임

7과 3을 비교 = > 7이 더 크므로 위치 변경!

결과 4,5,1,3,7

(7 정렬완료, [1회전 종료])

 

1회전이 종료되었습니다.

1회전에서는 대상 숫자가 7이었고 7의 인접숫자들과 비교를 총 4번 진행을 했습니다.

 

1회전의 결과는 한마디로 배열에서 가장 큰수가 제일 끝으로 정렬이 되었다는 것입니다.

 

[2회전]

그럼 2회전에서는 제일 앞에 있는 숫자 4가 대상 숫자(비교의 시작이되는 숫자)가 되겠죠?

그럼 4의 인접숫자와 비교를 몇번 진행할까요? 정답은 3번입니다.

왜냐면 4,5,1,3,7

이 배열에서 7은 이미 정렬이 끝났기 때문에 다시 비교를 하지 않습니다.

 

그럼 남은 숫자들은 5, 1, 3 이기 때문에 비교는 3번 진행하게 됩니다.

 

4 와 5를 비교 = > 4가 더 작으므로 위치 변경 안함!!!! 

결과 : 4,5,1,3,7

 

5와 1을 비교 = > 5가 더 크므로 위치 변경!

결과 4,1,5,3,7

 

5와 3을 비교 = > 5가 더 크므로 위치 변경!

결과 4,1,3,5,7

 

[2회전]의 결과는

4,1,3,5,7 이 됩니다.

 

2회전의 결과는 한마디로 배열에서 두번째로 큰 수가 정렬이 되었다는 것입니다.

 

그럼 여기서 배열안의 요소들을 버블 정렬의 정의대로 자동으로 자기들끼리 비교를 진행하게 하려면 어떤 프로그래밍 문법을 써야 할까요?

 

반복문..이겠죠? 자동으로..니깐 반복문 이 자연스럽게 떠오르면됩니다.

 

그럼 위에서 [1회전] , [2회전] .. 이런 n 회전을 반복문을 통해서 처리 한다고 하면 이 반복문은 총 몇번 반복을 하면될까요?

 

[7,4,5,1,3] 배열 안에는 총 5개의 숫자들이 있습니다. 그럼 5번 반복하면 될까요? 그렇게 보일 수 있는데 하나씩 돌려보면 7부터 1까지 4번만 반복해도 됩니다. 

 

왜냐면 비교는 숫자 2개를 가지고 진행을 하기 때문에 7부터 1까지를 대상숫자로 정해서 4회전으로 정렬을 하면 나머지 제일 끝에있는 숫자 3은 자동으로 정렬이 되어(?) 버립니다.

 

이 반복문을 바깥쪽 반복문이라고 하겠습니다.

 

[바깥쪽 반복문]

바깥쪽 반복문은 배열의 개수 - 1 만큼 반복을 합니다.

 

[안쪽 반복문]

그럼 n회전 내에서 대상 숫자와 인접한 숫자를 계속 반복해 나가는데 위에서 보았듯이 [7,4,5,1,3] 배열에서 

1회전때는 최대 4번 반복

2회전때는 최대 3번...

4회전때는 최대 1번...

이런식으로 인접숫자를 비교합니다.

 

즉, 안쪽 반복문은 배열의 개수 -1 번 부터 시작해서 회전이 1씩 증가할때 마다 반복 횟수가 - 1 씩 감소하게 됩니다.

 

위에서 작성한 시나리오대로 [바깥쪽 반복문] 과 [안쪽 반복문] 을 코드로 작성해보겠습니다.

 

[바깥쪽 반복문] 역할 :  대상숫자를 스캔합니다. 

[안쪽 반복문] 역할 : 대상숫자와 인접숫자를 비교하면서 정렬합니다.

 

var arr = [7,4,5,1,3]

var outterForLength = arr.count - 1


//[바깥쪽 반복문] : 대상숫자 스캔
while(0 < outterForLength){
    
    print("#바깥쪽 반복문 : \(outterForLength)")

    // 안쪽 반복문 횟수
    var innerLength = outterForLength
    
    // [안쪽 반복문] : 대상숫자와 인접숫자 비교
    while(0 < innerLength){
        
        print("-안쪽 반복문 : \(innerLength)")
        innerLength -= 1

    }// inner while - end
    
    outterForLength -= 1
    print("")
}

 

출력

출력을 해보면 바깥쪽 반복문이 1번씩 돌 때 마다 안쪽 반복문은 4번, 3번, 2번 .. 이런식으로 - 1 씩 반복을 진행하는것을 볼 수 있습니다.

 

#바깥쪽 반복문 : 4
-안쪽 반복문 : 4
-안쪽 반복문 : 3
-안쪽 반복문 : 2
-안쪽 반복문 : 1

#바깥쪽 반복문 : 3
-안쪽 반복문 : 3
-안쪽 반복문 : 2
-안쪽 반복문 : 1

#바깥쪽 반복문 : 2
-안쪽 반복문 : 2
-안쪽 반복문 : 1

#바깥쪽 반복문 : 1
-안쪽 반복문 : 1

 

대상숫자와 비교할 숫자 추출 후 비교와 교환 진행

이제 대상숫자를 뽑아 내고 비교할 숫자를 추출해서 서로 비교하고 교환시키는 로직을 작성해 보겠습니다.

안쪽 반복문 바로 위에 var idx = 0 변수를 작성해줍니다.

왜냐면 안쪽 반복문은 배열의 제일 첫번째 즉 0번째 인덱스에 있는 숫자와 idx+1 에 위치한 숫자를 비교할 것이기 때문입니다.

안쪽 반복문이 끝날때마다 idx는 1씩 증가합니다. 왜냐면 우측으로 이동 하면서 계속 인접 숫자들을 비교해야 하기 때문입니다.

 

비교는 arr 배열에서 앞의 숫자 arr[idx]가 뒤의 숫자 arr[idx+1] 보다 크면 서로 위치를 변경해서 값을 넣어주는 로직을 작성해주면 되겠죠?

        //대상 숫자
        let front = arr[idx]
        //비교 숫자
        let second = arr[idx+1]
        
        // 대상 숫자가 더 크면 교환
        if front > second {
            arr[idx] = second
            arr[idx+1] = front
        }

 

위의 전체적인 내용을 토대로 버블 정렬 코드를 swift로 작성하면 아래와 같습니다.

코드

var arr = [7,4,5,1,3]
var outterForLength = arr.count - 1

while(0 < outterForLength){
    
    // 안쪽 반복문
    var innerLength = outterForLength
    
    //안쪽 반복문에서 0번째 부터 0+1번째 숫자 비교 진행을 하기 때문
    var idx = 0
    while(0 < innerLength){
        
        //대상 숫자
        let front = arr[idx]
        //비교 숫자
        let second = arr[idx+1]
        
        // 대상 숫자가 더 크면 교환
        if front > second {
            arr[idx] = second
            arr[idx+1] = front
        }
    
        innerLength -= 1
        //다음 오른쪽 숫자로 이동
        idx += 1
    }
    
    outterForLength -= 1
}

print("arr:\(arr)")

 

출력

arr:[1, 3, 4, 5, 7]