선택 정렬Selection Sort
선택 정렬Selection Sort 알고리즘의 특징
- 제자리 정렬(in-place sorting)의 하나이다.
- 입력벼열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법.
- 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘.
- 첫번째 순서에 첫번째 위치에 가장 최소값을 넣는다.
- 두번째 위치엔 남은값중 최솟값을 넣는다.
- n 번째 위치엔 남은 값중 최솟값을 넣는다.
- 프로세스 방법
- 주어진 배열에서 최솟값을 찾는다.
- 그 값을 맨앞의 값과 교체한다.
- 맨처음 위치를 뺀 나머지 리스트를 같은 방법으로 교채한다.
- 하나의 원소만 남을때까지 위의 과정을 반복한다.
- 장점
- 자료의 이동 횟수가 미리 결정된다.
- 단점
- 안정성을 만족하지않는다.
알고리즘 예제
선택정렬의 코틀린 코드
fun main(){
print(selectionSort(intArrayOf(3,6,1,7,5,4,9)).joinToString(","))
//1,3,4,5,6,7,9
}
fun selectionSort(arr: IntArray): IntArray{
var minIdx = 0
var temp = 0
for(i in arr.indices){
minIdx = i
for(j in i+1 until arr.size ){
if(arr[minIdx] > arr[j]) {
minIdx = j
}
}
if(minIdx != i){
temp = arr[i]
arr[i] = arr[minIdx]
arr[minIdx] = temp
}
}
return arr
}- 시간복잡도
- O(n^2)
- 정렬할 자료의 길이만큼 이중 반복을한다.
반응형
'프로그래밍 > 알고리즘' 카테고리의 다른 글
| 레코드, 키의 정의 및 검색 트리 (0) | 2020.12.29 |
|---|---|
| 삽입정렬Insertion Sort (0) | 2020.12.27 |
| 버블 정렬Bubble Sort (0) | 2020.12.26 |
| 앞으로 공부할 알고리즘 (0) | 2020.12.22 |