[바미] - 정렬 알고리즘 정리 (JS)

Quick Sort (퀵 정렬)

피벗(pivot)을 기준으로 배열을 두 부분으로 나누고, 각각을 재귀적으로 정렬하는 분할 정복 알고리즘.

동작 방식

• 배열에서 피벗을 하나 선택
• 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
• 각 부분 배열에 대해 재귀적으로 다시 정렬
• 정렬된 하위 배열을 합쳐 최종 결과 생성

시간 복잡도

• 평균: O(n log n)
• 최악: O(n^2) (피벗이 항상 최소/최대일 경우)

특징

• 빠르다, 특히 대부분의 실제 상황에서
• 제자리 정렬 (in-place, 추가 메모리 거의 없음)
• 불안정 정렬 (같은 값의 원소 순서 보장 안 됨)

실무에선?

• 대용량 데이터 정렬
• JavaScript의 V8 엔진 (내부적으로 QuickSort 사용)
• 성능이 중요한 백엔드 API에서 자주 활용

코드

// Quick Sort
function quickSort(arr, left = 0, right = arr.length - 1, depth = 0) {
    // 재귀의 깊이에 따라 들여쓰기기
    const pad = ' '.repeat(depth);

    console.log(`${pad}quickSort(left: ${left}, right: ${right}), 호출, 배열 = [${arr}]`);

    // 종료 조건 - 더 이상 쪼갤 게 없으면 종료
    if (left >= right) {
        console.log(`${pad}구간 크기 <= 1 -> 정렬 끝`);
        return arr;
    }

    // 가운데 값을 피벗으로 지정.
    const pivotIndex = Math.floor((left + right) / 2);
    const pivot = arr[pivotIndex];
    console.log(`${pad}피벗 = arr[${pivotIndex}] = ${pivot}`);
    let leftValue = left;
    let rightValue = right;

    // 피벗을 기준으로 작은 값과 큰 값을 교환
    while (leftValue <= rightValue) {
        // 왼쪽에서 피벗보다 큰 값을 찾음
        while (arr[leftValue] < pivot) leftValue++;
        // 오른쪽에서 피벗보다 작은 값을 찾음
        while (arr[rightValue] > pivot) rightValue--;
        // 왼쪽과 오른쪽 값을 교환
        if (leftValue <= rightValue) {
            console.log(`${pad} swap arr [${leftValue}] = ${arr[leftValue]} <-> arr [${rightValue}] = ${arr[rightValue]}`);
            // 값 교환
            [arr[leftValue], arr[rightValue]] = [arr[rightValue], arr[leftValue]];
            // 인덱스 증가/감소
            leftValue++;
            rightValue--;
        }
    }

    console.log(`${pad}파티셔닝 완료 => [${arr}], 나뉜 두 구간 : left = [${left}...${rightValue}], right = [${leftValue}...${right}]`);
    // 왼쪽 파티션 재귀
    if (left < rightValue) quickSort(arr, left, rightValue); 
    // 오른쪽 파티션 재귀
    if (leftValue < right) quickSort(arr, leftValue, right);

    return arr;
}

const arr = [5, 2, 9, 1, 5, 6];

console.log('퀵 정렬:', quickSort([...arr]));

흐름

[5 2 9 1 5 6]     pivot=9
 └─<—partition—> [5 2 6 1 5]  |  [9]

[5 2 6 1 5]       pivot=6
 └─<—partition—> [5 2 5 1]    |  [6]

[5 2 5 1]         pivot=2
 └─<—partition—> [1] | [5 5]

[5 5]             pivot=5
 └─<—partition—> [5] | [5]

Pivot 으로 배열을 “왼쪽 < pivot < 오른쪽” 두 덩어리로 나누고, 각 덩어리를 다시 같은 방식으로 쪼개 나가며길이 0·1인 구간이 되면 재귀가 멈춤.

이 과정을 반복하면서 제자리에서(추가 배열 없이) 전체가 정렬됨.

Merge Sort (병합 정렬)

배열을 반으로 나눈 뒤 각각을 정렬하고, 다시 병합하면서 전체를 정렬하는 방식

동작 방식

1. 배열을 절반씩 나눔
2. 각 절반을 재귀적으로 정렬
3. 두 개의 정렬된 배열을 병합(merge)

시간 복잡도

• 모든 경우 : O(n log n) → 항상 안정적인 성능

특징

• 안정 정렬 (같은 값의 순서 유지)
• 추가 메모리 필요 (O(n) 공간)
• 재귀 기반 구현 → 스택 메모리 고려 필요

실무 예시

• 병렬 처리에 적합 (각 조각을 나눠서 독립 정렬 후 병합)
• 외부 정렬: 메모리에 모두 올릴 수 없는 데이터 (예: 파일 기반 정렬)
• 큰 로그 파일 정렬 등

코드

// 병합 정렬
function mergeSort(arr) {
    // 쪼갤 게 없으면 그대로 반환
    if (arr.length <= 1) return arr;

    // 배열을 반으로 쪼개기
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    return merge(left, right);
}

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++;
        }
    }

    // 남은 원소 추가
    return result.concat(left.slice(leftIndex), right.slice(rightIndex));
}

const arr = [5, 2, 9, 1, 5, 6];

console.log('병합 정렬:', mergeSort([...arr]));

Heap Sort (힙 정렬)

힙 자료구조(완전 이진 트리)를 이용해 가장 큰 값을 뽑아내며 정렬하는 방식

동작 방식

1. 배열을 최대 힙으로 구성
2. 루트(최대값)를 끝으로 보내고, 다시 힙으로 정리
3. 반복해서 정렬 완료
4. 제일 큰 값을 하나씩 뒤부터 채우는 방식으로 정렬하는 알고리즘

시간 복잡도

• 항상: O(n log n)

특징

• 제자리 정렬 (추가 공간 없음)
• 불안정 정렬
• heapify() 연산 덕분에 우선순위 처리에 유리

실무 예시

• 우선순위 큐 구현
• 상위 N개 값 추출 (Top-K)
• 실시간 정렬 (스트림 기반 데이터 정렬 등)

코드

// 힙 정렬
function heapSort(arr) {
    //최대 힙으로 변환 -> 부모 >= 자식 구조가 되도록 만듦
    buildMaxHeap(arr);

    // 힙 정렬 시작 -> 배열의 끝에서부터 하나씩 정렬된 위치로 보낸다.
    for (let end = arr.length - 1; end > 0; end --) {
        // 루트 <-> 끝 원소로 교환
        [arr[end], arr[0]] = [arr[0], arr[end]];
        // 줄어든 힙(0 ~ end-1)에서 다시 정렬
        heapify(arr, 0, end);
    }

    return arr;
}

function buildMaxHeap(arr) {
    // 마지막 부모 노드부터 역순으로 heapify()를 호출.
    // 자식 노드들은 이미 힙이기 때문.(leaf는 정리할 필요가 없음.)
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        // 각 부모 노드마다 heapify()를 호출해서 전체를 힙 구조로 바꾼다.
        heapify(arr, i, arr.length);
    }
}

// heapify 함수 - 부모 - 자식 비교 후 내려보내기
// 힙 조건 (부모 >= 자식)이 깨졌는지 확인하고, 필요한 경우 내려가며 정리한다.
function heapify(arr, index, heapSize) {
    // index = 현재 부모 위치
    // heapSize = 힙 범위 (정렬된 부분은 제외)

    // 현재 노드의 왼쪽, 오른쪽 자식 인덱스를 구한다.
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    // 가장 큰 값을 가진 인덱스를 임시로 저장할 변수수
    let largest = index;

    // 왼쪽 또는 오른쪽 자식이 현재 노드보다 크면, 그 자식이 가장 크다고 판단.
    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;

    // 가장 큰 값이 자식이라면면
    if (largest !== index) {
        [arr[index], arr[largest]] = [arr[largest], arr[index]]; // 값 교환
        heapify(arr, largest, heapSize); // 자식 노드에서 다시 힙 구성
    }
}

const arr = [5, 2, 9, 1, 5, 6];

console.log('힙 정렬:', heapSort([...arr]));

Timsort (팀정렬)

Merge Sort + Insertion Sort를 조합한 하이브리드 정렬 알고리즘 실제 대부분의 언어에서 사용하는 최적화 정렬 방식.

동작 방식

1. 작은 조각(run)들은 삽입 정렬로 정렬
2. 큰 조각(run)들은 병합 정렬 방식으로 정렬

이미 어느 정도 정리된 데이터는 그대로 두고, 나머지만 정리한다.

• 실제 데이터는 완전히 섞여 있지 않고 부분적으로 정렬된 경우가 많음
• 팀 정렬은 정렬된 흐름(run)을 감지해서 삽입 정렬로 처리하고, 그 후 병합 정렬 방식으로 전체를 합쳐줌

이미 정리된 문서 뭉치를 정리한다 가정할 때

작은 조각은 손으로 정리(삽입)

큰 덩어리는 파일로 병합(병합)

시간 복잡도

• 평균, 최악 : O(n log n)
• 최선: O(n) (이미 거의 정렬된 경우)

특징

• 안정 정렬
• 실제 데이터에서 매우 빠름 (정렬된 패턴을 잘 활용함)
• 매우 실용적이고 효율적
• 구현이 복잡해서 직쩝 짜기 어려움.

실무 예시

• Java의 Arrays.sort(), Python의 sorted(), Chrome의 V8 엔진
• 브라우저 Array.prototype.sort() 대부분 Timsort 기반
• 거의 모든 실무 프론트/백엔드 정렬 코드

코드

//삽입 정렬 함수 : 작은 조각(run)을 정렬할 때 사용
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let key = arr[i];
        let j = i - 1;

        // key보다 큰 값을 오른쪽으로 한 칸식 밀어줌
        while ( j >= left && arr[j] > key) {
            // 큰 값을 오른쪽으로 밀기
            arr[j + 1] = arr[j];
            j--;
        }
        // 자리를 찾았으면, key 값을 삽입입
        arr[j + 1] = key;
    }
}
//병합 함수 - 정렬된 두 구간을 하나로 합치기
function merge(arr, l, m, r) {
    // 왼쪽과 오른쪽 배열을 따로 복사해서 저장
    const left = arr.slice(l, m + 1); // 1 부터 mid까지
    const right = arr.slice(m + 1, r + 1); // mid + 1 부터 right까지
    // i : left, j: right, k: 원래 배열의 인덱스
    let i = 0, j = 0, k = l;

    // 두 배열을 비교하여 더 작은 값을 원래 배열에 넣는다.
    while (i < left.length && j < right.length) {
        arr[k++] = (left[i] <= right[i]) ? left[i++] : right[j++];
    }

    // 남은 값들을 복사 -> 왼쪽 또는 오른쪽 중 하나는 먼저 끝나기 때문에 복사.
    while (i < left.length) arr[k++] = left[i++];
    while (j < right.length) arr[k++] = right[j++];
}
// 팀소트 함수
function timSort(arr) {
    const RUN = 32; // 최소 덩어리 크기(run). 삽입 정렬할 단위.
    const n = arr.length;

    // 먼저 모든 run(작은 조각)을 삽입 정렬로 정렬
    for (let i = 0; i < n; i += RUN) {
        const end = Math.min(i + RUN - 1, n - 1); // 범위를 벗어나지 않도록 
        insertionSort(arr, i, end); // run 단위 정렬
    }

    // 그 다음 병합 정렬처럼 run들을 2개씩 합치며 정렬
    for (let size = RUN; size < n; size = 2 * size) {
        // 두 개의 run을 합치며 정렬
        for (let left = 0; left < n; left += 2 * size) {
            const mid = Math.min(left + size - 1, n - 1); // 첫 번째 run 끝
            const right = Math.min(left + 2 * size - 1, n - 1); // 두 번째 run 끝

            // 두 run을 병합
            if (mid < right) {
                merge(arr, left, mid, right);
            }
        }
    }
    // 정렬된 배열 반환
    return arr;
}

const arr = [5, 2, 9, 1, 5, 6];

console.log('팀 정렬:', timSort([...arr]));

Counting Sort / Radix Sort

Counting Sort

• 개념

  정수값들의 빈도수를 기반으로 정렬하는 방식 (비교 없이 정렬)

  Ex: [100, 90, 80, 90]

  각 숫자 몇 개 있는지 세면 [80:1, 90:2, 100:1]

  이걸 순서대로 늘어놓으면 [80, 90, 90, 100]

  그 대신 정수일 때만 쓸 수 있음.

• 시간 복잡도

  O(n + k) (n : 데이터 수, k: 값의 범위)

• 특징:

  • 안정 정렬
  • 비교 연산이 없음
  • 정수만 가능 / 값 범위가 작을 때만 유리

실무 예시

• 점수 정렬, 나이대 통계 등 범위가 작고 고정된 정수 정렬에 적합.

코드

// counting sort
function countingSort(arr) {
    // 가장 큰 값을 찾기
    const max = Math.max(...arr);
    // 카운팅 배열 생성 -> 각 숫자의 빈도를 저장
    const count = new Array(max + 1).fill(0);

    // 각 숫자의 빈도를 계산
    for (let num of arr) {
        count[num]++;
    }

    // 개수를 기반으로 정렬된 결과 만들기
    let sorted = [];

    for (let i = 0; i <= max; i++) {
        while (count[i]-- > 0) {
            sorted.push(i); // i를 count[i]만큼 넣음.
        }
    }

    return sorted;
}

const arr = [5, 2, 9, 1, 5, 6];

console.log('카운팅 정렬:', countingSort([...arr]));

Radix Sort

각 자릿수(1의 자리 → 10의 자리 …)를 기준으로 자리별로 정렬하는 방식

Ex : [170, 45, 75, 90, 802, 24, 2, 66]

1. 1의 자리로 정렬 : [802, 2, 24, 45, 75, 66, 170, 90]
2. 10의 자리로 정렬
3. 100의 자리로 정렬
4. 최종 정렬이 완료

• 시간 복잡도

  O(nk) (n : 데이터 수, k: 최대 자릿수)

• 특징

  • 안정 정렬
  • 숫자 기반 데이터에 매우 빠름
  • 문자 정렬도 가능 (특정 조건하에서)
  • 소수/음수는 추가 처리가 필요.
  • 범용성이 낮다.

• 실무 예시

  • 우편번호, 상품코드, 로그 ID 등의 고정 길이 숫자 정렬 (정수로 이루어진 고정폭 데이터)
  • 데이터베이스 내부 정렬
  • 대용량 로그 / 센서 데이터 전처리

코드

// 특정 자릿수를 추출하는 함수
function getDigit(num, place) {
    return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

/**
 * 배열에서 가장 큰 숫자의 자릿수 길이 구하는 함수
 * @param {*} arr 배열
 * @returns 가장 큰 숫자의 자릿수 길이
 * 예: [12, 400, 7] -> 400은 3자리이므로 maxDigits = 3
 */
function getMaxDigits(arr) {
    return Math.max(...arr.map(num => num.toString().length));
}

// radix sort 함수
function radixSort(arr) {
    const maxDigits = getMaxDigits(arr); // 최대 자릿수
    // 각 자릿수에 대해 정렬(1의 자리부터 ~ 최대 자릿수까지)기준으로 정렬을 반복복
    for (let k = 0; k < maxDigits; k++) {
        // 각 자릿수에 대한 버킷(0~9) 초기화
        const buckets = Array.from({ length: 10 }, () => []);
        // 각 숫자를 해당 자릿수에 맞는 버킷에 분배
        // 예를 들어 k=0 -> 1의 자리를 기준
        //          k=1 -> 10의 자리를 기준
        //          k=2 -> 100의 자리를 기준
        // 숫자 321 -> 1번 버킷
        // 숫자 305 -> 5번 버킷
        for (let i = 0; i < arr.length; i++) {
            const digit = getDigit(arr[i], k);
            buckets[digit].push(arr[i]);
        }
        // 버킷에 정렬된 숫자를 다시 배열에 복사
        arr = [].concat(...buckets);
    }

    return arr;
}

const arr = [5, 2, 9, 1, 5, 6];
console.log('기수 정렬:', radixSort([...arr]));

정렬 알고리즘	특징	실무 활용 예시
Quick Sort (퀵 정렬)	평균 시간 복잡도 O(n log n), 빠름, 대부분의 라이브러리 내부 구현	대량 데이터 정렬, 성능이 중요한 곳 (예: 정렬 API 내부)
Merge Sort (병합 정렬)	안정 정렬, 재귀적 구조, 메모리 사용 많음	대규모 데이터 처리, 외부 정렬, 병렬 정렬
Heap Sort (힙 정렬)	메모리 효율적, 최악 시간 O(n log n)	우선순위 큐나 Top-K 요소 정렬
Timsort (팀정렬)	실제 실무에서 가장 많이 쓰임 (Java, Python, Chrome V8 내부 사용)	Array.prototype.sort()의 실제 구현
Counting Sort / Radix Sort	정수 기반, 매우 빠름, 안정 정렬	로그 데이터나 ID 기반 정렬 (숫자 범위 작을 때 유리)
- 배열 정렬 시 직접 구현보다 내장 정렬 함수 사용(sort)이 대부분
- 내부 구현은 보통 Timsort 또는 QuickSort + InsertionSort 혼합