선택 정렬

Goal

1. 선택 정렬의 정렬 방식
2. 선택 정렬의 특징
3. javascript 구현
4. 시간 복잡도

선택 정렬의 개념

가장 작은 원소를 차례차례 탐색 후 맨 왼쪽 원소와 스왑하는 정렬 방법.

선택 정렬 예제

선택 정렬 javascript 구현 (오름 차순)

const numbers = [5, 10, 7, 3, 1, 9, 6, 4, 2, 8];

function selectSort(numbers) {
  const len = numbers.length;
  let min = 0;
  for (let i = 0; i < len - 1; i++) {
    min = i;
    for (let j = i + 1; j < len; j++) {
      if (numbers[j] < numbers[min]) min = j;
    }
    [numbers[i], numbers[min]] = [numbers[min], numbers[i]];
  }
  return numbers;
}

console.log(selectSort(numbers));  // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

선택 정렬의 시간 복잡도

최선 최악의 경우 모두 O(N^2)의 시간복잡도를 가진다.