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

 

 

 

안녕하세요 :) 소들입니다!!!!

오늘은 알고리즘 중에서 버블 정렬을 Swift로 구현해보려고 해요!
제가 알고리즘을 이제 막 시작해서 공부 하는데,

 

알고리즘을 공부하기 위해선

 

일단 연습장과 노트를 꺼내들고!!! 문제를 분석한 후에!!

간단한 경우부터 복잡한 경우까지 연습장에 써보고!!

어떤 알고리즘을 쓰는지 좋은지 판단 후에!!

코드로 옮겨서 테스트 해라!!

 

라고 하더라고요..?

전 지금까지 머리로 상상하면서 코드로만 풀었고요..?

따라서 이번엔 가장 어쩌면 기초고 쉬운 버블 정렬을

어떻게 접근해서 코드를 짜야하는지 이곳을 연습장 삼아 적어보려고 해요 :)

 

버블정렬, 선택정렬, 삽입정렬은 쉬우니 후딱 해치웁시다!!

모든 포스팅은 편의 말투로 합니다~!!

 

 

 

 

1. 버블 정렬이 모야?

 

버블 정렬은 정렬을 하기 위한 방법 중 하나임!

근데 정렬을 할 때 어떤 방식으로 할지 방법이 되게 많은데..!

그중 가장 간단하게 구현할 수 있고 쉬운 알고리즘임 :)

뭐 그만큼 시간복잡도가 크겠지만, 이는 마지막에 보겠음

 

일단 버블 정렬의 방식은

 

① 두 인접한 데이터를 비교한다

② 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 둘의 자리를 바꿔준다

 

자 이게 끗임

두 인접한 데이터가 무슨 말인고 할 수 있으니 그림으로 보여주겠음

 

 

 

 

엥 정렬 안됐는데여? 맞음ㅎ

한 번의 스캔으로 정렬이 안 되면,

배열 전체가 정렬될 때까지 스캔을 반복하는 것이 버블 정렬임!

 

 

 

 

그럼 이제 이 그림을 가지고 어떻게 코드를 구현할 것인지

생각을 해볼 것이셈

 

 

 

 

2. 구현 전 생각 해보기

 

첫 번째로, 스캔 방법에 대해서 생각해 볼 것임!

인접 데이터를 비교하고 swap하는 작업은, 하나의 배열에서 몇 번 반복해야 끝나는가?

에 대해 생각을 해보는 것임.

 

배열 요소가 3개인 [4, 10, 2]란 배열과,

배열의 요소가 4개인 [4, 10, 2, 1] 이란 배열로 예를 보겠음

 

	[4, 10, 2]	[4, 10, 2, 1]
1단계	[4, 10, 2]	[4, 10, 2, 1]
2단계	[4, 2, 10]	[4, 2, 10, 1]
3단계		[4, 2, 1, 10]

 

 

배열의 요소가 3개일 경우 2번의 작업으로,

배열의 요소가 4개일 경우엔 3번의 작업으로 모든 요소의 인접 데이터 비교 및 swap이 가능함! 

 

아하! 인접 데이터끼리 비교하며 swap하는 작업 (스캔 작업)은

총 (탐색하는 요소의 갯수 - 1) 만큼 진행하면 끝나는구나! 라는 것을 캐치해야 함

 

근데 배열에 대한 한 번의 스캔 작업은 끝났음

근데 결과를 보면 [4, 2, 10]과 [4, 2, 1, 10]으로 아직 정렬되지 않음..!!

 

맞음! 위에서도 말했듯, 버블 정렬은 위 스캔 작업을 전체가 정렬될 때까지 계속 반복해야 함..!

그럼 몇 번 반복 해야하지?에 대해 이제 생각해보는 것임

 

.

.

 

자 이제 두 번째로, 

스캔 작업을 몇 번 반복해야 배열 전체가 정렬이 될까?

에 대해 생각해 보는 것임

 

	[4, 10, 2]	[4, 10, 2, 1]
1번째 스캔	[4, 2, 10]	[4, 2, 1, 10]
2번째 스캔	[2, 4, 10]	[2, 1, 4, 10]
3번째 스캔		[1, 2, 4, 10]

 

 

배열의 요소가 3개일 경우 2번의 스캔으로,

배열의 요소가 4개일 경우엔 3번의 스캔으로 배열 전체 정렬이 가능함! 

 

왜냐??

스캔 작업을 하면 할 수록,

가장 큰 수부터(맨 마지막부터) 하나씩 정렬이 된단 것을 위 표에서 볼 수 있음

그말인즉, 1번 스캔하면 가장 마지막 요소는 가장 큰 값으로 정렬되었단 것이고,

2번 스캔하면 마지막에서 2번째 요소는 2번째 큰 값으로 정렬되었단 것임!

 

정리하면,

스캔 작업을 한 번 할 때마다 큰 값부터 하나씩 정렬될 테니,

스캔 작업을 최대 (배열 요소의 갯수 - 1) 만큼 진행하면 전체 배열이 정렬되는 것임

(count에서 - 1을 하는 이유는, 만약 10개 요소중 9개를 큰 값부터 정렬하면

나머지 1개는 가장 작은 값으로, 자동으로 0번 index에 들어있게 되어 있을테니!)

 

또한, 스캔 작업의 실행 횟수에 따라,

스캔 작업 시 탐색하는 요소의 수가 줄어든다 까지 이해해야 함

1번 스캔하면 맨 마지막 인덱스는 정렬 됐으니 탐색할 필요 없고,

2번 스캔하면 맨 마지막에서 2번째 인덱스부턴 정렬 됐으니 탐색할 필요 없음!

 

 

자 여기까지 이해했다면!!

그럼 이제 버블 정렬에 대한 조건을 모두 이해한 것임 :) 코드로 짜보자!

 

 

 

 

3. 코드로 구현해보기

 

 

func bubbleSort(_ array: inout [Int]) {
    for index1 in 0..<(array.count - 1) {                // 스캔 작업 반복
        var isSwap = false
        for index2 in 0..<((array.count - index1) - 1) { // 스캔 작업(인접 인덱스 비교 및 swap 반복) : (탐색하려는 요소의 갯수) - 1 => 탐색하려는 요소의 갯수는 스캔 횟수에 따라 차감됨(스캔 횟수만큼 정렬되어 있을테니)
            if array[index2] > array[index2 + 1] {
               array.swapAt(index2, (index2 + 1))
                isSwap = true
            }
        }
        if isSwap == false { return }
    }
}

 

 

우리가 위에서 생각한 것을 그대로 코드로 구현한 것 뿐임!

Swift에선 swap이란 메서드를 제공해서 쉽게 구현 가능함 :)

 

근데 isSwap은 뭔ㄷㅔ 갑툭튀?

자 만약 다음과 같이 이미 정렬된 배열을 정렬하려고 함

 

 

 

 

이 경우 스캔 작업 때, 아무런 swap도 일어나지 않음!!

왜냐?? 이미 정렬되어 있어서, 내 이전 index가 나보다 클 일이 없거든..!

 

따라서 스캔 작업 때,

단 한번도 swap이 일어나지 않았다는 말인 즉, 

모든 요소가 이미 정렬되어 있다!! 란 뜻임 :)

 

따라서 이땐, 더 이상의 작업은 해주지 않고 정렬을 끝내버리면 되는 것임!

 

 

 

 

4. 버블 정렬의 시간 복잡도

 

입력 값 n은 배열의 요소 갯수로 볼 때,

요소 갯수만큼 도는 반복문 안에,

요소 갯수( - 상수)만큼 도는 반복문이 돌기 때문에

 

O(n^2)

 

으로,

구현이 쉽고 간단한 장점이 있지만, 느린 알고리즘임..!

 

 

 

 

 

 

 

 

 

.

.

.

 

가~~장 쉽고 단순한 버블 정렬 알고리즘 끝! :)

피드백, 궁금증은 언제나 댓글 주세여~~ 20,000!