1. 정렬 (Sorting)

정의:

  • n개의 요소를 오름차순으로 재배열.
  • 예: 7, 3, 6, 2, 1 ➔ 1, 2, 3, 6, 7

2. 삽입 정렬 (Insertion Sort)

알고리즘:

  • n <= 1이면 이미 정렬된 상태.
  • a[0]는 재귀적으로 정렬.
  • a[n-1]을 정렬된 a[0]에 삽입.
  • 시간 복잡도: O(n^2)
  • 보통 비재귀적으로 구현.
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}


3. 선택 정렬 (Selection Sort)

알고리즘:

  • n <= 1이면 이미 정렬된 상태.
  • 가장 큰 요소를 리스트의 오른쪽 끝으로 이동.
  • 나머지 n-1 요소를 재귀적으로 정렬.
  • 시간 복잡도: O(n^2)
  • 보통 비재귀적으로 구현.
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n-1; i++) {
        min_idx = i;
        for (j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}


4. 퀵 정렬 (Quick Sort)

알고리즘:

  • n <= 1이면 리스트는 정렬된 상태.
  • n > 1이면 피벗 요소를 선택.
  • n 요소를 세 부분으로 나눔: 왼쪽, 중간(피벗), 오른쪽.
  • 왼쪽과 오른쪽 부분을 재귀적으로 정렬.
  • 정렬된 왼쪽 부분 + 피벗 + 정렬된 오른쪽 부분이 답.
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition (int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}


5. 병합 정렬 (Merge Sort)

알고리즘:

  • n > 1이면 요소를 두 개의 작은 인스턴스로 나눔.
  • 첫 번째 작은 인스턴스는 ceil(n/2) 요소를 포함.
  • 두 번째 작은 인스턴스는 floor(n/2) 요소를 포함.
  • 두 작은 인스턴스를 재귀적으로 정렬.
  • 정렬된 작은 인스턴스를 병합하여 정렬된 리스트를 생성.
  • 시간 복잡도: O(n log n)
  • 보통 비재귀적으로 구현.
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}


6. 외부 정렬 (External Sorting)

정의:

  • 내부 메모리에 모든 데이터를 수용할 수 없을 때 사용하는 정렬 방법.
  • 빠른 내부 정렬 방법을 적응.

단계:

  1. 초기 정렬 세그먼트 생성: 자연 세그먼트 또는 삽입 정렬 사용.
  2. 병합 단계: 정렬된 세그먼트 쌍을 병합하여 최종 정렬된 세그먼트를 생성.

병합 정렬 구현 예제:

// 외부 정렬 구현은 일반적으로 많은 데이터 I/O를 포함하며, 구체적인 예제는 상황에 따라 달라집니다.