선택 정렬Selection Sort

선택 정렬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)
  • 정렬할 자료의 길이만큼 이중 반복을한다.