배열(Array)은 자바스크립트에서 가장 자주 사용되는 데이터 구조 중 하나입니다. 중간 값(median)은 배열의 요소 중 가운데 값을 의미하며, 정렬된 배열의 경우에는 홀수 개의 요소일 경우 정확하게 중간 값이 됩니다. 이번 글에서는 자바스크립트에서 배열의 중간 값을 구하는 방법에 대해 알아보겠습니다.
1. 정렬된 배열의 중간 값 구하기
정렬된 배열에서는 중간 값은 바로 접근이 가능하므로 쉽게 구할 수 있습니다. 배열의 길이(n)가 홀수인 경우, 중간 인덱스는 (n-1) / 2가 됩니다. 이를 이용하여 배열의 중간 값을 가져올 수 있습니다. 다음은 정렬된 배열에서 중간 값을 가져오는 예시입니다.
const sortedArray = [1, 3, 5, 7, 9];
const middleIndex = (sortedArray.length - 1) / 2;
const middleValue = sortedArray[Math.floor(middleIndex)];
console.log(`중간 값은 ${middleValue}입니다.`);
// 출력: 중간 값은 5입니다.
2. 정렬되지 않은 배열의 중간 값 구하기
정렬되지 않은 배열의 경우, 중간 값에 접근하기 위해서는 다른 방법을 사용해야 합니다. 가장 일반적인 방법은 배열을 정렬한 후에 중간 값을 구하는 것입니다. 그러나 이 방법은 성능적으로 비효율적일 수 있으므로 다른 방법을 고려해야 합니다.
const unsortedArray = [9, 3, 7, 1, 5];
const sortedArray = unsortedArray.sort((a, b) => a - b);
const middleIndex = (sortedArray.length - 1) / 2;
const middleValue = sortedArray[Math.floor(middleIndex)];
console.log(`중간 값은 ${middleValue}입니다.`);
// 출력: 중간 값은 5입니다.
위의 코드는 정렬되지 않은 배열을 정렬한 후 중간 값을 구하는 방법입니다. 하지만 이는 배열을 정렬하는 데에 시간이 추가적으로 소요되므로 성능 저하를 야기할 수 있습니다.
3. Quickselect 알고리즘을 사용한 중간 값 구하기
Quickselect 알고리즘은 배열에서 특정 순서의 요소를 빠르게 찾는 알고리즘입니다. 이 알고리즘은 평균적으로 O(n)의 시간 복잡도를 가지며, 정렬된 배열이 아니어도 중간 값을 빠르게 구할 수 있습니다. 다음은 Quickselect 알고리즘을 사용하여 중간 값을 구하는 예시입니다.
function quickselect(arr, left, right, k) {
if (left === right) {
return arr[left];
}
const pivotIndex = partition(arr, left, right);
if (k === pivotIndex) {
return arr[k];
} else if (k < pivotIndex) {
return quickselect(arr, left, pivotIndex - 1, k);
} else {
return quickselect(arr, pivotIndex + 1, right, k);
}
}
function partition(arr, left, right) {
const pivot = arr[right];
let i = left - 1;
for (let j = left; j <= right - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, right);
return i + 1;
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
const unsortedArray = [9, 3, 7, 1, 5];
const middleIndex = Math.floor((unsortedArray.length - 1) / 2);
const middleValue = quickselect(unsortedArray, 0, unsortedArray.length - 1, middleIndex);
console.log(`중간 값은 ${middleValue}입니다.`);
// 출력: 중간 값은 5입니다.
위의 코드는 Quickselect 알고리즘을 사용하여 정렬되지 않은 배열의 중간 값을 구하는 예시입니다. 이 알고리즘은 배열을 정렬하지 않고도 빠르게 중간 값을 찾을 수 있으며, 성능적으로 효율적입니다.
자바스크립트에서 배열의 중간 값을 구하는 방법은 다양하지만, 위에서 소개한 방법들은 그 중에서도 가장 일반적으로 사용되는 방법입니다. 알고리즘 선택은 배열의 크기와 정렬 여부, 성능 요구사항 등을 고려하여 결정해야 합니다.