Swift3 ) Swift로 버블정렬(Bubble Sort)짜보기

ㅎㅎ버블정렬은 쉬우니 금방 해봅시다. 

그냥 C++코드랑 완전히 비슷해요.

다만 다른점이 있다면 Swift로 선택정렬짜보기!에서 했던것 처럼 swap하기전에 같은 위치가 아니라는 것을 확인해주면 됩니다.

C++코드 일단 볼게요.

버블정렬(Bubble Sort)

---

이건 C++로 짠 버블정렬 코드에요.

import UIKit

var arr = [3,10,9,7,5]
for i in 0..<arr.count{

    for j in 0..<arr.count-1{
        if arr[j]>arr[j+1]{
                swap(&arr[i],&arr[j+1])
            }
        }
    }
}
for i in 0..<arr.count{
    print(arr[i])
}

ㅎㅎ Swift코드입니다. 위 코드랑 매우매우 비슷하죠? 돌려보시면 정렬이 아주 잘 되는 것을 볼 수 있을거에요. 

자, 혹시 버블정렬을 조금 더 '빠르게'하는 법. 아시나요?

일단 이 방법을 알려면, 버블정렬의 특성을 아셔야 합니다. 

으음.. 일단 코드를 먼저 볼게요. 

import UIKit

var arr = [3,10,9,7,5]

var flag : Bool = false


for i in 0..<arr.count{

    flag=false

    for j in 0..<arr.count-1{

        if arr[j]>arr[j+1]

        {
            swap(&arr[j],&arr[j+1])

            flag=true

        }
    }

    if flag==false{

        break

    }

}

for i in 0..<arr.count{

    print(arr[i])

}

바로, flag로 반복을 줄여주는 것이죠.  

먼저 첫번째 for문이 시작되고, flag값을 false로 초기화 해주죠? 

그리고 두번째 for문안에서 만약 앞에 있는 값이 뒤에 있는 값보다 크면 값을 바꾸어주고,

flag를 true로 만들죠. 

이 소리는 한번이라도 두번째 for문안의 조건문 안에 들어가게 되면 flag는 true로 된다는 것입니다. 

만약 이 조건문에 안들어가게 되면 flag는?

네. 그대로 false겠죠. 그리고 두번째 for문이 끝나고 flag를 검사해줍니다. 

만약 flag가 그대로 false라면? for문을 종료해줍니다. 이는 두번째 for이 끝나고, 첫번째 for문 안에서 검사해주므로 첫번째 for문을 나가게 되고 정렬이 끝나게 됩니다. 

그럼 이런 질문을 할 수 있겠죠. 

"그래도 되나요??!" , "갑자기 for문을 멈추는데 다 정렬이 되나요?"

네. 됩니다!!

왜 이것이 가능할까요? 

먼저 제가 예전에 썼던 정렬 알고리즘 정리에 가셔서 버블정렬의 설명을 보고 와주세요.

간단하게 요약하자면, 버블정렬은 한 회전이 끝나면 배열안에서 가장 큰 값이 맨 뒤로 가게 됩니다.

정말 자명하죠? 인접한 값들과 계속 비교하면서 큰 값을 뒤로 계속 보내게 되면 결국엔 배열안에서

가장 큰 값이 맨 뒤로 가게 되겠죠. 

근데, 자 한번 봅시다. 

flag가 true가 안된다는 것은, 현재 내 위치에 있는 값보다 작은 것이 없다는 뜻이겠죠?

내 뒤에 있는 원소 모두가 일단 나보다 크다는 것입니다. 

그렇다면 비교를 더 진행할 필요가 있을까요? 

네. 없게 되겠죠.

이것은 기준을 세우고 비교하는 것이 아닌 인접한 원소들끼리 비교하므로, 가능해지게 되죠.

ㅎㅎㅎ

또한, 이러한 성질을 이용해서 시간을 더!! 줄일 수도 있답니다.

매 회마다 배열안에 가장 큰 값은 맨 뒤로 가게 됩니다. 

만약 9,8,7,6 이런배열이 있었다면,

첫번째 for문에서 9가 맨 뒤로 가게 되고, 그 다음 for문에서는 8, 그 다음은 7..이렇게 갑니다. 

즉, 매번 (두번째 for문에서) 끝까지 비교를 안해도 된다는 것이죠.

첫번째 for문의 i+1만큼 가장 큰 값이 뒤로 가기 때문에, 비교를 안해도 되게 됩니다.

즉 코드로 살펴보면,

import UIKit

var arr = [8,6,5,3,1,2,7,4]



var key : Int =  0

for i in 0..<arr.count{

    for j in 0..<arr.count-1-i{

        if(arr[j]>arr[j+1]){

            swap(&arr[j],&arr[j+1])

        }

    }

}

for i in 0..<arr.count{

    print(arr[i])

    

}

for j in 0..<arr.count-1-i

이부분! arr.count-1은 왜 하는지 아시죠? j+1이라는 인덱스에 접근할 것이기때문에 -1을 하지않으면 범위가 초과되어 런타임에러가 난답니다. 여기서 핵심은 -i인데요, 위에서 말했다시피 첫 회전에 배열안에 가장 큰 값이 가장 뒤로 가게 되고, 그 다음회전에 배열안에서 두번째로 큰 값이 뒤에서 첫번째자리에 위치하기 때문에 모든 회전에서 끝을 볼 필요가 없게됩니다. 끝에서부터 정렬이 완료된다고 생각하시면돼요. 정렬이 완료된 범위는 안봐도 되기 때문이죠 ㅎㅎ

자, 오늘 버블정렬을 Swift로도 짜보고 시간을 줄이는 두가지 방법에대해서 알아봤는데 어떠셨나요 ㅎㅎ

Swift정말 쉽지 않나요? 저도 계속 C문법이랑 헷갈리긴 하지만 ㅠㅠㅠ 열심히 연습해봐야겠어요!

아! 그리고 선택정렬때와 다르게, 왜 swap하는 문에서 인덱스가 같은지 검사 안해준 이유를 아세요?

검사를 안해줬는데 에러가 왜 안날까요 ㅎㅎ?

왜냐하면 같은 인덱스일리가 없다는것이 자명하기때문입니다. 

swap(&arr[j],&arr[j+1])

j와 j+1의 인덱스가 같아지는 상황이 있나요??네 없습니다.

그러니까 컴파일러는 오류를 내지 않게 되는 거죠!!

그냥 if문으로 감싸줘도 되긴하지만, 다른 케이스도 보여드리고 싶어서 일부로 뺐어요XD

결론 : 엑스코드는 똑똑하다.

도움이 되었으면 좋겠어요!XD