10 minute read

1. Sorting

  1. Compare the Comparable interface to the Comparator interface, and know when to use each one.
  2. Be able to decide which sort algorithm is appropriate for a given application.
  3. Understand the limitations of each sort algorithm.
  4. Explain the criteria for a divide-and-conquer algorithm.

1-1. Comparison-Based Sorts

비교 기반 정렬은 요소들 간의 비교를 통해 데이터를 정렬하는 알고리즘을 의미한다.

비교가 필요 없는 경우

모든 요소의 최종 위치를 사전에 알 수 있다면 비교 없이 정렬이 가능하다. ex) 0부터 99 사이의 100개의 고유 정수가 주어진 경우, 0은 항상 0번째 위치에, 99는 항상 99번째 위치에 있어야 한다. 이런 유형의 정렬 알고리즘 중 가장 잘 알려진 것은 Radix Sort이다.

1-2. 일반적인 정렬 알고리즘

정렬 알고리즘들은 모두 일반(generic) 알고리즘으로, 정적 메서드 형태로 구현된다. 정적 메서드는 호출 객체가 필요 없으며, 정렬할 컬렉션을 매개변수로 받아 처리한다.

Merge Sort와 Quick Sort는 Java Collections Framework에 포함된 정렬 알고리즘이며, java.util.Collections 또는 java.util.Arrays에서 찾을 수 있다.

1-3. 효율성 평가 기준

정렬 알고리즘의 효율성을 평가할 때 중요한 요소:

  • 평균 시간 복잡도 (averageTime(n))
  • 최악 시간 복잡도 (worstTime(n))

최악의 성능이 중요한 애플리케이션 (예: 국가 방위 시스템, 생명 유지 장치)에서는 최악의 경우 성능이 특히 중요하다. 일부 정렬 알고리즘은 평균적으로 매우 빠르지만, 최악의 경우 성능이 현저히 떨어질 수 있다.

1-4. 안정성 (Stability)

안정적인 정렬 (Stable Sort): 동일한 값의 요소들 간의 상대적 순서를 유지한다.

  • 학생의 배열에서 총 품질 점수로 정렬할 때, “Balan (28)”이 “Wang (28)”보다 앞에 있었다면, 정렬 후에도 이 순서는 유지된다. 안정적인 정렬은 일부 프로젝트에서 중요한 역할을 한다.
  • 이미 이름순으로 정렬된 학생 배열을 점수 순으로 정렬할 때, 안정적인 정렬은 추가 작업 없이 이름순을 유지할 수 있다

2. 단순 정렬 (Simple Sorts)

단순 정렬 알고리즘은 구현이 비교적 간단하지만, 데이터의 양이 많아질수록 비효율적인 실행 시간을 보이는 특징이 있습니다. 이들 알고리즘은 주로 작은 배열이나 특정 상황에서만 사용되며, 일반적으로 더 복잡한 알고리즘보다 성능이 떨어집니다.

  • 삽입 정렬
  • 선택 정렬
  • 버블 정렬을 설명합니다.

2-1. 삽입 정렬 (Insertion Sort)

개념

이미 정렬된 부분 배열에 새 요소를 하나씩 추가하여 전체 배열을 정렬하는 방식입니다. 각 요소는 자신의 올바른 위치로 ‘삽입’되며, 이를 위해 뒤로 밀기 (shifting)가 발생할 수 있습니다.

동작 원리

두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분 배열에서 올바른 위치로 이동시킵니다. 앞쪽 요소들과 비교하여 더 큰 요소는 오른쪽으로 이동시키고, 더 작은 요소를 만나면 그 자리에 삽입합니다. 이 과정을 배열의 끝까지 반복합니다.

시간 복잡도

  • 최악의 경우: 𝑂(𝑛^2) (역순으로 정렬된 경우)
  • 최선의 경우: 𝑂(𝑛) (이미 정렬된 경우)
  • 평균: 𝑂(𝑛^2)

공간 복잡도

𝑂(1) (추가적인 배열을 사용하지 않음, 제자리 정렬)

Java 구현

/**
 * 주어진 배열을 오름차순으로 정렬합니다.
 * 최악의 경우 시간 복잡도는 O(n^2)입니다.
 * @param x - 정렬할 배열
 * @throws NullPointerException - x가 null인 경우
 */
public static void insertionSort(int[] x) {
    for (int i = 1; i < x.length; i++) {
        for (int k = i; k > 0 && x[k - 1] > x[k]; k--) {
            swap(x, k, k - 1);
        }
    }
}

/**
 * 두 배열 요소의 위치를 교환합니다.
 * @param x - 배열
 * @param a - 교환할 첫 번째 요소의 인덱스
 * @param b - 교환할 두 번째 요소의 인덱스
 */
public static void swap(int[] x, int a, int b) {
    int t = x[a];
    x[a] = x[b];
    x[b] = t;
}

2-2. 선택 정렬 (Selection Sort)

개념

배열에서 가장 작은 요소를 찾아 첫 번째 위치와 교환하고, 그 다음 작은 요소를 두 번째 위치와 교환하는 방식입니다. 비교적 간단하지만 성능이 낮으며, 데이터의 초기 상태와 상관없이 항상 O(n^2)의 시간 복잡도를 가집니다.

  • 비안정적인 정렬로, 같은 값의 요소들이 입력 순서가 유지되지 않을 수 있습니다.

동작 원리

  1. 배열에서 최솟값을 찾아 첫 번째 요소와 교환합니다.
  2. 두 번째 요소부터 나머지 배열에서 최솟값을 찾아 교환합니다.
  3. 배열 끝까지 반복합니다.

시간 복잡도

  • 최악의 경우: O(n^2)
  • 최선의 경우: O(n^2)
  • 평균의 경우: O(n^2)

Java 구현

public static void selectionSort(int[] x) {
    for (int i = 0; i < x.length - 1; i++) {
        int minPos = i;
        for (int k = i + 1; k < x.length; k++)
            if (x[k] < x[minPos])
                minPos = k;
        swap(x, i, minPos);
    }
}

2-3.버블 정렬 (Bubble Sort)

개념

배열의 요소들을 순차적으로 비교하여 큰 값을 오른쪽으로 보내는 방식입니다. 가장 느린 정렬 알고리즘 중 하나로, 실무에서는 거의 사용되지 않습니다.

  • 안정적인 정렬로, 같은 값의 요소들이 입력 순서가 유지됩니다.

동작 원리

  1. 배열의 첫 번째 요소부터 인접한 요소와 비교하여 큰 값을 오른쪽으로 이동시킵니다.
  2. 마지막 교환이 발생한 위치까지만 비교하여 효율성을 높일 수 있습니다.
  3. 더 이상 교환이 없을 때까지 반복합니다.

시간복잡도

  • 최악의 경우: O(n^2)
  • 최선의 경우: O(n)
  • 평균의 경우: O(n^2)

Java 구현

public static void bubbleSort(int[] x) {
    int finalSwapPos = x.length - 1;
    while (finalSwapPos > 0) {
        int swapPos = 0;
        for (int i = 0; i < finalSwapPos; i++)
            if (x[i] > x[i + 1]) {
                swap(x, i, i + 1);
                swapPos = i;
            }
        finalSwapPos = swapPos;
    }
}

3. Comparator 인터페이스

단순 정렬 알고리즘인 삽입 정렬, 선택 정렬, 버블 정렬은 기본적으로 int와 같은 기본 자료형 배열을 오름차순으로 정렬합니다. 이들은 약간의 수정만으로 내림차순 정렬이나 long, double 등 다른 기본 자료형 배열도 쉽게 정렬할 수 있습니다.

  • 그러나 객체 배열을 정렬하는 경우는 다릅니다.

Comparable 인터페이스를 사용하는 정렬

객체 배열을 정렬하기 위해서는 객체의 “자연적 순서(natural ordering)”를 정의해야 합니다. 이를 위해 Java는 Comparable 인터페이스를 제공합니다. 예를 들어, Comparable을 구현한 객체 배열을 정렬하는 선택 정렬 메서드는 다음과 같습니다:

/**
 * 주어진 객체 배열을 오름차순으로 정렬합니다.
 * 최악의 시간 복잡도: O(n^2)
 * @param x - 정렬할 객체 배열
 * @throws NullPointerException - x가 null일 때
 */
public static void selectionSort(Object[] x) {
    for (int i = 0; i < x.length - 1; i++) {
        int pos = i;
        for (int k = i + 1; k < x.length; k++)
            if (((Comparable)x[k]).compareTo(x[pos]) < 0)
                pos = k;
        swap(x, i, pos);
    }
}

위 코드에서 배열의 요소는 Comparable 인터페이스를 구현해야 하며, compareTo() 메서드를 사용하여 비교가 이루어집니다. 예를 들어, String 클래스는 이미 Comparable 인터페이스를 구현하여 사전 순서(lexicographical order)로 정렬할 수 있습니다:

String[] names = {"Jayden", "Jack", "Rowan", "Brooke"};
selectionSort(names);
System.out.println(Arrays.toString(names)); // [Brooke, Jack, Jayden, Rowan]

예시: 문자열 길이로 정렬

다음은 문자열의 길이에 따라 정렬하는 ByLength라는 Comparator 클래스의 구현 예시입니다:

import java.util.Comparator;

public class ByLength implements Comparator<String> {
    /**
     * 두 개의 문자열을 길이에 따라 비교합니다.
     * 길이가 같다면 사전 순서로 비교합니다.
     * @param s1 - 첫 번째 문자열
     * @param s2 - 두 번째 문자열
     * @return s1이 s2보다 짧으면 음수, 같으면 0, 길면 양수
     */
    public int compare(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 == len2)
            return s1.compareTo(s2); // 길이가 같으면 사전 순서로 비교
        return len1 - len2; // 길이가 다르면 길이 차이 반환
    }
}

선택 정렬 메서드 수정

이제 Comparator를 사용하는 선택 정렬 메서드는 다음과 같습니다:

/**
 * 지정된 Comparator를 사용하여 객체 배열을 정렬합니다.
 * 최악의 시간 복잡도: O(n^2)
 * @param x - 정렬할 객체 배열
 * @param comp - 요소를 비교할 Comparator 객체
 * @throws NullPointerException - x 또는 comp가 null일 때
 */
public static <T> void selectionSort(T[] x, Comparator<? super T> comp) {
    for (int i = 0; i < x.length - 1; i++) {
        int pos = i;
        for (int k = i + 1; k < x.length; k++)
            if (comp.compare(x[k], x[pos]) < 0)
                pos = k;
        swap(x, i, pos);
    }
}

/**
 * 배열의 두 요소를 교환합니다.
 * @param x - 교환할 배열
 * @param a - 첫 번째 인덱스
 * @param b - 두 번째 인덱스
 */
public static void swap(Object[] x, int a, int b) {
    Object temp = x[a];
    x[a] = x[b];
    x[b] = temp;
}

4. 얼마나 빠르게 정렬할 수 있을까?

삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort)과 같은 기본 정렬 알고리즘은 최악의 경우(worstTime(n))와 평균적인 경우(averageTime(n)) 모두 O(n^2)의 시간 복잡도를 가집니다.

  • 이제 더 빠른 정렬 알고리즘을 알아보기 전에, 실제로 가능한 최적의 시간 복잡도를 계산해 보겠습니다. 이를 위해 결정 트리(Decision Tree)라는 도구를 사용합니다.

4-1. 결정 트리 (Decision Tree)

결정 트리는 n개의 요소를 정렬하는데 필요한 비교를 나타내는 이진 트리입니다.

  • 각 비단말 노드(non-leaf node)는 두 요소를 비교하는 연산을 나타내고,
  • 각 단말 노드(leaf node)는 n개의 요소가 정렬된 상태를 나타냅니다.

4-2. 결정트리와 최악의 시간 복잡도

결정 트리는 다음과 같은 특징을 가집니다, 단말 노드의 개수는 정렬 가능한 모든 경우의 수와 같다.

  • n개의 요소를 정렬하는 모든 가능한 순열의 개수는 n!입니다. 따라서, n개의 요소를 정렬하는 결정 트리는 n!개의 단말 노드를 가져야 합니다.
  • 이진 트리의 단말 노드 수는 높이에 대한 지수 함수 관계를 가진다. 이진 트리 정리에 따르면, 어떤 비어 있지 않은 이진 트리 t의 단말 노드 수는 2^height(t)보다 작거나 같다.
  • $n! \leq 2^{\text{height}(t)}$

4-3. 로그를 사용한 높이의 하한 계산

이 식의 양변에 로그를 취하면,

  • $ \text{height}(t) \geq \log_2 (n!) $

이는 n개의 요소를 정렬하는 어떤 비교 기반 정렬 알고리즘이라도 최소 log2(n!)만큼의 비교가 필요하다는 것을 의미합니다.

로그 함수의 근사치

log2(n!)는 다음과 같이 근사할 수 있습니다:

  • $ \log_2 (n!) \geq \frac{n}{2} \log_2 \left(\frac{n}{2}\right) $

이는 결국 n log n의 형태를 가지며, 비교 기반 정렬 알고리즘의 최악의 시간 복잡도는 적어도 O(n log n)이라는 사실을 의미합니다. $ \log_2 (n!) $을 근사할 때, 사실 이는 로그 함수들의 합입니다:

  • $\log_2 (1) + \log_2 (2) + \log_2 (3) + \cdots + \log_2 (n)$

여기서 각각의 로그값이 점차적으로 증가하지만 느리게 증가하기 때문에, 이 값들을 $ N \cdot \log_2 (N) $로 근사할 수 있다는 것입니다.

$ \log_2(1) + \log_2(2) + \log_2(3) + \cdots + \log_n(n) = \log_2 (n!)$
$ \leq \log_2(N) + \log_2(N) + \log_2(N) + \cdots + \log N = N \log_2(N)$

  • 즉, 대체적으로 이 합은 에 근접하는 형태로 합산될 수 있습니다.

4-4. 정리

  • Sorting Fact 1: 비교 기반 정렬 알고리즘의 최악의 시간 복잡도는 O(n log n)입니다.
  • Sorting Fact 2: 비교 기반 정렬 알고리즘의 평균 시간 복잡도도 O(n log n)입니다.
  • Sorting Fact 3: 최악의 시간 복잡도가 O(n log n)인 비교 기반 정렬 알고리즘은 평균적인 경우에도 O(n log n)의 시간 복잡도를 가집니다.

5. Merge Sort Algorithm

Merge Sort는 java.util 패키지의 Arrays 클래스에 포함된 객체 배열을 정렬하는 알고리즘입니다. 다음은 Merge Sort의 주요 아이디어입니다:

  • 배열을 7개 이하의 작은 부분 배열로 나눕니다.
  • 각 부분 배열을 Insertion Sort로 정렬합니다.
  • 두 개의 정렬된 부분 배열을 합쳐 더 큰 정렬된 배열로 만듭니다.
  • 이 과정을 배열 전체가 정렬될 때까지 반복합니다.

Java 구현

/**
 * Sorts a specified array of objects according to the compareTo method
 * in the specified class of elements.
 * The worstTime(n) is O(n log n).
 * @param a - the array of objects to be sorted.
 */
public static void sort(Object[] a) {
    Object[] aux = (Object[]) a.clone();
    mergeSort(aux, a, 0, a.length);
} // method sort

/**
 * Sorts, by the Comparable interface, a specified range of a specified array
 * into the same range of another specified array.
 * The worstTime(k) is O(k log k), where k is the size of the subarray.
 * @param src - the specified array whose elements are to be sorted into another specified array.
 * @param dest - the specified array whose subarray is to be sorted.
 * @param low - the smallest index in the range to be sorted.
 * @param high - 1 + the largest index in the range to be sorted.
 */
private static void mergeSort(Object[] src, Object[] dest, int low, int high) {
    int length = high - low;
    
    // Use Insertion Sort for small subarrays.
    if (length < 7) {
        for (int i = low; i < high; i++)
            for (int j = i; j > low && ((Comparable) dest[j - 1]).compareTo(dest[j]) > 0; j--)
                swap(dest, j, j - 1);
        return;
    }

    // Sort left and right halves of src into dest.
    int mid = (low + high) >> 1; // same as / 2, but faster
    mergeSort(dest, src, low, mid);
    mergeSort(dest, src, mid, high);
    
    // If left subarray less than right subarray, copy src to dest.
    if (((Comparable) src[mid - 1]).compareTo(src[mid]) <= 0) {
        System.arraycopy(src, low, dest, low, length);
        return;
    }
    
    // Merge sorted subarrays in src into dest.
    for (int i = low, p = low, q = mid; i < high; i++) {
        if (q >= high || (p < mid && ((Comparable) src[p]).compareTo(src[q]) <= 0))
            dest[i] = src[p++];
        else
            dest[i] = src[q++];
    }
} // method mergeSort

Stability

Merge Sort는 요소들의 상대적 순서를 유지하기 때문에 Stable Sort입니다.

왜 Merge Sort를 사용할까?

버블 정렬이나 선택 정렬과 같은 간단한 정렬 알고리즘은 배열의 길이가 길어질수록 성능이 급격히 떨어집니다. 반면 Merge Sort는 분할 정복 (Divide and Conquer) 방식을 사용하여 훨씬 더 나은 확장성을 가집니다.

1. 분할 (Divide): 배열을 절반으로 계속 나눕니다. 각 부분 배열의 크기가 작아질수록 삽입 정렬이 더 효율적이므로, 일반적으로 7개 이하가 될 때 insertion sort로 처리합니다. 또는, 1개의 요소만 남을 때까지 나눌 수도 있습니다. (모든 단일 요소 배열은 이미 정렬된 상태)

  • $ Depth = \log_2(n) $

2. 정복 (Conquer): 이렇게 나뉜 작은 부분 배열들을 Merge하여 점점 더 큰 정렬된 배열을 만듭니다. 두 개의 정렬된 배열을 합치는 것은 두 배열을 각각의 첫 번째 요소부터 비교하여 더 작은 요소를 결과 배열에 추가하는 방식으로 이루어집니다.

  • 병합 작업은 두 배열의 길이를 합친 만큼의 비교 연산이 필요하므로, 각 레벨에서 O(n) 시간이 걸립니다.

Case 1:

한 배열의 모든 요소가 다른 배열의 모든 요소보다 작거나 클 때 → 단순히 두 배열을 이어붙이면 됩니다.

Case 2:

그렇지 않을 때 → 두 배열의 요소들을 하나씩 비교하여 정렬된 상태로 병합합니다.

Leave a comment

You may also enjoy

AI Utilization in XR Technology

1 minute read

Recently, there have been many tips on how to use ChatGPT effectively on the Internet. This skill is called Prompt Engineering. Some people are very good at ...