[Algorithm] Selection Sort (선택정렬) by Swift

안녕하세요! Joy 입니다. 알고리즘을 또 공부하러 왔습니다..

HIG 포스팅도 계속 해야하는데 번역기를 많이 참조하지만 생각보다 시간이 걸리다보니 늦어지네요 ㅠ_ㅠ

(근데 갑자기 생각난건데 구독자가 많은 것도 아닌데 약간 유루바 느낌으로 포스팅 하는거 재밌습니다..히히)

 

아무튼! 오늘은 저번 거품정렬 (Bubble Sort) 에 이어 두번째 알고리즘 선택정렬을 정리해보려고 해요! 

 

오타와 오류 지적은 감사히 받겠습니다!

 

개념

• Bubble Sort와 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
• 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 된다.

 

Process

• 먼저 주어진 배열 중에 최소값을 찾는다.
• 그 값을 맨 앞에 위치한 값과 교채한다. (pass)
• 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.

 

이 글을 보시는 분들은 밑으로 내리기 전에 자신만의 선택 정렬 메소드를 먼저 한번 작성해보세요!!

 

제가 작성한 선택정렬 메소드는 아래와 같습니다!!

func selectionSort(arrOriginal: [Int]) {
    var arr = arrOriginal
    var indexMin: Int = 0
    var tmp: Int = 0
    
    // 1. 위치 선택
    for i in 0..<arr.count-1 {
        indexMin = i
        // 2. i+1 번째 원소부터 선택한 위치의 값과 비교를 시작
        for j in i+1..<arr.count {
            // 3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면 위치를 갱신
            if arr[j] < arr[indexMin] {
                indexMin = j
            }
        }
        
        // 4. swap
        // 2번 반복문이 끝난 뒤에는 indexMin에 1번에서 선택한 위치에 들어가야하는 값의 위치를 갖고 있으므로 서로 교환
        tmp = arr[indexMin]
        arr[indexMin] = arr[i]
        arr[i] = tmp
    }
    print(arr)
}

 

Selection Sort 시각적으로 확인하기

Selection Sort

 

시간복잡도

• 데이터의 개수가 n개라고 했을 때,
  • 첫 번째 회전에서의 비교 횟수 = 1 ~ (n-1) => n-1
  • 두 번째 회전에서의 비교횟수 = 2 ~ (n-1) => n-2
  • ...
  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
• 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악의 경우 시간 복잡도는 O(n^2)으로 동일하다.

 

공간복잡도

• 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(n)이다.

 

장점

• Bubble Sort와 마찬가지로 알고리즘이 단순하다.
• 정렬을 위한 비교 횟수는 많지만 Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• Bubble Sort와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬

 

단점

• 시간 복잡도가 O(n^2)으로 비효율적이다.
• 불안정 정렬이다.

 

 

Selection Sort는 Bubble Sort와 유사하지만 조금 더 빠르다는 걸 알 수 있었어요.

n번째 회전에 정렬상태를 만드는 문제에서 활용할 수 있겠네요!

 

오늘도 읽어주셔서 감사합니다 :) 

 

 

참고 출처 : https://gyoogle.dev/blog/algorithm/Selection%20Sort.html