선택 정렬

선택정렬(O(n^2))

• 버블정렬과 마찬가지로 기본적인 정렬
• 0번째에 한바퀴를 돌아서 최소값을 찾아서 최소값을 0번째로 옮기고, 최소값이 있던 자리에 0번째 값을 옮긴다.
• 1번째에 1번째 최소값을 찾아서 1번째로 옮기고 1번째 최소값이 있던 자리에 1번째 값을 옮긴다.
• 이런식으로 반복

var selectionSort = function(arr) {
  let minIndex, temp, i, j;
  for (i = 0; i < arr.length - 1; i++) {
    minIndex = i; // 최소값 인덱스는 i로 놓고 반복
    for (j = i + 1; j < arr.length; j++) { // i 다음 값부터 해서 반복
        if (arr[j] < arr[minIndex]) { // 현재 위치에 담긴 값이 i번째 값보다 작다면
            minIndex = j; // 최소값 인덱스는 현재 위치
        }
    }
    // 현재 순서값과 최소값의 위치를 서로 바꿔줌
    temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
  }
  return arr;
};

[9,6,7,3,5] minIndex=0

• j[1] 6, 9 minIndex = 1;
• j[2] 7, 6 minIndex = 1; => 안걸림
• j[3] 3, 6 minIndex = 3;
• j[4] 5, 3 minIndex = 3; => 안걸림
• 처음 한바퀴돌면 가장작은 수가 담긴 인덱스가 3이라는 것을 알수 있음
• temp=3, arr[3]=9, arr[0]=3 => 0번째에 최소값이 옴

[3,6,7,9,5] minIndex=1

• j[2] 7, 6 minIndex=1 => 안걸림
• j[3] 9, 6 minIndex=1 => 안걸림
• j[4] 5, 6 minIndex=4 => 서로 바꿈
• temp=4, arr[4]=6, arr[1]=5 => 1번째 최소값 정렬

[3,5,7,9,6] minIndex=2

• j[3] 9, 7 minIndex=1 => 안걸림
• j[4] 6, 7 minIndex=4 => 서로 바꿈
• temp=6, arr[4]=7, arr[2]=6 => 2번째 최소값 정렬

[3,4,6,9,7] minIndex=3

• j[4] 7, 9 minIndex=4 => 서로 바꿈
• temp=6, arr[4]=9, arr[3]=7

[3,4,6,7,9] 끝