Swift) 선택 정렬(Selection Sort) 구현 해보기

 

 

 

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

오늘은 알고리즘 중에서 선택 정렬을 Swift로 구현해보려고 해요!

어렵지 않으니 이또한 후딱 해치웁시다!!!!!!!!!!

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

 

 

 

 

1. 선택 정렬이 모야?

 

선택 정렬 역시 정렬을 하기 위한 방법 중 하나임!

일단 선택 정렬의 방식은

 

① 데이터 중 가장 작은 값을 찾는다

② 찾은 값을 데이터 맨 앞 값과 교체한다

③ 맨 앞 데이터를 제외하고 위 과정을 반복한다

 

자 이게 끝임..

그림으로 보면 더 쉬움!!!

 

 

 

 

 

 

이렇게 0번 index부터 가장 작은 값으로 채워 나가는 게

선택 정렬임!! 버블 정렬보다 훨 쉬운듯 :)

 

 

 

 

2. 구현 전 생각하기

 

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

기준 index의 다음 index부터, 최소값을 찾기 위해선 몇 번 비교해야 하는가?

에 대해 생각을 해보는 것임

 

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

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

 

 

	[4, 10, 2]	[4, 10, 2, 1]	최소값
1단계	[4, 10, 2]	[4, 10, 2, 1]	4
2단계	[4, 10, 2]	[4, 10, 2, 1]	2
3단계		[4, 10, 2, 1]	1
swap	[2, 10, 4]	[1, 10, 2, 4]

 

 

배열의 요소가 3개일 경우, 

0번째 index가 기준일 경우, 1~2번째 index 중 최소값을 찾음

배열의 요소가 4개일 경우,

0번째 index가 기준일 경우, 1~3번째 index 중 최소값을 찾음

 

아하! 최소값을 찾는 스캔 작업은

(기준 index + 1 ..< 배열 요소의 수.count) 만큼 반복하면 끝나는구나! 라는 것을 캐치해야 함

 

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

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

 

맞음! 위에서도 말했듯, 선택 정렬은 위 스캔 작업을 배열 전체가 정렬될 때까지

기준 index를 1씩 늘려가며 반복해야 함..!

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

.

.

 

자 이제 두 번째로, 

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

에 대해 생각해 보는 것임

 

 

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

 

 

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

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

 

왜냐??

스캔 작업을 하면 할 수록,

가장 작은 수부터(맨 처음부터) 하나씩 정렬이 된단 것을 위 표에서 볼 수 있음

그말인 즉, 1번 스캔하면 가장 첫 번째 요소는 가장 작은 값으로 정렬되었단 것이고,

2번 스캔하면 두 번째 요소는 두 번째 작은 값으로 정렬되었단 것임!

 

정리하면,

스캔 작업을 한 번 할 때마다 앞에서부터 작은값으로 하나씩 정렬될 테니,

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

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

나머지 1개는 가장 큰 값으로, 자동으로 마지막 index에 들어있게 되어 있을테니!)

 

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

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

 

 

 

 

3. 코드로 구현해보기

 

 

func selectionSort(_ array: inout [Int]) {
    for stand in 0..<(array.count - 1) {                // 스캔 작업 반복
        var minIndex = stand
        for index in (stand + 1)..<array.count {        // 스캔 작업 (stand가 0이면 1번 index부터 마지막 Index까지 돌며 최소값을 찾아야 하니까)
            if array[index] < array[minIndex] {
                minIndex = index
            }
        }
        array.swapAt(stand, minIndex)
    }
}

 

 

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

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

 

개인적으로 버블 정렬보다 훨씬 쉽다 생각함..!

 

 

 

 

4. 선택 정렬의 시간 복잡도

 

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

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

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

 

O(n^2)

 

으로,

구현이 쉽고 간단한 장점이 있지만,

버블 정렬과 마찬가지로... 느린 알고리즘임..!

 

 

 

 

 

 

 

.

.

.

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

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

 

버블 정렬하고 말투가 거의 똑같다 생각되면, 기분탓일 겁니다 ^^;