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) (정렬 후 한 번 순회)

    반응형

    댓글