정렬 - 선택 정렬(Selection sort)

버블 정렬과 함께 기본적인 정렬에 속하는 정렬 알고리즘은 하나가 더 있습니다. 바로 선택 정렬인데요, 버블 정렬과 비슷하지만 약간 다른 방식의 알고리즘입니다. 오늘은 선택 정렬(Selection sort)에 대해 알아보도록 하겠습니다.

 

📍 선택 정렬(Selection sort)

선택 정렬은 전체 값 중 가장 작은 값을 찾아 제일 앞에 두고, 첫번째 값을 제외하고 제일 작은 값을 찾아 두번째에, 두 번째까지의 값을 제외하고 가장 작은 값을 찾아 세번째에 배치하는 식의 연산을 통해 정렬하는 방식입니다.

자바스크립트로 구현하면 다음과 같습니다.

//숫자로 이루어진 배열 arr가 있다고 가정

for (let i = 0; i < n - 1; i++) {
  let min = i;
  for (let j = i + 1; j < n; j++) {
    //i 다음것이랑부터 비교
    if (arr[j] < arr[min]) {
      //숫자로 만들어 비교
      min = j;
    }
  }
  let temp = inputTestCase[i]; //자리바꾸기
  arr[i] = arr[min];
  arr[min] = temp;
}

버블정렬과 비슷한 것 같지만, 버블 정렬은 정렬된 상태인 경우 중간에 중단이 가능합니다. 하지만 선택 정렬의 경우 비교 연산을 계속 수행해야 합니다.

 

⏰ 시간복잡도

선택 정렬의 시간복잡도는 어떻게 될까요? 정렬을 해야 할 최악의 경우, 즉 단 한 글자도 제자리에 있지 않은 다음과 같은 배열이 있다고 생각해봅시다.

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

 

무한루프가 1번 돌 경우 [1, 4, 2, 3, 5];

2번째 돈 경우 [1, 3, 2, 4, 5];
3번째 돈 경우 [1, 2, 3, 4, 5];
4번째에서 마지막으로 확인 후 종료되게 됩니다.

 

위와 같이 무한루프는 총 4번을 돌며, 한번 돌 때마다 내부 for문은 순서대로 4, 3, 2, 1 번 돌게 됩니다. 

 

따라서 길이가 n인 배열의 선택 정렬의 시간복잡도는 ((n-1) + (n-2) + .... + 1) 이므로 $O(n^2)$으로 표현됩니다.