[Algorithm] Selection Sort, 선택 정렬

What is it

선택정렬이란, 배열이 있을 때 가장 작은 요소를 기준으로 삼아
맨 앞의 데이터와 자리를 바꿔 정렬하는 방법이다!

How to works it

1. 주어진 데이터 중, 최소값을 찾음
2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복

출처 https://visualgo.net/en/sorting

선택 정렬은 위의 이미지처럼 정렬된다!

기준이 될 맨 앞자리를 가리킬 for문과
그 기준 뒤부터 배열 맨 끝까지 돌면서 가장 작은 요소를 찾을 for문이 필요하다

Codes

func selectionSort(_ array: Array<Int>) -> Array<Int>{
    var arr = array
    for stand in 0 ..< (arr.count - 1) {	//기준이 될 맨 앞자리를 가리킬 for문
        var lowest = stand
        for index in (stand + 1) ..< arr.count {	//기준 뒤부터 배열 맨 끝 중 최솟값 찾는 for문
            if arr[lowest] > arr[index] {
                lowest = index
            }
            let tmp = arr[lowest]		//가장 작은 요소를 찾으면 맨 앞자리와 자리를 바꿈 
            arr[lowest] = arr[stand]
            arr[stand] = tmp
        }
    }
    return arr
}

시간 복잡도는 반복문이 두개여서 O(n^2)