선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

• 순서대로 해당 위치마다 (최솟값 or 최댓값)을 찾아서 넣는 알고리즘
• 오름차순 정렬 : 배열의 왼쪽부터 순서대로 최소값을 찾는다
• 내림차순 정렬 : 배열의 왼쪽부터 순서대로 최대값을 찾는다

시간 복잡도 : O(n^2)   => n(n-1)/2

공간 복잡도 : O(N)

장점 

• 구현하기 쉽다
• 비교는 여러번 수행하지만 교환 횟수는 적기 때문에 교환이 많이 일어나야 하는 정렬에 비해 효율적이다
• 배열 안에서 교환하기 때문에 다른 메모리 공간이 필요없다.

단점

• 시간 복잡도 측면에서 비효율적이다.
• 불안정한 정렬이다

 

function selectionSort(arr) {
  var min = 0;
  var temp = 0;
  var count = 0;

  for(var i=0; i<arr.length; i++) {
    min = i //(arr[0] ~ arr.length-1)순서대로 최솟값을 구하기위해서 min에 i를 넣는다
    for(var j=i+1; j<arr.length; j++) {
      count++
      if(arr[j]<arr[min]) {
        min = j
        console.log(`${i}번째 위치에 최솟값 ${j}번째에서 찾음`)
      }
      if(i != min) {
        temp = arr[i]
        arr[i] = arr[min]
        arr[min] = temp
        console.log(`${i}번째 위치에 최솟값 ${j}번째와 교환`)
      }
      console.log(`${arr}, i : ${i}, j : ${j}, 횟수 : ${count} 최솟값 : ${min}`)
    }
    console.log(`${i}번째 최솟값 탐색 끝`)
    console.log("")
  }
  return arr
}
console.log(selectionSort([2,13,22,6,1]))

// 2,13,22,6,1, i : 0, j : 1, 횟수 : 1 최솟값 : 0
// 2,13,22,6,1, i : 0, j : 2, 횟수 : 2 최솟값 : 0
// 2,13,22,6,1, i : 0, j : 3, 횟수 : 3 최솟값 : 0
// 0번째 위치에 최솟값 4번째에서 찾음
// 0번째 위치에 최솟값 4번째와 교환
// 1,13,22,6,2, i : 0, j : 4, 횟수 : 4 최솟값 : 4
// 0번째 최솟값 탐색 끝
// 
// 1,13,22,6,2, i : 1, j : 2, 횟수 : 5 최솟값 : 1
// 1번째 위치에 최솟값 3번째에서 찾음
// 1번째 위치에 최솟값 3번째와 교환
// 1,6,22,13,2, i : 1, j : 3, 횟수 : 6 최솟값 : 3
// 1번째 위치에 최솟값 4번째에서 찾음
// 1번째 위치에 최솟값 4번째와 교환
// 1,2,22,13,6, i : 1, j : 4, 횟수 : 7 최솟값 : 4
// 1번째 최솟값 탐색 끝
// 
// 2번째 위치에 최솟값 3번째에서 찾음
// 2번째 위치에 최솟값 3번째와 교환
// 1,2,13,22,6, i : 2, j : 3, 횟수 : 8 최솟값 : 3
// 2번째 위치에 최솟값 4번째에서 찾음
// 2번째 위치에 최솟값 4번째와 교환
// 1,2,6,22,13, i : 2, j : 4, 횟수 : 9 최솟값 : 4
// 2번째 최솟값 탐색 끝
// 
// 3번째 위치에 최솟값 4번째에서 찾음
// 3번째 위치에 최솟값 4번째와 교환
// 1,2,6,13,22, i : 3, j : 4, 횟수 : 10 최솟값 : 4
// 3번째 최솟값 탐색 끝
// 
// 4번째 최솟값 탐색 끝