선택 정렬 (Selection Sort)

선택 정렬(Selection Sort)은 각 순서에 넣을 요소의 '위치'는 이미 정해져 있고, 아직 정렬되지 않은 나머지 배열 중에서 가장 작은(또는 큰) 값을 계속 '선택'하여 정해진 위치의 요소와 교환(Swap)하는 매우 직관적이고 단순한 제자리 정렬 알고리즘입니다.

1. 선택 정렬의 작동 원리

버블 정렬(Bubble Sort)과 마찬가지로 동작은 단순하지만 교환 횟수가 적다는 특징이 있습니다.
● 최솟값 탐색(Scanning) : 현재 인덱스부터 배열의 끝까지 모두 훑으면서 가장 작은 값을 찾습니다.
● 교환(Swapping) : 찾아낸 최솟값을 현재 인덱스의 값과 자리를 바꿉니다.
● 반복(Iteration) : 인덱스를 1씩 늘려가며 위 과정을 배열 끝까지 반복합니다.

2. 시간 및 공간 복잡도 분석

평가 기준	복잡도	심층 설명
최선/평균/최악 시간 복잡도	O(N²)	데이터가 이미 정렬되어 있든 역순이든 상관없이 무조건 배열 전체를 탐색하여 최소값을 찾아야 하므로 언제나 `N(N-1)/2` 번의 비교를 수행합니다.
공간 복잡도	O(1)	주어진 배열 안에서 값의 위치만 교환하는 제자리 정렬(In-place Sort)이므로 별도의 추가 메모리 공간이 필요하지 않습니다.

💡 실무 지식: 불안정 정렬(Unstable Sort)의 한계

선택 정렬은 동일한 값을 가진 요소들의 상대적인 순서가 뒤바뀔 수 있는 불안정 정렬(Unstable Sort)입니다. 예를 들어 [5A, 5B, 1] 이라는 배열에서 최솟값 1과 맨 앞의 5A를 교환하면 [1, 5B, 5A]가 되어 5A와 5B의 원래 순서가 역전됩니다. O(N²) 이라는 한계와 맞물려 실제 서비스에서는 거의 사용되지 않으며 알고리즘 학습용으로 주로 다뤄집니다.

// JavaScript 구현 function selectionSort(arr) { const n = arr.length; console.log("초기 배열:", arr); for (let i = 0; i < n - 1; i++) { let minIdx = i; // 현재 인덱스 이후부터 최소값의 인덱스를 찾음 for (let j = i + 1; j < n; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } // 최소값이 자기 자신이 아니라면 스왑(Swap) if (minIdx !== i) { let temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = temp; } } return arr; } const arr = [5, 3, 1, 4, 2]; console.log("정렬 결과:", selectionSort(arr));

평가 기준

복잡도

심층 설명

최선/평균/최악 시간 복잡도

O(N²)

데이터가 이미 정렬되어 있든 역순이든 상관없이 무조건 배열 전체를 탐색하여 최소값을 찾아야 하므로 언제나 N(N-1)/2 번의 비교를 수행합니다.

공간 복잡도

O(1)

주어진 배열 안에서 값의 위치만 교환하는 제자리 정렬(In-place Sort)이므로 별도의 추가 메모리 공간이 필요하지 않습니다.