Swift) 선택 정렬이란/선택 정렬 구현해 보기

 

 

 

안녕하세요, UX를 고려하는 개발자 유자입니다!

오늘은 선택정렬이 무엇인지에 대해 알아보고
Swift로 구현해 보려고 합니다!

 

 

 

 

 

1. 선택 정렬이란?

 

선택 정렬은 정렬을 하기 위한 방법 중 하나로,

가장 작은 데이터(혹은 가장 큰 데이터)를 찾아
첫 번째 위치(혹은 가장 마지막 위치)의 데이터와

교환해 나가는 방식의 정렬 방법입니다.

 

 

 

 

 

 

 

 

 

2. 선택 정렬 예시

 

다음과 같이 정렬되지 않은 숫자들을

선택 정렬 방식을 사용하여 오름차순으로 정렬해 보겠습니다.

 

 

 

[6, 3, 8, 5, 2, 7, 4, 1]

 

 

 

 

가장 먼저 숫자에서 가장 작은 값을 찾습니다.

이때 가장 작은 값을 찾기 위해서는

다음과 같이 정렬되지 않은 모든 값을 확인하며 가장 작은 값을 찾아야 합니다.

 

 

① 가장 처음에 있는 6은 지금까지 본 숫자 중에 가장 작습니다.

따라서 현재까지는 가장 작은 값입니다.

 

 

 

 

② 다음은 3입니다.

3은 6보다 적으니 이제 6은 잊어버리고 3을 가장 작은 수로 기억합니다.

 

 

 

 

 

 

③ 8은 3보다 크고, 5도 3보다 크니 그냥 지나갑니다.

④ 2는 3보다 더 작은 수입니다. 그러므로 이제 2가 가장 작은 수가 됩니다.

 

 

 

 

⑤ 7과 4는 2보다 크니 그냥 지나갑니다.

⑥ 1은 2보다 작으니, 1이 가장 작은 수가 됩니다.

 

 

 

 

 

배열의 끝까지 다 확인해서 가장 작은 값을 찾았습니다.

오름차순으로 정렬하기로 했으니

가장 작은 값이 가장 앞에 있어야 하므로

첫 번째 위치에 있는 값과 교환합니다.

 

 

 

 

 

이제 정렬된 1은 제외하고

 

두 번째 숫자부터 시작해서 가장 작은 값을 찾고,

두 번째 자리를 교환합니다.

 

 

 

 

 

이 방법을 사용해 배열 끝까지 정렬하다 보면
다음과 같이 오름차순 정렬이 완료됩니다.

 

 

[1, 2, 3, 4, 5, 6, 7, 8]

 

 

 

이러한 정렬 방법을 ‘선택 정렬’이라고 합니다.

 

 

 

 

 

 

 

 

 

 

3. 선택 정렬 의사코드

데이터의 개수가 n개라고 했을 때

‘선택 정렬’을 의사코드로 다음과 같이 작성할 수 있습니다.

 

 

0부터 n - 1까지 i에 대해서
  i번째 항목부터 마지막 항목 중 가장 작은 항목을 찾습니다.
  가장 작은 항목을 i번째 항목과 교환합니다.

 

 

 

 

 

 

 

 

 

 

4. 선택 정렬 시간복잡도

 

 

4-1. 실행시간의 상한

선택 정렬을 사용할 경우 가장 작은 데이터(혹은 가장 큰 데이터)를 찾기 위해

 

 

 

처음에는 데이터 개수 n개를 모두 확인해야 합니다.

 

 

그리고 이렇게 확인한 데이터를 교환하면

 

 

 

 

두 번째 순서에는 n - 1개의 데이터를 확인합니다.

 

 

이런 방법으로 배열의 끝까지 정렬하게 되면

 

 

 

결과적으로는 총 최대 n + (n - 1) + (n  - 2) + …+1 번의 과정이 반복되고,

이를 식으로 표현하면 다음과 같이 표현할 수 있습니다.

 

n(n + 1) / 2

 

 

 

위 식은 다음과 같이 표현할 수 있고,

 

 

n^2 / 2 + n / 2

 

 

 

결국 n의 값이 커질수록 n^2의 영향력이 가장 크기 때문에

선택정렬의 Big - O는 O(n^2)가 됩니다.

(이 부분은 이전 포스팅 참고 부탁드립니다.)

 

 

 

 

 

 

4-2. 실행시간의 하한

 

그렇다면 선택 정렬을 오메가 표기법으로 작성하면 어떻게 될까요?

이미 정렬되어 있는 배열을 선택 정렬을 이용해서

오름차순 정렬해 보겠습니다.

 

 

[1, 2, 3, 4, 5, 6, 7, 8]

 

 

 

가장 처음에 있는 숫자 1이

배열에 있는 숫자 중 가장 작은 수인지 알기 위해서는

배열에 있는 모든 수를 확인해야 하므로 때문에 n번 실행됩니다.

 

두 번째 순서 역시 2가 가장 작은 수인 것을 확인하기 위해서는
정렬되어 있는 1을 제외하고 배열에 있는 모든 수를 확인해야 합니다.

따라서 n - 1번 실행됩니다.

 

즉, 정렬이 되어있다고 해도 모든 횟수를 그대로 진행해야 하므로

선택정렬의 오메가 표기법 역시 Ω(n^2)입니다.

 

 

 

 

 

 

 

 

 

 

5. 선택 정렬 구현해 보기

이제 선택정렬을 Swift로 구현해 보겠습니다.

 

func selectionSort(_ arr: inout [Int]) {
    let n = arr.count
    for i in 0..<(n - 1) {
        var minValueIndex = i
        for j in (i + 1)..<n {
            if arr[j] < arr[minValueIndex] {
                minValueIndex = j
            }
        }
        arr.swapAt(minValueIndex, i)
    }
}

 

 

 

매개 변수로 전달받은 값을 함수 내부에서 수정할 것이기 때문에

inout 매개 변수로 작성해 줍니다.

 

이제 0부터 arr.count - 1 전까지 반복해 줍니다.

가장 마지막 데이터는 정렬할 필요가 없기 때문에

arr.count가 아닌 arr.count - 1로 작성해 주었습니다.

 

i를 minValueIndex 변수에 할당하고,

i + 1부터 배열 마지막 항목까지 탐색해서,

값이 더 작으면 값을 변경해 주었습니다.

 

마지막으로 swapAt 메서드를 사용해서

위치를 변경하면 오름차순 선택 정렬 완성됩니다!

 

 

 

 

---

 

 

 

 

 

이렇게 선택정렬 포스팅이 마무리되었습니다!

유튜브에 정렬 알고리즘과 관련된 좋은 시각 자료가 있어서 함께 공유합니다!

유튜브에 있는 다른 배열에 대해서는 앞으로 한 개씩 공부해 보겠습니다!

 

 

유튜브 링크 바로가기