정렬(Sorting)이란?
정렬이란 데이터를 특정한 순서대로 배치하는 과정이다. 일반적으로 숫자 또는 문자열을 값에 따라 정렬한다. 예를 들어, 학생을 키 순서대로 정렬하거나, 도시를 인구수 기준으로 정렬할 수 있다.
다음과 같은 배열이 있다고 가정하자.
A = [5, 2, 8, 14, 1, 16];
이를 숫자 크기 순서로 정렬하면 다음과 같다.
A = [1, 2, 5, 8, 14, 16];
정렬 알고리즘은 시간 복잡도와 메모리 사용량에 따라 차이가 있다. 여기서는 대표적인 정렬 알고리즘을 살펴본다.
1. 선택 정렬 (Selection Sort)
아이디어: 배열에서 가장 작은 원소를 찾아 첫 번째 위치와 교환하는 작업을 반복한다.
JavaScript 코드:
function selectionSort(A) {
let n = A.length;
for (let k = 0; k < n; k++) {
let minIndex = k;
for (let j = k + 1; j < n; j++) {
if (A[j] < A[minIndex]) {
minIndex = j;
}
}
[A[k], A[minIndex]] = [A[minIndex], A[k]]; // swap
}
return A;
}
시간 복잡도: O(n²) (이중 반복문 사용)
2. 카운팅 정렬 (Counting Sort)
아이디어: 원소의 등장 횟수를 배열에 저장한 후, 카운트 배열을 기반으로 정렬한다.
JavaScript 코드:
function countingSort(A, k) {
let n = A.length;
let count = new Array(k + 1).fill(0);
for (let i = 0; i < n; i++) {
count[A[i]] += 1;
}
let p = 0;
for (let i = 0; i <= k; i++) {
for (let j = 0; j < count[i]; j++) {
A[p++] = i;
}
}
return A;
}
시간 복잡도: O(n + k) (단, k 값이 클 경우 메모리 사용량이 많아질 수 있음)
3. 합병 정렬 (Merge Sort)
아이디어: 배열을 절반씩 나눈 후, 각각 정렬하고 병합하는 방식이다.
JavaScript 코드:
function mergeSort(A) {
if (A.length <= 1) return A;
let mid = Math.floor(A.length / 2);
let left = mergeSort(A.slice(0, mid));
let right = mergeSort(A.slice(mid));
return merge(left, right);
}
function merge(left, right) {
let result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
시간 복잡도: O(n log n) (분할 + 병합 과정이 로그 단위로 진행됨)
4. 내장 정렬 함수 (Built-in Sorting)
JavaScript는 기본적으로 O(n log n) 복잡도의 정렬 함수를 제공한다.
JavaScript 코드:
A.sort((a, b) => a - b);
이 방식은 정렬 속도가 빠르고 코드가 간결하기 때문에 대부분의 경우 내장 함수를 활용하는 것이 좋다.
5. 배열 내 서로 다른 값의 개수 구하기
배열 A에 있는 서로 다른 값의 개수 를 구하는 문제를 해결해보자.
O(n log n) (정렬 후 비교)
JavaScript 코드:
function distinct(A) {
if (A.length === 0) return 0;
A.sort((a, b) => a - b);
let result = 1;
for (let k = 1; k < A.length; k++) {
if (A[k] !== A[k - 1]) {
result++;
}
}
return result;
}
시간 복잡도: O(n log n) (정렬 후 한 번 순회)
반응형
댓글