배열의 중앙값을 반환하는 함수

배열 array[l…r]의 중앙값을 반환하는 함수를 간단히 구현하였다.

작성한 코드

선택 정렬 알고리즘을 바탕으로 하였다.
단, 정렬이 목적이 아니라 중앙값을 찾는 것이 목적이므로
정렬은 중앙값의 인덱스까지만 수행하면 된다.

// 배열 생성
const array = [];
for (let i = 0; i < 10; i++) { // 10개의 난수 생성
  array[i] = Math.floor(Math.random() * 100 + 1); // 난수 범위: 1~100
}
console.log('array:', array);

// 배열의 두 요소 값을 교환하는 함수
const swap = function (array, x, y) {
  const temp = array[x];
  array[x] = array[y];
  array[y] = temp;
};

// 배열 array[l...r]의 중앙값을 반환하는 함수
const arrayMid = function (array, l, r) {
  const mid = Math.floor((r-l) / 2); // 중앙값이 위치할 인덱스
  let i; let j; let min;

  // 선택 정렬
  for (i = l; i <= l + mid; i++) { // l + mid 까지만 정렬한다.
    min = i;
    for (j = i + 1; j <= r; j++) { // 최소값을 탐색한다.
      if (array[j] < array[min]) min = j;
    }
    if (i !== min) swap(array, i, min); // 최소값을 i의 자리에 삽입한다.
  }
  return array[l + mid]; // 중앙값을 반환한다.
};

// 배열(array[4...8])의 중앙값 출력
const midValue = arrayMid(array, 4, 8);
console.log('array[4...8]의 중앙값:', midValue);

출력 결과

장점

1. 중앙값의 인덱스까지만 정렬하므로
   알고리즘의 수행시간을 조금 더 줄일 수 있다.
2. 전체 배열의 중앙값은 물론이고,
   배열의 부분 범위의 중앙값도 쉽게 구할 수 있다.
   (인덱스를 통해 부분 범위를 지정해주면 된다)

단점

선택정렬을 바탕으로 하였기 때문에,
시간복잡도가 여전히 O(n^^2)으로 효율적인 알고리즘은 아니다.
(다른 정렬 알고리즘 또는 sort 메소드를 사용하면 더 좋을 듯 하다)