분할정복과 병합정렬(merge sort), 퀵 정렬(quick sort)

분할 정복과 고급정렬

분할 정복

• 문제를 나눌 수 없을 때까지 나누어 각각을 풀고 다시 합병하여 문제의 답을 얻는 알고리즘
• 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식
  • 일반적으로 재귀함수로 구현된다.
• 문제를 잘게 쪼갤 때 부분 문제들은 서로 중복되지 않는다.
  • 병합 정렬, 퀵 정렬 등

고급 정렬

1) 병합정렬

리스트를 절반으로 계속해서 자른다.

더이상 나눌 수 없을 만큼 나뉘었다면, 값을 비교 후 정렬해가며 병합한다.

리스트를 계속해서 나누는 함수와 나뉜 리스트를 정렬하며 합치는 함수를 만든다.

구현

// 병합 정렬
const mergeSort = arr => {
  // 재귀함수 종료 조건
  if (arr.length <= 1) {
    return arr;
  }

  /** 1) 주어진 배열 나누기 */
  const middle = parseInt(arr.length / 2, 10); // 주어진 배열의 가운데 인덱스 구하기
  const left = mergeSort(arr.slice(0, middle)); // 첫 번째 요소부터 middle번째 요소 전까지 담긴 배열
  const right = mergeSort(arr.slice(middle, arr.length)); // middle번째 요소부터 마지막 요소까지 담긴 배열

  /** 2) 나뉜 값들 합치기 */
  const result = []; // 정렬된 요소들이 담길 배열
  let leftIndex = 0; // 왼쪽 배열 인덱스 초기화
  let rightIndex = 0; // 오른쪽 배열 인덱스 초기화

  // 2-1) left와 right 둘 다 있을 때
  while (left.length > leftIndex && right.length > rightIndex) {
    if (left[leftIndex] > right[rightIndex]) {
      result.push(right[rightIndex]); // 둘을 비교하여 작은 값을 결과에 집어넣는다.
      rightIndex++; // 결과에 값을 집어넣은 쪽은 다음 요소로 이동한다.
    } else {
      result.push(left[leftIndex]);
      leftIndex++;
    }
  }

  // 2-2) left만 데이터가 남았을 때
  while (left.length > leftIndex) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  // 2-3) right만 데이터가 남았을 때
  while (right.length > rightIndex) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
};
// 테스트
let example = [];
for (let i = 0; i < 10; i++) {
  // 1~1000 범위의 난수
  const item = Math.floor(Math.random() * 1000 + 1);
  example.push(item);
}
console.log(mergeSort(example));

2) 퀵 정렬 quick sort

기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다.

각 왼쪽 오른쪽은 재귀함수를 사용해서 위 작업을 반복한다.

함수는 왼쪽, pivot, 오른쪽을 리턴한다.

구현

만약 리스트 내 요소의 개수가 한 개면 리스트 리턴

그렇지 않으면 리스트 맨 앞의 데이터를 기준점으로 놓기

left와 right 변수를 만들고 맨 앞의 데이터를 뺀 나머지 데이터를 기준점과 비교하여 기준점보다 작으면 left에 넣고 크면 right에 넣는다.

const quickSort = arr => {
  // 재귀함수 종료 조건
  if (arr.length <= 1) {
    return arr;
  }
  // 배열 준비
  const pivot = arr[0]; // 기준점
  const left = []; // 기준점보다 작은 값
  const right = []; // 기준점보다 큰 값
  // 기준점 다음 요소부터 정렬 시작
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else if (arr[i] > pivot) {
      right.push(arr[i]);
    }
  }

  return [...quickSort(left), ...[pivot], ...quickSort(right)];
};

const sorted = quickSort([123, 234, 236, 5, 2, 1, 7, 8, 9, 11, 345]);
console.log(sorted);

마지막 배열을 return 하는 방법은 Array.prototype.concat()을 이용하거나 ...spread 기법을 사용할 수 있다.

// Array.prototype.concat() 메소드로 배열 이어붙이기
return quickSort(left).concat(pivot, quickSort(right));

// ...spread 이용
return [...quickSort(left), ...pivot, ...quickSort(right)];