[재귀] 병합정렬, 퀵정렬

 

오늘은 정렬 알고리즘에 대해 배우는 날이였다.

강사님이 자꾸 재귀라는 단어를 반복하셔서

파워문과 수포자인 나는 오늘 재귀란 무엇인가에 대해 찾아보는 것으로 시간을 보냈다

 

 

쉽게 말해 자기자신을 다시 호출하는것을 말한다.

마치 마트료시카 인형처럼

 

하나를 열면 또 하나가 있고를 반복해 제일 작은것까지 열면 그걸로 끝나는 마치 마트료시카 인형같은 연산 방법이라고 생각하면된다.

그렇다면 정렬 알고리즘에서의 재귀란
큰 배열 정렬 -> 반으로 쪼개서 작은배열로 만듬 -> ...반복 -> 더이상 쪼개지지않으므로 계산 종료 라 말할수있겠다.

 

재귀는 반드시 기저조건과 재귀호출이 있어야한다.

//기저조건
if (n === 1) return 1;  // 이게 없으면 무한 반복!

//재귀호출
return n + sum(n - 1);  // 점점 작아지면서 기저 조건으로

 

기저조건이란 멈추는 조건,
재귀호출은 자기 자신을 호출하는것을 말한다.

이 두가지는 필수요소이다.

 

반복문 vs 재귀

예시는 같은 결과를 낸다. 반복문이랑 어떻게 다를까?

// 반복문 방식
function sumLoop(n) {
  let total = 0;
  for (let i = 1; i <= n; i++) {
    total += i;
  }
  return total;
}

// 재귀 방식
function sumRecursion(n) {
  if (n === 1) return 1;
  return n + sumRecursion(n - 1);
}

 

재귀는 자기자신을 호출하면서 n이 더이상 연산이 되지않을때까지 return 하게된다.

한마디로 단순 반복문은 1부터 차례대로 더하지만 재귀는 반대로 제일 큰 것부터 1까지 거꾸로 계산된다는 것이다

오늘 배운것 중 선택,버블,삽입 정렬은 단순 반복문(for,while)을 이용해 문제를 풀었지만

병합과 퀵 정렬은 재귀를 이용해야만 하기때문에 재귀에 대한 이해가 꼭 필요하다!

 

 

병합정렬

그럼 재귀의 대표적인 병합정렬 개념에 대해 정리해보자

function mergeSort(arr) { // 재귀로 정렬하는 함수
  // 기저 조건: 배열 크기 1이면 이미 정렬됨
  if (arr.length <= 1) {
    return arr;
  }
  
  // 반으로 쪼개기
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  
  // 양쪽을 각각 정렬하고 합치기(재귀)
  return merge(
    mergeSort(left),
    mergeSort(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, ...left.slice(i), ...right.slice(j)];
}

console.log(mergeSort([7, 3, 9, 1, 5])); // [1, 3, 5, 7, 9]

 

큰 배열 정렬하기 어려우니까 반으로 쪼개서 작은 배열로 만드는 함수를 만들고

작은 배열들을 정렬해서 합치는 함수를 만드는 방식이다

 

 

수업 실습문제

Q. 두 개의 정렬된 배열이 주어지고, 이 두 배열을 합병 정렬을 이용하여 하나의 정렬된 배열로 병합하는 프로그램을 작성하세요.

// 시작 코드
function mergeSortedArrays(arr1, arr2) {
  const result = [];
  let i = 0;  // arr1의 인덱스
  let j = 0;  // arr2의 인덱스
  
  // 두 배열을 비교하면서 작은 값부터 result에 추가
  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i]);
      i++;
    } else {
      result.push(arr2[j]);
      j++;
    }
  }
  
  // 남은 요소들 추가
  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }
  
  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }
  
  return result;

}

// 입력 예시
const array1 = [1, 3, 5, 7, 9]
const array2 = [2, 4, 6, 8]


// 출력 예시
mergeSortedArrays(array1, array2)
//[1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

퀵정렬

function quickSort(arr) {
  // 기저 조건: 배열 크기가 1 이하면 이미 정렬됨
  if (arr.length <= 1) {
    return arr;
  }
  
  // 기준값(pivot): 마지막 요소 선택
  const pivot = arr[arr.length - 1];
  const left = [];   // pivot보다 작은 것
  const right = [];  // pivot보다 큰 것
  
  // pivot 제외하고 왼쪽/오른쪽 분류
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  // 재귀: 왼쪽 정렬 + pivot + 오른쪽 정렬
  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([7, 3, 9, 1, 5]));
// [1, 3, 5, 7, 9]

퀵정렬은 먼저 기준값이란 pivot을 하나 정한다.

그리고 기준값보다 작은것들은 왼쪽, 큰것들은 오른쪽으로 분류시킨다.
양쪽을 재귀로 정렬한 다음에 이어붙이는 정렬방식이다.

 

수업 실습문제

Q. 길이가 N인 정수 배열이 주어집니다. 이 배열에서 K번째로 큰 수를 찾아 출력하는 프로그램을 작성하세요.

// 시작 코드
function quickSortDesc(arr) {
  // 기저 조건: 배열 크기가 1 이하면 이미 정렬됨
  if (arr.length <= 1) {
    return arr;
  }
  
  // 기준값(pivot): 마지막 요소 선택
  const pivot = arr[arr.length - 1];
  const left = [];   // pivot보다 큰 것 (내림차순이니까!)
  const right = [];  // pivot보다 작은 것
  
  // pivot 제외하고 분류
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > pivot) {  // 오름차순과 반대!
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  // 재귀: 큰 것(왼쪽) + pivot + 작은 것(오른쪽)
  return [...quickSortDesc(left), pivot, ...quickSortDesc(right)];

}

// 입력 예시
const k = 2
const descArr = quickSortDesc([7, 3, 9, 1, 5])

// 출력 예시
console.log(descArr[k - 1]) // 7

 

 

솔직히 이렇게 정리해도 머리에 잘들어오진않는데

최대한 문제를 많이 풀어서 익숙해지는 방법밖에는 없는거같다 ㅠㅠ