정렬 (C++)

1. 정렬 (Sorting)

정렬은 데이터를 특정 기준에 따라 순서대로 배열하는 작업.

---

정렬 알고리즘의 주요 개념

1. 비교 기반 정렬: 데이터 간의 크기를 비교하여 순서를 정한다.
2. 안정적 정렬 (Stable Sort): 동일한 값이 있을 때, 원래 순서를 유지하는 정렬 방식. 예를 들어, 나이순으로 정렬하면서 이름순을 유지해야 할 때 안정적 정렬이 필요.
3. 시간 복잡도: 정렬 알고리즘의 효율성을 나타내는 척도. (https://gangdonggil.tistory.com/80)
   • 최선, 평균, 최악의 경우에 따라 다를 수 있다.

---

기본 정렬 알고리즘

• 버블 정렬 (Bubble Sort) (https://gangdonggil.tistory.com/84)
  • 동작 원리: 인접한 두 개의 데이터를 비교하여 크기가 작은 값을 앞으로 보내는 방식.
  • 시간 복잡도:
    • 최악/평균: O(n^2)
    • 최선 (이미 정렬된 경우): O(n)
  • 장점: 구현이 매우 간단.
  • 단점: 비효율적.
  코드 예시:

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

• 선택 정렬 (Selection Sort) (https://gangdonggil.tistory.com/85)
  • 동작 원리: 매번 가장 작은 값을 찾아 정렬되지 않은 부분의 맨 앞으로 이동.
  • 시간 복잡도: O(n^2)
  • 장점: 메모리 사용량이 적음.
  • 단점: 속도가 느림.
  코드 예시:

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);
    }
}

• 삽입 정렬 (Insertion Sort) (https://gangdonggil.tistory.com/86)
  • 동작 원리: 데이터를 하나씩 확인하며 정렬된 부분에 삽입.
  • 시간 복잡도:
    • 최악/평균: O(n^2)
    • 최선 (이미 정렬된 경우): O(n)
  • 장점: 데이터가 거의 정렬된 상태일 때 빠름.
  • 단점: 많은 데이터를 처리하기엔 비효율적.
  코드 예시:

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    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;
        }
        arr[j + 1] = key;
    }
}

---

효율적인 정렬 알고리즘

• 퀵 정렬 (Quick Sort) (https://gangdonggil.tistory.com/87)
  • 동작 원리: 기준점(pivot)을 정하고, pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할. 각 부분을 재귀적으로 정렬.
  • 시간 복잡도:
    • 최선/평균: O(nlog⁡n)
    • 최악: O(n^2) (pivot이 최적이 아닐 경우)
  • 장점: 평균적으로 빠름.
  • 단점: pivot 선택이 중요.
  코드 예시:

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

void quickSort(vector<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);
    }
}

• 병합 정렬 (Merge Sort) (https://gangdonggil.tistory.com/manage/posts/)
  • 동작 원리: 데이터를 반으로 나누고 각각 정렬 후 병합.
  • 시간 복잡도: O(nlog⁡n)
  • 장점: 안정적이며 대규모 데이터 정렬에 적합.
  • 단점: 추가 메모리 사용.
  코드 예시:

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);
    for (int k = left; k <= right; ++k) arr[k] = temp[k - left];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

• 힙 정렬 (Heap Sort) (https://gangdonggil.tistory.com/89)
  • 동작 원리: 데이터를 힙 자료구조로 구성한 뒤, 최대값/최소값을 제거하며 정렬.
  • 시간 복잡도: O(nlog⁡n)
  • 장점: 추가 메모리가 필요 없음.
  • 단점: 구현이 복잡.
  코드 예시:

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = n / 2 - 1; i >= 0; --i) heapify(arr, n, i);
    for (int i = n - 1; i > 0; --i) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

---

C++ STL 활용

C++ 표준 라이브러리를 활용하면 정렬을 빠르고 간단하게 처리할 수 있습니다.

• std::sort:
  • 시간 복잡도: O(nlog⁡n)
  • 내부적으로 퀵 정렬을 기반으로 동작.
  • 예시:

#include <algorithm>
#include <vector>
using namespace std;

vector<int> arr = {5, 2, 8, 1, 3};
sort(arr.begin(), arr.end());

• std::stable_sort:
  • 시간 복잡도: O(nlog^2n)
  • 안정적 정렬을 보장.
• 사용자 정의 정렬:
  • 특정 기준으로 정렬 가능.
   

struct Point {
    int x, y;
};

bool compare(const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

vector<Point> points = {{1, 2}, {3, 4}, {1, 1}};
sort(points.begin(), points.end(), compare);

---