정렬 알고리즘

// 1. 버블 정렬 (Bubble Sort)
// 인접한 두 원소를 비교해 더 큰 값을 오른쪽으로 밀어냄
// 시간복잡도: O(n²), 공간복잡도: O(1)
void bubbleSort(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; // 이미 정렬된 경우 조기 종료
    }
}

 

// 2. 선택 정렬 (Selection Sort)
// 미정렬 구간에서 최솟값을 찾아 맨 앞으로 이동
// 시간복잡도: O(n²), 공간복잡도: O(1)
void selectionSort(int arr[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        int minIdx = i;
        for (int j = i + 1; j < length; j++)
        {
            if (arr[j] < arr[minIdx])
                minIdx = j;
        }
        swap(arr[i], arr[minIdx]);
    }
}

 

// 3. 삽입 정렬 (Insertion Sort)
// 현재 원소를 정렬된 구간의 올바른 위치에 삽입
// 시간복잡도: O(n²), 거의 정렬된 경우 O(n), 공간복잡도: O(1)
void insertionSort(int arr[], int length)
{
    for (int i = 1; i < length; 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;
    }
}

 

// 4. 합병 정렬 (Merge Sort)
// 배열을 반으로 나눠 재귀적으로 정렬한 후 합병
// 시간복잡도: O(n log n), 공간복잡도: O(n)
void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int* L = new int[n1];
    int* R = new int[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];

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

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right)
{
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

 

// 5. 퀵 정렬 (Quick Sort)
// 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할 후 재귀 정렬
// 시간복잡도: 평균 O(n log n), 최악 O(n²), 공간복잡도: O(log n)
int partition(int arr[], int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] <= pivot)
        {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[right]);
    return i + 1;
}

void quickSort(int arr[], int left, int right)
{
    if (left >= right) return;
    int pivotIdx = partition(arr, left, right);
    quickSort(arr, left, pivotIdx - 1);
    quickSort(arr, pivotIdx + 1, right);
}

 

// 6. 힙 정렬 (Heap Sort)
// 최대 힙을 구성한 후 루트(최댓값)를 꺼내며 정렬
// 시간복잡도: O(n log n), 공간복잡도: O(1)
void heapify(int arr[], int length, int i)
{
    int largest = i;
    int left    = 2 * i + 1;
    int right   = 2 * i + 2;

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

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

void heapSort(int arr[], int length)
{
    for (int i = length / 2 - 1; i >= 0; i--)
        heapify(arr, length, i);

    for (int i = length - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

 

// 7. 계수 정렬 (Counting Sort)
// 각 값의 등장 횟수를 세어 정렬 (정수, 값의 범위가 작을 때 유리)
// 시간복잡도: O(n + k), 공간복잡도: O(k)  [k = 값의 범위]
void countingSort(int arr[], int length)
{
    int maxVal = arr[0];
    for (int i = 1; i < length; i++)
        if (arr[i] > maxVal) maxVal = arr[i];

    int* count = new int[maxVal + 1]();
    for (int i = 0; i < length; i++)
        count[arr[i]]++;

    int idx = 0;
    for (int i = 0; i <= maxVal; i++)
        while (count[i]-- > 0)
            arr[idx++] = i;

    delete[] count;
}