정렬 알고리즘 - 선택 정렬의 이해와 효율적 구현 방법

선택 정렬 개요

• 매 반복마다 배열에서 가장 작은 값을 찾아 정렬되지 않은 부분 배열의 첫 번째 요소와 교환하는 방식으로 동작합니다.

선택 정렬 동작 원리

1. 배열에서 최솟값을 찾습니다.
2. 최솟값과 배열의 첫 번째 요소를 교환합니다.
3. 다음 반복에서는 두 번째 요소부터 시작하여 남은 요소들 중 최솟값을 찾아 두 번째 요소와 교환합니다.
4. 이 과정을 반복하여 배열을 정렬합니다.

선택 정렬 코드 예시

function test(arr) {
 const n = arr.length
 for(let i = 0; i < n - 1; i++) {
  let minIndex = i
  for(let j = i + 1; j < n; j++) {
   if(arr[j] < arr[minIndex]) {
    minIndex = j
   }
  }
 }
 if(minIndex !== i) {
  [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]]
 }
}

const arr = [5,4,3,2,1]
test(arr)

• 결과는 1,2,3,4,5로 나옵니다. 반대의 결과가 나오기 위해서는 if(arr[j] > arr[minIndex])로 바꿔야합니다.
• 위치 교환은 es6 구조 분해 할당 문법입니다.

선택 정렬 시간 복잡도

• 최선이나 최악이나 평균의 경우 O(n^2) 시간 복잡도를 가집니다.

선택 정렬 장점

• 구현이 간단합니다.
• 제자리 정렬이므로 추가적인 메모리 공간이 필요하지 않습니다.

선 정렬 단점

• 배열의 크기가 클수록 비효율적입니다.
• 항상 최악의 경우와 동일한 시간 복잡도를 가집니다.

버블 정렬 활용

• 이해하기 쉬워서 알고리즘 학습의 첫 걸음으로 활용됩니다.