정렬(Sorting)의 비교

정렬 Sorting 은 데이터를 일정한 순서대로 재배열하는 과정을 말한다.
예를 들어 숫자를 오름차순으로 정렬하거나, 이름을 사전순으로 나열하는 것이 정렬의 예다.

정렬 알고리즘은 비교 기반 정렬과 비비교 기반 정렬로 나눌 수 있다.
여기서는 비교 기반 정렬 중 대표적인 네 가지 알고리즘인 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬을 중심으로 비교해보겠다.

---

버블 정렬 Bubble Sort

인접한 두 원소를 비교하여 순서가 잘못된 경우 서로 교환하는 방식이다.
한 번의 패스가 끝날 때마다 가장 큰 값이 맨 뒤로 이동한다.
단순하지만 비효율적이다.

시간 복잡도

• 최선: O n
• 평균: O n 제곱
• 최악: O n 제곱

예시 코드

 

#include <iostream>
using namespace std;

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

---

선택 정렬 Selection Sort

전체 데이터 중에서 가장 작은 값을 선택하여 맨 앞의 데이터와 교환하는 과정을 반복한다.
교환 횟수가 적지만, 비교 횟수는 많다.

시간 복잡도

• 최선: O n 제곱
• 평균: O n 제곱
• 최악: O n 제곱

예시 코드

 

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

---

삽입 정렬 Insertion Sort

데이터를 하나씩 확인하면서 자신의 위치를 찾아 삽입하는 방식이다.
거의 정렬된 상태의 데이터에 대해서는 매우 효율적이다.

시간 복잡도

• 최선: O n
• 평균: O n 제곱
• 최악: O n 제곱

예시 코드

 

void insertionSort(int arr[], int n) {
    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

기준 원소 pivot 을 하나 선택하고, 이를 기준으로 작은 값과 큰 값을 분할하여 재귀적으로 정렬한다.
분할 정복 Divide and Conquer 방식의 대표적인 정렬 알고리즘이다.
실제 실행 속도가 매우 빠르다.

시간 복잡도

• 최선: O n log n
• 평균: O n log n
• 최악: O n 제곱

예시 코드

 

int partition(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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

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

---

정렬 알고리즘 비교표

정렬 방법	평균 시간 복잡도	공간 복잡도	특징
버블 정렬	O n 제곱	O 1	구현이 가장 단순하지만 느리다
선택 정렬	O n 제곱	O 1	교환 횟수가 적지만 비교가 많다
삽입 정렬	O n 제곱	O 1	거의 정렬된 데이터에 빠르다
퀵 정렬	O n log n	O log n	실제로 가장 빠른 정렬 중 하나다

---

정리

정렬 알고리즘의 선택은 데이터의 크기, 정렬된 정도, 메모리 제약에 따라 달라진다.
작은 데이터에서는 삽입 정렬이, 큰 데이터에서는 퀵 정렬이나 병합 정렬이 주로 사용된다.
즉, 상황에 맞는 정렬 알고리즘을 선택하는 것이 효율적인 프로그램 작성의 핵심이다.