(퀵/병합) 정렬 개념 정리

정렬의 종류

1. 버블 정렬 (Bubble Sort)

• 가장 기초적인 정렬
• 시간복잡도: O(n²)
• 구현이 쉽지만 비효율적

 2. 선택 정렬 (Seletion Sort)

• 가장 작은/큰 원소를 선택해서 정렬
• 시간복잡도: O(n²)
• 버블정렬보다 실제 교환 횟수가 적음

3. 삽입 정렬 (Insertion Sort)

• 작은 데이터셋에서 효율적
• 시간복잡도: O(n²)
• 거의 정렬된 데이터에서 매우 효율적

4. 퀵 정렬 (Quick Sort)

• 실제로 가장 많이 사용되는 정렬
• 평균 시간복잡도: O(nlogn)
• 분할 정복 방식

5. 병합 정렬 (Merge Sort)

• 안정적인 정렬 알고리즘
• 시간복잡도: O(nlogn)
• 추가 메모리 공간 필요

퀵 정렬과 병합 졍렬을 학습하면 좋은 점

1. 분할 정복(Divide and Conquer) 패러다임의 대표적인 예시
2. 재귀적 문제 해결 능력 향상
   재귀 예시

1. 숫자 카운트 다운

// 숫자를 입력받아 1까지 카운트다운하기
function countdown(n) {
 // 기저 조건(종료 조건)
 if(n <= 0) {
  console.log("끝!");
  return;
 }
 
 console.log(n);
 countdown(n - 1); //재귀 호출
}

// 실행
countdown(5);
// 출력;
// 5
// 4
// 3
// 2
// 1
// 끝!

---------------------------------------------
2. 팩토리얼

// n! 계산하기 (5! = 5 * 4 * 3 * 2 * 1)
function factorial(n) {
 // 기저 조건
 if(n <= 1) return 1;
 
 return n * factorial(n - 1);
}

// 실행 과정 보기
function factorialWithLog(n) {
 console.log(`factorial(${n}) 호출됨`);
 
 if(n <= 1) {
  console.log(`factorial(${n}) = 1 반환`);
  return 1;
 }
 
 const result = n * factorialWithLog(n - 1);
 console.log(`factorial(${n}) = ${result} 반환`);
 return result;
}

// 실행
console.log(factorialWithLog(4));
// 출력;
// factorial(4) 호출됨
// factorial(3) 호출됨
// factorial(2) 호출됨
// factorial(1) 호출됨
// factorial(1) = 1 반환
// factorial(2) = 2 반환
// factorial(3) = 6 반환
// factorial(4) = 24 반환
// 24

---------------------------------------------
3. 피보나치 수열

// 피보나치 수열의 n번째 숫자 구하기
// 0, 1, 1, 2, 3, 5, 8, 13, ...
function fibonacci(n) {
 // 기저 조건
 if(n <= 1) return n;
 
 return fibonacci(n - 1) + fibonacci(n - 2);
}

// 실행 과정 보기 (작은 숫자로 테스트)
function fibonacciWithLog(n, indent = '') {
 console.log(`${indent}fibonacci(${n}) 호출됨`);
 
 if(n <= 1) {
  console.log(`${indent}fibonacci(${n}) = ${n} 반환`);
  return n;
 }
 
 const result = fibonacciWithLog(n - 1, indent + ' ') + fibonacciWithLog(n - 2, indent + ' ');
 console.log(`${indent}fibonacci(${n}) = ${result} 반환`);
 return result;
 
}

// 실행
console.log(fibonacciWithLog(4));

  

    3. 복잡한 문제를 작은 단위로 나누어 해결하는 방법 학습

 

시간 복잡도와 공간 복잡도

 

1. 시간 복잡도

입력 크기에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타내는 척도 -> 얼마나 빠르게 계산 하는가?

• O(1) : 입력 크기와 관계없이 항상 같은 시간 소요

// 배열의 첫 번째 요소 접근
function getFirst(arr) {
 return arr[0];
}

 

• O(n) : 입력 크기에 비례하여 시간 증가 ex) for문

// 배열의 모든 요소 출력
function printAll(arr) {
 for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
 }
}

 

• O(n²) : 입력 크기의 제곱에 비례하여 시간 증가 ex) 2중 for문

// 버블 정렬
function bubbleSort(arr) {
 for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length -1; j++) {
   if (arr[j] > arr[j + 1]) {
    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
   }
  }
 }
}

 

• O(log n) : 입력 크기가 2배가 되어도 시간은 1만큼만 증가 ex) 크기가 8인 배열은 3번, 16인 배열은 4번 실행

// O(log n) 쉬운 예시
let n = arr.length;
while (n > 1) {
 n = Math.floor(n / 2);
}

// 이진 검색 예시
// 이미 정렬된 배열에서 특정 숫자를 찾는 검색
// 절반씩 나눠서 찾음
function binarySearch(arr, target) {
 let left = 0;
 let right = arr.length - 1;
 
 while (letf <= right) {
  let mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) left = mid + 1;
  else right = mid - 1;
 }
 return -1;
}

 

2. 공간 복잡도

알고리즘이 실행될 때 필요한 메모리 공간의 크기를 나타내는 척도 -> 얼마나 메모리 공간을 적게 사용하는가? 

• O(1) : 입력 크기와 관계없이 일정한 메모리만 사용, 추가 변수가 고정된 크기만큼만 필요

// 두 수의 합
function sum(a, b) {
    const result = a + b;  // 변수 하나만 사용
    return result;
}

// 배열에서 최대값 찾기
function findMax(arr) {
    let max = arr[0];  // 변수 하나만 사용
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

 

• O(n) : 입력 크기에 비례하는 메모리 사용, 배열이나 객체를 새로 만드는 경우가 대표적

// 배열 복사
function copyArray(arr) {
    const newArr = [];  // 새로운 배열 생성
    for (let i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    return newArr;
}

// 피보나치 수열 저장
function fibonacci(n) {
    const fib = new Array(n);  // n크기의 배열 생성
    fib[0] = 0;
    fib[1] = 1;
    for (let i = 2; i < n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    return fib;
}

 

• O(n²) : 입력 크기의 제곱만큼 메모리 사용 ex) 2차원 배열

// 2차원 행렬 생성
function createMatrix(n) {
    const matrix = [];
    for (let i = 0; i < n; i++) {
        matrix[i] = new Array(n).fill(0);
    }
    return matrix;
}


createMatrix(3);
// 실행 결과:
[
    [0, 0, 0],  // 3개의 요소
    [0, 0, 0],  // 3개의 요소
    [0, 0, 0]   // 3개의 요소
]
// 총 9개(3×3)의 메모리 공간 필요

createMatrix(4);
// 실행 결과:
[
    [0, 0, 0, 0],  // 4개의 요소
    [0, 0, 0, 0],  // 4개의 요소
    [0, 0, 0, 0],  // 4개의 요소
    [0, 0, 0, 0]   // 4개의 요소
]
// 총 16개(4×4)의 메모리 공간 필요

 

• O(log n) : 입력값이 2배가 되어도 저장 공간은 1만큼만 증가

function divideByTwo(n) {
    let steps = [];  // 각 단계의 숫자를 저장
    
    while (n > 1) {
        steps.push(n);
        n = Math.floor(n / 2);
    }
    
    return steps;
}

// 예시:
console.log(divideByTwo(100));

// n = 100 → [100, 50, 25, 12, 6, 3, 1]  // 7개 저장
// n = 200 → [200, 100, 50, 25, 12, 6, 3, 1]  // 8개 저장
// n = 400 → [400, 200, 100, 50, 25, 12, 6, 3, 1]  // 9개 저장

 

퀵 정렬

1. 퀵 정렬 과정

1. 배열의 중앙 요소를 피벗(pivot)으로 선택
2. 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분할
3. 분할된 왼쪽과 오른쪽 배열에 대해 재귀적으로 퀵 정렬 수행

2. 구현 코드

function quickSort(arr) { // 10
 if (arr.length <= 1) return arr;
 
 const pivot = arr.[Math.floor(arr.length / 2)];
 const left = arr.filter(num => num < pivot);
 const equal = arr.filter(num => num === pivot);
 const right = arr.filter(num => num > pivot);
 
 return [...quickSort(left), ...equal, ...quickSort(right)];
}

 

3. 실행 과정 예시

배열 [4, 2, 7, 1, 9, 3, 8, 6, 5]의 정렬 과정 :

Level 1

전체 배열 : [4, 2, 7, 1, 9, 3, 8, 6, 5]
피벗 : 9
분할 결과 : [4, 2, 7, 1, 3, 8, 6, 5] + [9]

Level 2

왼쪽 배열 : [4, 2, 7, 1, 3, 8, 6, 5]
피벗 : 3
분할 결과 : [2, 1] + [3] + [4, 7, 8, 6, 5]

Level 3

왼쪽 [2, 1]             오른쪽 : [4, 7, 8, 6, 5]
피벗 : 1                피벗 : 8
결과 : [] + [1] + [2]   결과 : [4, 7, 6, 5] + [8]

Level 4

[4, 7, 6, 5]
피벗 : 6
결과 : [4, 5] + [6] + [7]

Level 5

[4, 5]
피벗 : 5
결과 : [4] + [5]

 

4. 시간 복잡도 분석

1) 각 레벨에서의 연산 -O(n)

• 모든 요소는 피벗과 3번씩 비교됨(less, equal, greater)
• n개 요소 -> 3n번의 비교 연산

2) 레벨 수 계산 (log n)

n = 8일 떄 : [1, 2, 3, 4, 5, 6, 7, 8]
8 → 4 → 2 → 1 (3레벨 = log₂8)

n = 16일때 : 
16 → 8 → 4 → 2 → 1 (4레벨 = log₂16)

 

3) 최종 시간 복잡도

• 각 레벨 : 3n번의 비교
• 레벨 수 : log n
• 총 연산 수 : 3n * log n
• 빅오 표기법 : O(n log n)

병합 정렬

1. 병합 정렬이란?

'분할 정복(Divide and Conquer)' 알고리즘을 기반으로 하는 정렬 방법

• 분할(Divide) : 배열을 절반으로 나눔
• 정복(Conquer) : 나눈 부분 배열을 정렬
• 병합(Merge) : 정렬된 부분 배열들을 하나로 병합

2. 병합 정렬의 장점

 1) 안정적인 성능

• 항상 O(n log n)의 시간 복잡도 보장
• 입력 데이터 상태와 무관한 일정한 성능

 2) 안정 정렬(Stable Sort)

• 같은 값의 요소들의 상대적 위치 보존
• 객체 정렬에 효과적

 3) 대용량 데이터 처리에 적합

• 연결 리스트 등 순차적 접근 데이터 구조에 효율적
• 외부 정렬에 자주 사용

3. 구현코드

// 병합 정렬의 메인 함수
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);
 console.log({left, right});
 
 // 병합 전 상태 확인
 const sortedLeft = mergeSort(left);
 console.log({sortedLeft});
 const sortedRight = mergeSort(right);
 console.log({sortedRight});
 
 // 재귀적으로 분할하고 병합
 return merge(sortedLeft, sortedRight);
}

// 두 정렬되 배열을 병합하는 함수
function merge(left, right) {
 const result = [];
 let leftIndex = 0;
 let rightIndex = 0;
 
 // 두 배열을 비교하면서 작은 값을 결과 배열에 추가
 while (leftIndex < left.length && rightIndex < right.length) {
  if (left[leftIndex] < right[rightIndex]) {
   result.push(left[leftIndex]);
   leftIndex++;
  }else {
   result.push(right[rightIndex]);
   rightIndex++;
  }
 }
 
 // 남은 요소들을 결과 배열에 추가
 console.log({
  afterWhileResult: result,
  left,
  right,
  result: result
   .concat(left.slice(leftIndex))
   .concat(right.slice(rightIndex)),
 });
 return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 사용 예시

// 예시 1
const arr1 = [64, 34, 25, 12];
console.log("정렬 전:", arr1);
console.log("정렬 후:", mergeSort(arr1));

// 예시 2
const arr2 = [38, 27, 43, 3, 9, 82, 10, 15];
console.log("정렬 전:", arr2);
console.log("정렬 후:", mergeSort(arr2));

// 예시 3
const arr3 = [64, 34, 25, 12, 22, 11, 90]
console.log("정렬 전:", arr3);
console.log("정렬 후:", mergeSort(arr3));

 

4. 실행 과정 예시

배열 [38, 27, 43, 3, 9, 82, 10, 15]의 정렬 과정:

분할 단계

                [38, 27, 43, 3, 9, 82, 10, 15]
                /                           \
        [38, 27, 43, 3]                [9, 82, 10, 15]
        /             \                  /         \
    [38, 27]      [43, 3]          [9, 82]      [10, 15]
    /     \        /    \           /    \        /     \
  [38]   [27]    [43]   [3]      [9]   [82]    [10]   [15]

 

병합 단계

  [38]   [27]    [43]   [3]      [9]   [82]    [10]   [15]
     \   /          \   /          \   /          \   /
   [27, 38]      [3, 43]         [9, 82]      [10, 15]
        \         /                  \           /
    [3, 27, 38, 43]              [9, 10, 15, 82]
                \                      /
          [3, 9, 10, 15, 27, 38, 43, 82]

 

5. 실행 과정 코드

mergeSort 함수

1) 배열의 길이가 1 이하면 이미 정렬된 상태이므로 반환

if(arr.length <= 1) return arr;

// mergeSort([1]) -> [1]

 

2) 배열을 반으로 나누기

// arr = [64, 34, 25, 12]
const mid = Math.floor(arr.length / 2); // 2
const left = arr.slice(0, mid); // [64, 34]
const right = arr.slice(mid); // [25, 12]

 

3) mergeSort 실행 (재귀적)

const sortedSLeft = mergeSort(left);
// mergeSort([64, 34]);

 

4) 배열을 반으로 나누기

// arr= = [64, 34]
const mid = Math.floor(arr.length / 2); // 1
const left = arr.slice(0, mid); // [64]
const right = arr.slice(mid); // [34]

 

5) mergeSort([64]) 실행 (재귀적)

const sortedLeft = mergeSort(left);
// mergeSort([64]); => sortedLeft는 [64]

 

6) mergeSort([34])

const sortedRight = mergeSort(right);
//mergeSort([34])l => sortedRight는 [34]

 

7) merge([64], [34]) 실행

// 새롭게 정렬할 배열 생성
const result = [];
// 순서대로 확인하기 위해 인덱스 0으로 세팅
let leftIndex = 0;
let rightIndex = 0;

 

8) 왼쪽 배열 혹은 오른쪽 배열 중 하나라도 확인이 끝났는지 체크

while (leftIndex < left.length && rightIndex < right.length) {
}

// 0 < 1 && 0 < 1 -> 통과

 

9) 더 작은 숫자를 result 배열에 추가 및 index 증가

// left[leftIndex] -> [64][0] -> 64
// right[rightIndex] -> [34][0] -> 34
// 64 > 34
// result.push(right[rightIndex]) -> result -> [34]
// rightIndex = 1
if (left[leftIndex] < right[rightIndex]) {
 result.push(left[leftIndex]);
 leftIndex++;
}else {
 result.push(right[rightIndex]);
 rightIndex++;
}

 

10) 왼쪽 배열 혹은 오른쪽 배열 중 하나라도 확인이 끝났는지 체크

while (leftIndex < left.length && rightIndex < right.length) {
}

// 0 < 1 && 1 < 1 -> 통과 X

 

11) 남은 데이터 합치기

result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
// result -> [34]
// result.concat(left.slice(0)) -> [34, 64]
// .concat(right.slice(1)); -> 남은 거 없음

// 결과 = [34, 64]

 

12) 3번의 sortedLeft 완성

const sortedLeft = mergeSort(left);
// sortedLeft = [34, 64]

 

13) sortedRight 실행

const sortedRight = mergeSort(right);
// mergeSort([25, 12]);

 

14) 배열 반으로 나누기

// [25, 12]
const mid = Math.floor(arr.length / 2); // 1
const left = arr.slice(0, mid); // [25]
const right = arr.slice(mid); // [12]

 

15) mergeSort([25]), mergeSort([12]) 실행

if(arr.length <= 1) return arr;
// mergeSort([25]) -> [25] 반환
// mergeSort([12]) -> [12] 반환

 

16) merge([25], [12]) -> [12, 25] 반환

 

17) sortedRight 값

const sortedRight = mergeSort(right);
// sortedRight = [12, 25]

 

18) merge([34, 64], [12, 25])

function merge(left, right) {
 const result = [];
 let leftIndex = 0;
 let rightIndex = 0;
 
 // 두 배열을 비교하면서 작은 값을 결과 배열에 추가
 while (leftIndex < left.length && rightIndex < right.length) {
  if (left[leftIndex] < right[rightIndex]) {
   result.push(left[leftIndex]);
   leftIndex++;
  }elst {
   result.push(right[rightIndex]);
   rightIdex++;
  }
 }
 
 return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// 1. 34와 12 비교 -> result = [12]
// 2. 34와 25 비교 -> result = [12, 25]
// 3. rightIndex (2) < right.length (2) -> while문 벗어남
// 4. concat으로 합치기 -> result  [12, 25, 34, 64]

 

6. 시간 복잡도 분석

분할 단계 (log n)

• 배열이 반으로 계속 나뉨
• 8개 요소: 8 → 4 → 2 → 1 (3단계 = log₂8)
• 16개 요소 : 16 → 8 → 4 → 2 → 1 (4단계 = log₂16)

function mergeSort(arr) {
    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));
}

 

 

병렬 단계 (n)

각 레벨에서 모든 요소를 비교하며 병합

n개의 요소를 비교하는 작업 수행

function merge(left, right) {
    const result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    // 이 while 루프는 O(n)
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
    
    return result
        .concat(left.slice(leftIndex))
        .concat(right.slice(rightIndex));
}

 

전체 시간 복잡도 계산

• 레벨 수 : O(log n) - 분할 횟수
• 각 레벨의 작업량 : O(n) - 병합 시 비교 연산
• 따라서, O(n) × O(log n) = O(n log n)

7. 공간 복잡도

• 임시 배열 필요 : O(n)
• 재귀 호출 스택 : O(log n)
• 총 공간 복잡도 : O(n)