[알고리즘] 선택 정렬에 관하여

• 가장 원시적인 방법중의 하나다
• 매번 정렬되지 않은 데이터중 가장 작은 것을 선택해 앞으로 보낸다는 의미다

 

코드 (자바스크립트)

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j;
      }
    }

    [array[i], array[minIndex]] = [array[minIndex], array[i]];
  }

  return array;
}

 

시간 복잡도

• 선택 정렬의 시간 복잡도는 O(N2) 이다
  •  N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다
  • 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다 (N + N - 1 + N - 2, N - 3 + … + 2)
  • 근사치로 이를 (N2 + N) / 2 로 표현할 수 있는데, 빅오 표기법으로 간단히 O(N2)로 한다

 

설명

1. 전체 중 가장 작은 데이터를 선택한다. 그리고 이것을 맨 앞에 있는 데이터와 바꾼다
2. 정렬되지 않은 데이터 중에서 가장 작은 데이터를 선택한다. 그리고 이것을 두번째 데이터와 바꾼다
3. 모든 데이터가 정렬 될때까지 step 1 그리고 step 2를 반복한다.

 

참고

1. 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈 - https://books.google.ca/books?id=vBz-DwAAQBAJ&source=gbs_book_other_versions