선택정렬

진행방법

• 전체 배열에서 가장 작은 값을 찾는다
• 배열에서 맨 앞의 값과 이 최솟값의 위치를 바꾼다
• 즉,매 번 시행시마다 가장 작은 원소의 위치가 하나씩 결정된다(버블정렬은 맨 뒤에 가장 큰 원소가 하나씩 결정되던 것과 반대)
• 맨 앞의 값을 제외하고 다시 최솟값을 찾고,이미 결정된 맨 앞의 값을 제외한 가장 앞의 원소와 위치를 바꾼다
• 정렬이 끝날 때까지 계속 반복

장점

• 추가 메모리를 필요로 하지 않고, 주어진 공간 내에서만 메모리 사용

단점

• 정렬이 끝나고 주어진 순회횟수를 끝까지 채움
• 언제나 시간복잡도 O(n^2)을 가진다(매번 최솟값을 찾아야 하기에)
• 그러므로 효율이 떨어짐

특징

• 중복된 원소가 존재하는 경우,그 값 사이의 위치가 바뀔 수 있는 unStable한 정렬

구현

• 해야할 것
  최솟값을 찾기 -> 그 값을 가장 앞의 값과 바꾸기
  계속 반복

let arr = [5, 4, 3, 2, 10, 1,1];

const selectionSort = (arr) => {
  let minIndex;
  for (let i = 0; i < arr.length; i++) {
    minIndex = i; 
    
    //매 시행시 최솟값이 배열의 앞에 위치
    //비교를 시작하는 위치를 오른쪽으로 한 칸씩 옮겨줌
    
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;  
        
        //주어진 배열을 순회하며 가장 작은 값의 인덱스를 저장
      }
      if (minIndex !== i) {
        let swap = arr[i]; 
        //배열의 맨 앞에 위치한 값
        
        arr[i] = arr[minIndex]; 
        //최솟값을 배열의 맨 앞에 넣는다
        
        arr[minIndex] = swap;   
        //원래 최솟값의 위치에 맨 앞에 있던 값을 넣음
      }
    }
    console.log(`${i+1}회전: ${arr}`);
  }
  return arr;
};
console.log(selectionSort(arr)); 
//[1, 1, 2, 3, 4, 5, 10]