반응형
선택 정렬 소개
선택 정렬은 정렬 알고리즘 중 하나로, 버블 정렬과 비슷하지만 큰 값을 배열 끝에 위치시키는 대신 작은 값을 한 번에 하나씩 위치에 배열하는 방식입니다.
선택 정렬 동작 방식
- 첫 번째 요소를 가장 작은 값으로 저장합니다.
- 이 요소를 배열의 다음 요소와 비교하여 더 작은 수를 찾을 때까지 계속합니다.
- 더 작은 수를 찾으면, 그 작은 수를 새로운 "최소값"으로 지정하고 배열의 끝까지 계속합니다.
- "최소값"이 처음 시작한 값(인덱스)이 아닌 경우, 두 값을 교환합니다.
- 배열이 정렬될 때까지 다음 요소로 이 과정을 반복합니다.
선택 정렬 의사 코드
{for i from 0 to n-1:
minIndex = i
for j from i+1 to n:
if array[j] < array[minIndex]:
minIndex = j
if minIndex != i:
swap(array[i], array[minIndex])}
선택 정렬 구현
다음은 ES2015(JavaScript) 버전의 선택 정렬 구현 예제입니다.
function selectionSort(arr) {
const swap = (arr, idx1, idx2) =>
([arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);
for (let i = 0; i < arr.length; i++) {
let lowest = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[lowest]) {
lowest = j;
}
}
if (i !== lowest) {
swap(arr, i, lowest);
}
}
return arr;
}
선택 정렬 빅오 복잡도
선택 정렬의 시간 복잡도는 O(n^2)입니다. 이는 이중 for 루프를 사용하여 배열의 각 요소를 비교하기 때문입니다. 선택 정렬은 다음과 같은 점에서 버블 정렬보다 효율적입니다.
- 스왑 횟수: 선택 정렬은 각 반복이 끝날 때 한 번만 스왑을 수행합니다. 이는 불필요한 스왑을 줄여줍니다.
- 단순성: 구현이 간단하여 이해하기 쉽습니다.
공간 복잡도
선택 정렬은 추가적인 배열을 사용하지 않고 주어진 배열 내에서 정렬을 수행하기 때문에 공간 복잡도는 O(1)입니다.
선택 정렬의 장점과 단점
장점
- 구현이 간단하고 이해하기 쉽습니다.
- 데이터의 양이 적을 때는 효율적입니다.
- 주어진 배열 내에서 정렬을 수행하기 때문에 추가 메모리가 필요하지 않습니다.
단점
- 시간 복잡도가 O(n^2)이기 때문에 대량의 데이터에 대해서는 비효율적입니다.
- 안정 정렬이 아닙니다. (같은 값의 요소들이 정렬 후에도 입력 순서가 유지되지 않을 수 있습니다.)
선택 정렬의 활용
선택 정렬은 데이터의 양이 적고, 간단한 정렬을 필요로 하는 경우에 유용합니다.
선택 정렬은 단순하지만, 알고리즘의 기본 개념을 이해하는 데 도움이 됩니다. 더 복잡한 알고리즘을 배우기 전에 선택 정렬을 이해하고 구현해 보는 것이 좋습니다.
반응형
'Algorithm > Theory' 카테고리의 다른 글
버블 정렬, 선택 정렬, 삽입 정렬 비교 (0) | 2024.07.19 |
---|---|
삽입 정렬 (Insertion Sort) (0) | 2024.07.19 |
버블 정렬 (Bubble Sort) 정렬 알고리즘 소개 (0) | 2024.07.14 |
검색 알고리즘 (0) | 2024.07.10 |
(더 어려운) 재귀 연습 문제 1부 (0) | 2024.07.10 |