[Algorithm] Selection Sort(선택 정렬) : 가장 작은 원소를 찾아서 선택하고 기준 원소와 자리를 교환하는 방식

알고리즘에서의 Selection Sort(선택 정렬)에 대하여 Swift를 기반으로 하여 살펴봅니다.

 

 

#. 구독 대상

• 컴퓨터 및 소프트웨어 공학과 관련자
• 소프트웨어 관련 종사자 
• 기타 컴퓨터 공학에 관심이 있으신 분
• 알고리즘의 개념을 잡고 싶으신 분
• 기타 소프트웨어 개발과 지식에 관심이 있으신 모든 분들
• Swift 언어를 활용하여 알고리즘을 공부해보고 싶으신 분들

 

 

---

 

Selection Sort(선택 정렬)

 

Selection Sort(선택 정렬)은 배열의 전체 원소들을 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식으로 정렬하는 정렬 알고리즘입니다.

 

즉 전체 원소 중에서 가장 작은 원소를 찾아서 선택하고 기준 원소와 자리를 교환하는 방식입니다.

 

 

 

 

 

---

 

 

 

동작 흐름

 

기본적인 알고리즘의 컨셉을 살펴보면 아래와 같습니다.

 

 

1. 배열 요소 중에서 가장 작은 값을 찾습니다.

2. 제일 작은 값을 첫 번째 요소와 자리를 교체합니다.

3. 이번에는 2번째부터 전체 배열 요소 중 가장 작은 값을 다시 찾습니다.

4. 다시 2번과 같이 2번째 자리의 요소와 가장 작은 값을 비교 후 자리를 교체합니다.

5. 배열의 마지막 자리까지 위와 같은 방법을 반복합니다.

 

 

[ 8, 3, 5, 4, 6 ] 인 배열을 정렬한다고 생각해봅니다.

 

위에서 설명한 방식대로 진행하면 아래와 같은 흐름으로 진행됨을 알 수 있습니다.

 

 

 

 

 

 

---

 

 

 

 

특징

 

선택 정렬은 아래와 같은 특징을 가진 알고리즘입니다.

 

1. 배열 요소 중에서 가장 작은 값을 찾고 해당 값을 제일 앞으로 이동시켜 교환하면서 비교하는 정렬 알고리즘

2. 이중 루프로서 구현이 됨에 따라서 최고, 최악, 평균 모두 시간 복잡도가 O(n^2)이다.

3. 버블 정렬과 비슷하게 요소를 비교하지만 교환은 단 한번만 이루어진다.

 

 

 

 

---

 

 

 

 

 

Implementation

 

Swift를 활용하여 선택 정렬 알고리즘을 살펴보겠습니다.

 

func selectionSort<T : Comparable>(_ array: [T]) -> [T] {
    var arr = array
    
    for stand in 0 ..< (arr.count - 1) {
        var lowest = stand
        for index in (stand + 1) ..< arr.count {
            if arr[lowest] > arr[index] {
                lowest = index
            }
            let tmp = arr[lowest]
            arr[lowest] = arr[stand]
            arr[stand] = tmp
        }
    }
    
    return arr
}

let numbers = [ 5, -2, 3, 1, 10, 9, 6, 8, 7, 0 ]

print(selectionSort(numbers)) // [-2, 0, 1, 3, 5, 6, 7, 8, 9, 10]

 

 

 

---

 

 

 

이상으로 Swift를 기반으로하여 Selection Sort(선택 정렬) 에 대하여 설명하였습니다.

 

 

 

 

감사합니다.

 

 

 

 

 

 

 

---

[참고 자료(References)]

 

[1] Swift3 ) Swift로 선택정렬(Selection Sort)짜보기 : https://zeddios.tistory.com/66

[2] 선택 정렬 selection sort with swift : https://hyerios.tistory.com/66

[3] 버블 정렬과 선택 정렬 : https://usinuniverse.bitbucket.io/blog/sort-algorithm-1.html

[4] Swift Language 선택 정렬 : https://riptutorial.com/ko/swift/example/28305/선택-정렬

[5] [Sort] 선택 정렬(Selection Sort) : https://palpit.tistory.com/123

[6] Sorting Algorithms: Implementing Selection Sort Using Swift : https://medium.com/appcoda-tutorials/sorting-algorithms-implementing-selection-sort-using-swift-30500ae6b93a

[7] [Algorithm] Selection Sort, 선택 정렬 : https://velog.io/@delmasong/Algorithm-Selection-Sort-선택-정렬

[8] What is Selection Sort? : https://www.codingame.com/playgrounds/506/sorting-in-swift/selection-sort

[9] [알고리즘] 정렬 알고리즘 - 선택,버블,삽입 : https://baked-corn.tistory.com/114

[10] 선택 정렬 : https://ko.wikipedia.org/wiki/선택_정렬