[Kotlin] 선택 정렬 - Selection Sort

🔷 선택 정렬 (Selection Sort)이란?

[이미지 출처]https://www.programmingsimplified.com/c/source-code/c-program-selection-sort

   가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 마지막 위치)의 수와 교환하는 방식의 정렬 방법이다.

    조건에 충 족하는 데이터와 변경할 위치의 데이터를 선택하여 변경한다.

    데이터를 정렬하기 위하여 추가적인 데이터가 필요하지 않기에 '제자리 정렬(in-place sort)'로 분류되기도 한다.

---

🔷 버블 정렬의 장점

🔹교환 횟수 최소화

    변경 위치는 미리 정해져있고 부합하는 데이터를 찾아 변경하는 방식으로 교환 횟수는 최소화된다.

🔹적은 메모리

    정렬을 위하여 추가적인 메모리를 사용하지 않는다.

---

🔷 버블 정렬의 단점

🔹비교 횟수 증가

    각 위치에 맞는 데이터를 찾기 위하여 매번 데이터를 비교해야한다.

🔹안정성

    값이 같은 데이터가 존재하는 경우 상대적인 위치가 변경될 수 있다.

---

🔷 시간 복잡도

🔹최악의 경우 :  O(n^2)

    n개를 입력했을 때, 최악의 경우 n*n번이 실행된다.

🔹최선의 경우 :  Ω(n^2)

    n개를 입력했을 때, 최선의 경우 n*n번이 실행된다.

---

🔷 구현

🔹코틀린 (Kotlin)

[이미지 출처]https://visualgo.net/en/sorting

fun main() {
	// 리스트 생성
    val selectionList = mutableListOf<Int>(6, 5, 1, 2, 4, 3)
	
    // 리스트 내부 반복
    for(i in 0 until arr.size-1) {
    	// 가장 작은 인덱스로 현재 인덱스 설정
        var minIdx = i
        
        // 현재 인덱스에서부터 리스트 내부 반복
        for(j in i+1 until selectionList.size) {
        	// 가장 작은 값으로 인덱스 교체
            if(selectionList[j] < selectionList[minIdx]) minIdx = j
        }
        
        // 가장 작은 값과 현재 데이터 교체
        var temp = selectionList[minIdx];
		selectionList[minIdx] = selectionList[i];
		selectionList[i] = temp;
    }
}