기본 정렬(버블, 선택, 삽입)

📌 정렬이란?

정렬은 데이터를 정해진 기준(예: 오름차순, 내림차순 등)에 따라 순서대로 배열하는 과정입니다.

정렬이 중요한 이유는 바로 탐색 효율 때문입니다. 예를 들어 이진 탐색은 정렬이 되어 있어야 사용할 수 있습니다.

---

🛠️ 예제에서 사용한 기본 구조

int main()
{
    vector<int> v{ 1, 5, 3, 4, 2 };

    std::sort(v.begin(), v.end());       // C++ STL 정렬 (참고용)
    BubbleSort(v);                       // 버블 정렬
    SelectionSort(v);                    // 선택 정렬
    InsertionSort(v);                    // 삽입 정렬
}

세 정렬 모두 동일한 벡터 v를 사용합니다. 각각 정렬 전 상태로 초기화하고 적용하면 됩니다.

---

💧 1. 버블 정렬 (Bubble Sort)

void BubbleSort(vector<int>& v)
{
    const int n = (int)v.size();

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j < (n - 1 - i); j++)
        {
            if (v[j] > v[j + 1])
            {
                int temp = v[j];
                v[j] = v[j + 1];
                v[j + 1] = temp;
            }
        }
    }
}

✅ 설명

• 인접한 두 요소를 비교해가며 정렬합니다.
• 한 바퀴 돌면 가장 큰 값이 뒤로 "버블"처럼 밀려납니다.
• 반복 횟수: N * (N-1) / 2 → O(N²) 시간 복잡도
• 정렬된 데이터가 많을수록 효율이 떨어짐

---

🎯 2. 선택 정렬 (Selection Sort)

void SelectionSort(vector<int>& v)
{
    const int n = (int)v.size();

    for (int i = 0; i < n - 1; i++)
    {
        int bestIdx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (v[j] < v[bestIdx])
                bestIdx = j;
        }

        int temp = v[i];
        v[i] = v[bestIdx];
        v[bestIdx] = temp;
    }
}

✅ 설명

• 가장 작은 값을 골라서 현재 위치와 교환합니다.
• 반복하면서 정렬된 영역을 앞에서부터 쌓아갑니다.
• swap은 한 번만 일어나기 때문에 교환 횟수가 적습니다.
• 시간 복잡도: O(N²) (비교 횟수는 항상 동일)

---

🧩 3. 삽입 정렬 (Insertion Sort)

void InsertionSort(vector<int>& v)
{
    const int n = (int)v.size();

    for (int i = 1; i < n; i++)
    {
        int insertData = v[i];

        int j;
        for (j = i - 1; j >= 0; j--)
        {
            if (v[j] > insertData)
                v[j + 1] = v[j];
            else
                break;
        }

        v[j + 1] = insertData;
    }
}

✅ 설명

• 정렬된 부분과 비교하면서 삽입 위치를 찾아 끼워넣는 방식입니다.
• 앞쪽에서 정렬된 부분을 유지하며, 삽입이 반복됩니다.
• 데이터가 이미 정렬에 가까울수록 성능이 좋아집니다!
• 평균 및 최악 시간 복잡도는 O(N²)이지만, 최선의 경우 O(N)까지 줄어듭니다.

---

🔍 세 정렬 알고리즘 비교

정렬 방식	핵심 원리	평균/최악 시간 복잡도	특징
버블 정렬	인접한 두 값 비교 후 swap	O(N²)	구현 단순하지만 가장 비효율적
선택 정렬	최소값 찾아 위치 교환	O(N²)	교환 횟수 적음
삽입 정렬	앞쪽 정렬 구간에 삽입	O(N²), 최선 O(N)	정렬된 데이터에 유리

---