6. 정렬 (Sorting) Codility Lesson 한국어 정리본 (JavaScript ver.)

정렬(Sorting)이란?

정렬이란 데이터를 특정한 순서대로 배치하는 과정이다. 일반적으로 숫자 또는 문자열을 값에 따라 정렬한다. 예를 들어, 학생을 키 순서대로 정렬하거나, 도시를 인구수 기준으로 정렬할 수 있다.

다음과 같은 배열이 있다고 가정하자.

A = [5, 2, 8, 14, 1, 16];

이를 숫자 크기 순서로 정렬하면 다음과 같다.

A = [1, 2, 5, 8, 14, 16];

정렬 알고리즘은 시간 복잡도와 메모리 사용량에 따라 차이가 있다. 여기서는 대표적인 정렬 알고리즘을 살펴본다.

---

1. 선택 정렬 (Selection Sort)

아이디어: 배열에서 가장 작은 원소를 찾아 첫 번째 위치와 교환하는 작업을 반복한다.

JavaScript 코드:

function selectionSort(A) {
    let n = A.length;
    for (let k = 0; k < n; k++) {
        let minIndex = k;
        for (let j = k + 1; j < n; j++) {
            if (A[j] < A[minIndex]) {
                minIndex = j;
            }
        }
        [A[k], A[minIndex]] = [A[minIndex], A[k]]; // swap
    }
    return A;
}

시간 복잡도: O(n²) (이중 반복문 사용)

---

2. 카운팅 정렬 (Counting Sort)

아이디어: 원소의 등장 횟수를 배열에 저장한 후, 카운트 배열을 기반으로 정렬한다.

JavaScript 코드:

function countingSort(A, k) {
    let n = A.length;
    let count = new Array(k + 1).fill(0);
    
    for (let i = 0; i < n; i++) {
        count[A[i]] += 1;
    }
    
    let p = 0;
    for (let i = 0; i <= k; i++) {
        for (let j = 0; j < count[i]; j++) {
            A[p++] = i;
        }
    }
    return A;
}

시간 복잡도: O(n + k) (단, k 값이 클 경우 메모리 사용량이 많아질 수 있음)

---

3. 합병 정렬 (Merge Sort)

아이디어: 배열을 절반씩 나눈 후, 각각 정렬하고 병합하는 방식이다.

JavaScript 코드:

function mergeSort(A) {
    if (A.length <= 1) return A;
    
    let mid = Math.floor(A.length / 2);
    let left = mergeSort(A.slice(0, mid));
    let right = mergeSort(A.slice(mid));
    
    return merge(left, 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.concat(left.slice(i)).concat(right.slice(j));
}

시간 복잡도: O(n log n) (분할 + 병합 과정이 로그 단위로 진행됨)

---

4. 내장 정렬 함수 (Built-in Sorting)

JavaScript는 기본적으로 O(n log n) 복잡도의 정렬 함수를 제공한다.

JavaScript 코드:

A.sort((a, b) => a - b);

이 방식은 정렬 속도가 빠르고 코드가 간결하기 때문에 대부분의 경우 내장 함수를 활용하는 것이 좋다.

---

5. 배열 내 서로 다른 값의 개수 구하기

배열 A에 있는 서로 다른 값의 개수 를 구하는 문제를 해결해보자.

O(n log n) (정렬 후 비교)

JavaScript 코드:

function distinct(A) {
    if (A.length === 0) return 0;
    
    A.sort((a, b) => a - b);
    let result = 1;
    
    for (let k = 1; k < A.length; k++) {
        if (A[k] !== A[k - 1]) {
            result++;
        }
    }
    return result;
}

시간 복잡도: O(n log n) (정렬 후 한 번 순회)