정렬 알고리즘

1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 간단한 알고리즘입니다. 두 요소를 비교하여 순서가 맞지 않으면 교환하는 방식으로, 배열의 끝까지 반복합니다. 이 과정이 전체 배열을 한 번 순회할 때마다 가장 큰 값이 맨 끝으로 이동합니다.

동작 원리

1. 첫 번째 요소와 두 번째 요소를 비교합니다.
2. 두 번째 요소가 더 작으면 두 요소를 교환합니다.
3. 두 번째 요소와 세 번째 요소를 비교하여 같은 작업을 반복합니다.
4. 배열의 끝까지 이를 반복합니다.
5. 마지막 요소까지 도달하면 처음부터 다시 시작하여 이 과정을 반복합니다.

코드 예제

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

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]);
            }
        }
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    bubbleSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

시간 복잡도

• 최악: O(n^2)
• 평균:O(n^2)
• 최선: O(n) (이미 정렬된 경우)

---

2. 선택 정렬 (Selection Sort)

선택 정렬은 배열을 순회하면서 가장 작은(혹은 큰) 요소를 찾아 첫 번째 위치와 교환하는 방식입니다. 이를 반복하여 정렬을 완료합니다.

동작 원리

1. 배열에서 가장 작은 요소를 찾습니다.
2. 그 요소를 첫 번째 요소와 교환합니다.
3. 두 번째 요소부터 다시 같은 작업을 반복합니다.
4. 전체 배열이 정렬될 때까지 이를 반복합니다.

코드 예제

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

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]);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    selectionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

시간 복잡도

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

---

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 배열의 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분 배열의 적절한 위치에 삽입하는 방식입니다.

동작 원리

1. 두 번째 요소를 첫 번째 요소와 비교하여 적절한 위치에 삽입합니다.
2. 세 번째 요소를 앞의 두 요소와 비교하여 적절한 위치에 삽입합니다.
3. 이를 반복하여 전체 배열을 정렬합니다.

코드 예제

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

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;
    }
}

int main() {
    vector<int> arr = {12, 11, 13, 5, 6};
    insertionSort(arr);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

시간 복잡도

• 최악: O(n^2)
• 평균: O(n^2)
• 최선: O(n) (이미 정렬된 경우)

---

4. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 알고리즘의 일종으로, 피벗을 기준으로 배열을 두 부분으로 나누고, 각각을 재귀적으로 정렬합니다.

동작 원리

1. 피벗 요소를 선택합니다.
2. 피벗보다 작은 요소는 피벗의 왼쪽에, 큰 요소는 피벗의 오른쪽에 위치시킵니다.
3. 피벗을 기준으로 배열을 두 부분으로 나누고, 각각에 대해 퀵 정렬을 재귀적으로 수행합니다.

코드 예제

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

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);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

시간 복잡도

• 최악: O(n^2) (매우 불균형하게 분할되는 경우)
• 평균: O(nlog⁡n)
• 최선: O(nlog⁡n)

---

5. 병합 정렬 (Merge Sort)

병합 정렬은 분할 정복 알고리즘으로, 배열을 절반으로 나누어 각각을 재귀적으로 정렬한 후 병합하는 방식입니다.

동작 원리

1. 배열을 절반으로 나눕니다.
2. 각각을 재귀적으로 병합 정렬합니다.
3. 두 정렬된 배열을 병합하여 전체 배열을 정렬합니다.

코드 예제

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

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);
    }
}

int main() {
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    quickSort(arr, 0, arr.size() - 1);
    for (int num : arr) {
        cout << num << " ";
    }
    return 0;
}

시간 복잡도

• 최악: O(nlog⁡n)
• 평균: O(nlog⁡n)
• 최선: O(nlog⁡n)

---

요약

이상에서 설명한 다양한 정렬 알고리즘은 각각의 장단점이 있으며, 상황에 맞게 선택하여 사용할 수 있습니다. 데이터셋의 크기와 정렬의 필요성에 따라 적절한 알고리즘을 선택하는 것이 중요합니다. 코딩 테스트나 면접에서 자주 물어보는 주제이므로, 각 알고리즘의 동작 원리와 구현 방법을 숙지하는 것이 좋습니다.