JavaScript로 배열의 홀수와 짝수 요소 분리 정렬하기

문제 개요

정수(Integer)로 이루어진 배열을 입력받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열 안의 모든 홀수를 앞쪽에, 모든 짝수를 뒤쪽에 배치하도록 배열을 정렬합니다.

홀수끼리 또는 짝수끼리의 상대적인 순서는 중요하지 않으며, 단지 모든 홀수가 어떤 짝수보다도 먼저 위치하기만 하면 됩니다.

입력 예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [0, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 1];

위 배열을 정렬하면 결과는 다음과 같은 형태가 됩니다. 홀수가 짝수보다 앞에 오기만 하면 되므로 여러 가지 올바른 답이 존재할 수 있습니다.

const output = [
  1, 3, 5, 7, 9,
  1, 0, 2, 4, 6,
  8, 0
];

알고리즘 접근 방식

효율적인 해결 방법 중 하나는 삽입 정렬(insertion sort)과 유사하게 배열을 순회하면서 인접한 두 원소를 비교하는 것입니다. 짝수 뒤에 홀수가 있는 경우 두 원소의 자리를 교환(swap)하여 홀수를 앞쪽으로 밀어냅니다. 이렇게 하면 별도의 추가 배열 없이 제자리(in-place)에서 정렬을 수행할 수 있다는 장점이 있습니다.

구현 코드

const arr = [0, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 1];

const sortOddEven = (arr = []) => {
  let i = 0, j, temp;
  while (i < arr.length - 1) {
    j = i;
    // 현재 원소가 짝수이고 다음 원소가 홀수라면 자리를 교환
    while (!(arr[j] % 2) && arr[j + 1] % 2) {
      temp = arr[j];
      arr[j] = arr[j + 1];
      arr[j + 1] = temp;
      if (!j) {
        break;
      };
      j--;
    };
    i++;
  };
};

sortOddEven(arr);
console.log(arr);

실행 결과

위 코드를 실행하면 콘솔에 다음과 같이 출력됩니다.

[
  1, 3, 5, 7, 9,
  1, 0, 2, 4, 6,
  8, 0
]

대안: filter()를 활용한 간결한 방법

제자리 정렬이 꼭 필요하지 않다면, 배열의 filter() 메서드를 사용해 훨씬 간결하게 해결할 수도 있습니다.

const arr = [0, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 1];

const result = [
  ...arr.filter(n => n % 2 !== 0), // 홀수
  ...arr.filter(n => n % 2 === 0)  // 짝수
];

console.log(result);
// [1, 3, 5, 7, 9, 1, 0, 2, 4, 6, 8, 0]

filter() 방식은 코드가 직관적이고 읽기 쉽다는 장점이 있습니다. 다만 원본 배열 외에 새로운 배열을 생성하기 때문에 메모리를 추가로 사용합니다. 음수가 포함된 배열에서도 n % 2 !== 0 조건을 사용하면 홀수를 정확히 판별할 수 있으니 참고하세요. 성능과 메모리 상황에 맞게 두 방식 중 적절한 것을 선택해 사용하면 됩니다.