[알고리즘] 정렬 알고리즘 기본 (버블, 선택, 삽입, 카운팅 정렬)

정렬 알고리즘에 대해 정리한 글입니다. 정렬 알고리즘의 전반적인 내용과 대표적인 기본 정렬 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬, 그리고 카운팅 정렬에 대해 정리하였습니다.

(병합 정렬, 퀵 정렬, 힙 정렬 등의 알고리즘은 추후 정리할 예정입니다.)

---

정렬 (Sorting)

• 정렬(Sorting)은 주어진 데이터를 특정 기준(ex. 오름차순, 내림차순 등)에 맞춰 순서대로 재배열하는 과정
  • 오름차순 정렬 : 작은 값부터 큰 값 순서로 정렬
  • 내림차순 정렬 : 큰 값부터 작은 값 순서로 정렬
• 가장 기초적이면서도 광범위하게 사용되는 알고리즘으로, 데이터 검색과 데이터 관료 효율을 높이는데 필수적이며, 여러 문제 해결에서도 자주 활용

정렬 알고리즘 평가 기준

1. 시간 복잡도 (Time Complexity)
   • 주어진 N개의 데이터를 정렬하는 데 필요한 연산 횟수를 함수적으로 표현
   • 일반적으로 Big-O 표기법을 사용하여 최선(Best), 평균(Average), 최악(Worst) 시간 복잡도를 나타냄
2. 공간 복잡도 (Space COmplexity)
   • 정렬 과정에서 추가로 필요한 메모리가 어느 정도인지 나타냄
   • 제자리 정렬(In-place Sorting) : 추가적인 보조 공간 사용을 최소화하는 방식 ( 주로 $ O(1) $ )
3. 안정성 (Stable / Unstable)
   • 안정 정렬 (Stable Sort) : 값이 같은 원소들이 정렬 후에도 원래의 상대적인 순서를 유지하는 정렬
   • 불안정 정렬 (Unstable Sort) : 값이 같은 원소들의 상대적인 순서가 달라질 수 있는 정렬
4. 구현 난이도
   • 알고리즘의 이해와 구현이 얼마나 쉬운지 평가
   • 단순한 알고리즘(ex. 버블 정렬, 선택 정렬 등)은 구현하기 쉽지만, 시간 복잡도가 높음
   • 복잡한 고효율의 알고리즘(ex. 퀵 정렬, 병합 정럴 등)은 구현 난이도가 상대적으로 높음

대표적인 정렬 알고리즘 비교

알고리즘	평균 시간복잡도	최악 시간복잡도	공간복잡도	안정성	제자리 정렬	구현 난이도
버블 정렬	$ O(N^2) $	$ O(N^2) $	$ O(1) $	언종	O (교환)	매우 쉬움
선택 정렬	$ O(N^2) $	$ O(N^2) $	$ O(1) $	불안정	O (교환)	매우 쉬움
삽입 정렬	$ O(N^2) $	$ O(N^2) $	$ O(1) $	안정	O (이동)	쉬움
병합 정렬	$ O(N \log N) $	$ O(N \log N) $	$ O(N) $	안정	X	중간
퀵 정렬	$ O(N \log N) $	$ O(N^2) $	$ O(\log N) $	불안정	O (분할)	중간
힙 정렬	$ O(N \log N) $	$ O(N \log N) $	$ O(1) $	불안정	O (교환)	중간
카운팅 정렬	$ O(N + K) $	$ O(N + K) $	$ O(N + K) $	안정	X	쉬움

---

기본 정렬 알고리즘

버블 정렬 (Bubble Sort)

동작 원리

• 인접한 두 원소를 비교하고, 정렬 기준에 어긋나면 교환(Swap)
• 한 번의 패스 이후에는 (오름차순 기준으로) 가장 큰 원소가 맨 뒤에 위치
• 모든 원소가 정렬될 때까지 패스를 반복

장점과 단점

• 장점 : 구현이 매우 쉽고, 구현 실수가 적음
• 단점 : N이 큰 경우, 연산 횟수가 많아 비효율적

예시 코드

Python 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                # 파이썬의 교환 방식
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break

if __name__ == "__main__":
    arr = [5, 3, 8, 4, 2]
    bubble_sort(arr)
    print("After Bubble Sort:", arr)

C++ 코드

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

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // 교환 발생 여부 체크
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                // 인접 원소 교환
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        // 교환이 한 번도 없었다면 이미 정렬된 상태 → 반복 종료
        if (!swapped) break;
    }
}

int main() {
    vector<int> arr = {5, 3, 8, 4, 2};
    bubbleSort(arr);

    cout << "After Bubble Sort: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

선택 정렬 (Selection Sort)

동작 원리

• 아직 정렬되지 않은 구간에서 최솟값(오름차순 기준)을 찾아 해당 위치(가장 앞)와 교환
• 버블 정렬과 달리 내부 반복마다 한 번의 교환이 이루어짐

장점과 단점

• 장점 : 교환 횟수가 최대 N-1번으로 비교적 적음 (많은건 어절 수 없ㅇㅁ...😭)
• 단점 : 안정 정렬이 아니며, N이 커지면 비효율적

예시 코드

Python 코드

def selection_sort(arr):
    n = len(arr)
    for i in range(n - 1):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]

if __name__ == "__main__":
    arr = [5, 3, 8, 4, 2]
    selection_sort(arr)
    print("After Selection Sort:", arr)

C++ 코드

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

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        // i번째 위치에 들어갈 최소값을 찾기
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // 찾은 최소값과 i번째 요소를 교환
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    vector<int> arr = {5, 3, 8, 4, 2};
    selectionSort(arr);

    cout << "After Selection Sort: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

삽입 정렬 (Insertion Sort)

동작 원리

• 배열의 첫 번쨰 원소는 정렬되어 있다고 가정하고, 두 번째 원소부터 자신의 위치를 찾아 앞쪽 정렬된 부분에 삽입
• 이미 정렬된 구간은 항상 오름차순 혹은 내림차순 상태를 유지
• 데이터가 거의 정렬된 상태라면, 비교적 빠른 성능( $ O(N) $ )을 보임

예시 코드

Python 코드

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

if __name__ == "__main__":
    arr = [5, 3, 8, 4, 2]
    insertion_sort(arr)
    print("After Insertion Sort:", arr)

C++ 코드

#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;
        
        // key보다 큰 값은 한 칸씩 뒤로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 삽입 위치(j+1)에 key를 배치
        arr[j + 1] = key;
    }
}

int main() {
    vector<int> arr = {5, 3, 8, 4, 2};
    insertionSort(arr);

    cout << "After Insertion Sort: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

---

비교 정렬이 아닌 정렬

• 비교 기반의 정렬이 아닌 정렬 알고리즘은 데이터 범위 등에 따라 매우 빠른 정렬 속도를 낼 수 있음
• 대표적으로 카운팅 정렬 (Counting Sort), 기수 정렬 (Radix Sort), 버킷 정렬 (Bucket Sort) 등이 존재

카운팅 정렬 (Counting Sort)

• 비교 정렬이 아닌 정렬 방법으로, 데이터 범위가 제한적이고 정수 형태일 때 매우 효율적으로 동작

동작 원리

• 각 숫자가 몇 번 등장하는 지 센 후, 누적 개수를 이용해 정렬된 결과를 출력

장점과 단점

• 장점 : 데이터 값의 범위가 작을수록 매우 빠르고, 안정 정렬로 구현 가능
• 단점 : 데이터 값의 범위가 클 경우 메모리 사용이 커짐

적용 시 주의사항

• 음수 처리 : 기본 구현에서는 0 이상의 정수에 대해서만 적용이 가능 (필요하다면, 가장 작은 값을 0으로 Shift 하거나, 별도의 매핑을 사용)

예시 코드

Python 코드

def counting_sort(arr, max_value):
    # max_value: 데이터의 최댓값(0 이상 가정)
    size = len(arr)
    count = [0] * (max_value + 1)
    output = [0] * size

    # 1. 카운트 배열에 빈도 세기
    for num in arr:
        count[num] += 1

    # 2. 누적 합
    for i in range(1, max_value + 1):
        count[i] += count[i - 1]

    # 3. 뒤에서부터 정렬 결과 채우기 (안정성)
    for i in range(size - 1, -1, -1):
        value = arr[i]
        output[count[value] - 1] = value
        count[value] -= 1

    return output

if __name__ == "__main__":
    arr = [1, 4, 2, 4, 3, 1, 0, 4]
    max_val = 4
    sorted_arr = counting_sort(arr, max_val)
    print("After Counting Sort:", sorted_arr)

C++ 코드

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

vector<int> countingSort(const vector<int>& arr, int maxValue) {
    // maxValue: 데이터의 최댓값(0 이상 가정)
    int size = arr.size();
    
    // 카운트 배열(0 ~ maxValue)
    vector<int> count(maxValue + 1, 0);
    // 정렬 결과 배열
    vector<int> output(size, 0);

    // 1. 카운트 배열에 빈도 세기
    for (int i = 0; i < size; i++) {
        count[arr[i]]++;
    }

    // 2. 누적 합으로 변환
    for (int i = 1; i <= maxValue; i++) {
        count[i] += count[i - 1];
    }

    // 3. 뒤에서부터 순회하여 정렬 결과 채우기(안정 정렬)
    for (int i = size - 1; i >= 0; i--) {
        int value = arr[i];
        output[count[value] - 1] = value;
        count[value]--;
    }

    return output;
}

int main() {
    vector<int> arr = {1, 4, 2, 4, 3, 1, 0, 4};
    // 데이터 범위: 0 ~ 4
    int maxValue = 4;

    vector<int> sortedArr = countingSort(arr, maxValue);

    cout << "After Counting Sort: ";
    for (int num : sortedArr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

---

정렬 알고리즘 선택 가이드

1. 데이터 크기 (N)
   • N이 작다면 단순 구현(삽입 정렬 등)도 실용적
   • N이 매우 크다면, $ O(N \log N) $ 알고리즘(병합, 퀵, 힙 등)이 필수
2. 데이터가 정렬되어 있는 정도
   • 거의 정렬된 상태라면, 삽입 정렬이 매우 빠름 ( $ O(N) $ )
   • 무작위 데이터 또는 균일한 분포일 경우, 퀵 정렬이 평균 성능이 좋음
3. 안정성 필요 여부
   • 같은 값을 가진 데이터를 원본 순서대로 유지해야 한다면, 버블, 삽입, 병합 정렬 등 안정 정렬 선택
4. 메모리 제약
   • 추가 메모리 사용이 제한적이라면, 힙 정렬이나 퀵 정렬 사용 (제자리 정렬)
   • 보조 배열이 사용 가능하면, 병합 정렬 (안정 + 성능)
5. 데이터 범위
   • 범위가 작다면 카운팅 정렬이 매우 빠름