[2주차 TIL] KnockOn Bootcamp - 정렬 알고리즘

 

📘 정렬 알고리즘의 기초 – 버블, 선택, 삽입 정렬

---

📖 개요

정렬(Sorting)은 데이터를 특정한 순서(오름차순 또는 내림차순)로 재배열하는 알고리즘이다.
정렬은 검색, 탐색, 데이터 처리의 전처리 과정으로 자주 사용된다.

본 장에서는 세 가지 기본 정렬 알고리즘을 구현하고, 그 동작 방식과 차이점을 이해한다.

---

💡 학습 목표

1. 버블 정렬(Bubble Sort)의 작동 원리와 구현
2. 선택 정렬(Selection Sort)의 작동 원리와 구현
3. 삽입 정렬(Insertion Sort)의 작동 원리와 구현
4. 각 정렬 알고리즘의 시간 복잡도 및 특징 분석

---

1. 버블 정렬 (Bubble Sort)

📌 원리

인접한 두 데이터를 비교하여 큰 값을 뒤로 보내는 방식.
가장 큰 값이 '거품처럼' 맨 뒤로 밀려나는 원리.

📌 시간 복잡도

• 최악/평균: O(n²)
• 최선(정렬되어 있는 경우): O(n)

📁 구현 코드

#include <stdio.h>

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

---

2. 선택 정렬 (Selection Sort)

📌원리

배열을 순차적으로 탐색하며 가장 작은 값을 선택하여 앞쪽으로 이동시킴.

📌시간 복잡도

• 항상: O(n²)

📁 구현 코드

#include <stdio.h>

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

---

3. 삽입 정렬 (Insertion Sort)

📌 원리

두 번째 원소부터 시작하여, 자신보다 앞에 있는 원소들과 비교해 알맞은 위치에 삽입.

📌 시간 복잡도

• 최악/평균: O(n²)
• 최선(정렬된 경우): O(n)

📁 구현 코드

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int key, j;
    for (int i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 앞의 값들이 key보다 크면 뒤로 밀기
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

---

📊 비교 요약

정렬 방식	최선	평균	최악	안정 정렬
버블 정렬	O(n)	O(n²)	O(n²)	✅ Yes
선택 정렬	O(n²)	O(n²)	O(n²)	❌ No
삽입 정렬	O(n)	O(n²)	O(n²)	✅ Yes

---

🧩 실습 예시

#include <stdio.h>

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int data1[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int data2[10], data3[10];

    // 배열 복사
    for (int i = 0; i < 10; i++) {
        data2[i] = data1[i];
        data3[i] = data1[i];
    }

    bubbleSort(data1, 10);
    selectionSort(data2, 10);
    insertionSort(data3, 10);

    printf("Bubble Sort: ");
    printArray(data1, 10);
    printf("Selection Sort: ");
    printArray(data2, 10);
    printf("Insertion Sort: ");
    printArray(data3, 10);

    return 0;
}

---

🧠 마무리

정렬 알고리즘은 리버싱에서는 직접적으로 등장하진 않지만, 아래와 같이 간접적으로 분석 대상이 되기도 한다:

• 배열 재정렬 루틴 (ex. 서버 패킷 내부 정렬)
• 값 기준의 오름차순 정렬 분석 시, 버블 정렬/삽입 정렬 패턴이 보일 수 있음
• 리버싱 중 특정 정렬된 테이블을 기준으로 순차 접근 알고리즘 분석

---

필요하다면 위 내용을 .h/.c로 나눠 모듈화하거나,
퀵 정렬, 병합 정렬, 힙 정렬로 확장된 내용도 제공할 수 있어.
다음 챕터로 퀵소트/머지소트, 또는 정렬 알고리즘의 시간 복잡도 실험 분석으로 갈까?