선택 정렬

• 매번 가장 작은 것을 찾아 제일 앞의 값과 교환하는 것
• 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 값과 교환하고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복수행

예시)
let array = [7,2,4,8,1,4,0,10,11];
let N = array.length;//데이터의 개수를 N으로 표현

for(let i = 0; i < N; i++){
  let min = array[i];
  let minIndex = i;
  for(let j = i+1; j < N; j++){
    //i를 min으로 설정했기때문에 i+1부터 반복수행
    if(min > array[j]){
      min = array[j];
      minIndex = j;
    }
  }
  let temp = array[minIndex];
  array[minIndex] = array[i];
  array[i] = temp;
}
console.log(array);

//출력: [0, 1, 2, 4, 4, 7, 8, 10, 11]

시간복잡도

• 매번 가장 작은 수를 찾기 위해 비교연산이 필요
• 연산 횟수는 N + (N-1) + (N-2) + (N-3)+ ... +2
  //N, N-1, N-2,...,2개중에 가장 작은 수를 찾음
  근사치로 N*(N+1)/2번의 연산을 수행, 이는 (N^2+N)로 표현할 수 있고, 빅오 표기법으로는 O(N^2) (2중 반복문이 사용되었기 때문)