1. 서론
코딩 테스트, 알고리즘 문제 풀이에 있어서 정렬 알고리즘은 필수적으로 익혀야 할 주제입니다. 다양한 배열의 정렬 방법 중에서 선택 정렬(Selection Sort)은 그 구현이 간단하고, 그 과정이 직관적이기 때문에 많은 사람들에게 초기 단계에서 배우기 좋은 알고리즘으로 여겨집니다. 이번 강좌에서는 선택 정렬의 개념과 원리, 그리고 자바스크립트로 구현하는 방법을 자세히 알아보겠습니다.
2. 선택 정렬(Selection Sort)란?
선택 정렬은 배열을 정렬하는 간단한 알고리즘으로, 주어진 배열을 반복하면서 가장 작은 값(또는 가장 큰 값을) 찾아서 현재 위치와 교환하는 방식으로 동작합니다. 이 알고리즘은 매 회전마다 정렬된 부분과 정렬되지 않은 부분으로 나누어 진행됩니다.
2.1. 동작 원리
선택 정렬은 다음의 방법으로 동작합니다:
- 배열의 첫 번째 요소부터 시작하여, 배열의 나머지 요소 중에서 가장 작은 요소를 찾아 첫 번째 요소와 교환합니다.
- 두 번째 요소부터 같은 과정을 반복하여, 두 번째 요소와 두 번째 이후의 요소 중에서 가장 작은 요소를 교환합니다.
- 이 과정을 배열의 마지막 요소까지 반복합니다.
2.2. 선택 정렬의 시간 복잡도
선택 정렬의 시간 복잡도는 최악의 경우와 평균 경우 모두 O(n^2)입니다. 이는 배열의 크기에 따라 성능이 급격히 저하될 수 있다는 것을 의미합니다. 따라서 선택 정렬은 소규모 데이터 세트에서 사용할 때 가장 적합합니다.
3. 선택 정렬 구현하기
이번 장에서는 선택 정렬을 자바스크립트로 구현해보겠습니다.
3.1. 기본 구현
아래의 코드는 선택 정렬을 구현한 기본적인 자바스크립트 함수입니다:
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
// 현재 인덱스(i)를 후보로 초기화
let minIndex = i;
// 나머지 배열을 스캔하여 가장 작은 요소의 인덱스를 찾음
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j; // 더 작은 값을 찾으면, minIndex를 업데이트
}
}
// 후보가 된 최소값과 현재 위치(i)를 교환
// 현재 위치가 최소값이 아니라면 교환
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// 사용 예
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = selectionSort(unsortedArray);
console.log(sortedArray); // [11, 12, 22, 25, 64]
3.2. 코드 설명
위의 코드는 선택 정렬 알고리즘을 사용하는 함수입니다. 함수를 하나씩 분석해 보겠습니다:
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]]; }: 최종적으로 최소값이 현재 인덱스 위치에 없으면, 교환을 수행합니다.
4. 최적화된 선택 정렬
기본 선택 정렬은 최적화를 추가할 수 있습니다. 불필요한 교환을 줄이는 방법을 추가하여 성능을 조금 더 향상시킬 수 있습니다. 예를 들어, 정렬이 완료된 상태를 확인하여 더 이상의 교환이 필요 없을 경우 루프를 종료하고 성능을 높이는 방법이 있습니다. 아래 코드는 최적화된 선택 정렬을 보여줍니다:
function optimizedSelectionSort(arr) {
const n = arr.length;
let isSorted = true;
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;
isSorted = false; // 교환이 발생할 것임을 메모
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
// 배열이 이미 정렬된 경우 루프 종료
if (isSorted) break;
}
return arr;
}
// 사용 예
const unsortedArray = [64, 25, 12, 22, 11];
const sortedArray = optimizedSelectionSort(unsortedArray);
console.log(sortedArray); // [11, 12, 22, 25, 64]
4.1. 최적화 설명
최적화된 선택 정렬 함수는 초기화 단계에서 let isSorted = true;를 사용하여 배열이 정렬되었음을 추적합니다. 각 반복 후, 배열에 실제 교환이 있었다면 해당 플래그를 false로 설정합니다. 만약 현재 반복에서 교환이 발생하지 않았다면 배열이 완전히 정렬되었으며, 반복문을 종료합니다.
5. 실용적인 예제
선택 정렬을 활용하여 실제로 데이터를 정렬하는 예제를 보여드리겠습니다. 예를 들어, 학생의 성적 데이터를 정렬할 수 있습니다. 이를 통해 학생들의 성적을 비교하거나 필요한 정보를 제공하는 데 도움을 줄 수 있습니다.
const students = [
{ name: "Emily", score: 85 },
{ name: "David", score: 92 },
{ name: "Sophie", score: 76 },
{ name: "John", score: 89 },
{ name: "Max", score: 90 },
];
function selectionSortByScore(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].score < arr[minIndex].score) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
const sortedStudents = selectionSortByScore(students);
console.log(sortedStudents);
5.1. 실용적 예제 설명
위 코드는 학생의 성적을 기준으로 배열을 정렬하는 방법을 보여줍니다. 각 학생은 이름과 점수 객체로 표현되며, selectionSortByScore 함수를 통해 성적 오름차순으로 정렬되어 결과를 제공합니다.
6. 결론
선택 정렬은 구현이 간단하여 초보자들이 알고리즘의 기본 원리를 이해하는 데 매우 유용한 방법입니다. 그러나 선택 정렬은 O(n²)의 시간 복잡도를 가지고 있기 때문에 대규모 데이터의 경우 효율이 떨어지며, 실제 프로덕션 환경에서는 퀵 정렬, 병합 정렬과 같은 더 나은 알고리즘을 사용하는 것이 좋습니다. 하지만, 선택 정렬을 통해 알고리즘의 기초를 다지는 것은 중요한 학습 과정입니다. 앞으로 코딩 테스트 준비에 이 지식이 많은 도움이 되기를 바랍니다.