[자료구조] 정렬 알고리즘

1. 버블 정렬 (Bubble Sort)

 

인접한 두 수를 비교해서, 크기가 순서대로 되어 있지 않으면 서로 교환한다.

이 과정을 반복해서 가장 큰 수가 맨 뒤로 떠오르는 방식 like 거품

 

시간 복잡도 (문제를 해결하는데 걸리는 시간과 입력의 함수 관계)

• 최악: O(n²)
• 최선 (이미 정렬된 경우): O(n) → 개선된 버전일 때
• 평균: O(n²)

[4, 6, 2, 7, 5] → 비교 4-6 (X), 6-2 (swap), 6-7 (X), 7-5 (swap) → [4, 2, 6, 5, 7]

 

2. 선택 정렬 (Selection Sort)

 

아직 정렬되지 않은 부분에서 가장 작은 값을 선택해서 맨 앞의 요소와 교환한다. 이 과정을 계속 반복!

 

시간 복잡도:

• 최악, 최선, 평균 모두 O(n²)
• 교환 횟수가 적음 (항상 n번만 교환)

[4, 6, 2, 7, 5] → 2가 제일 작음 → 2 와 4 swap → [2, 6, 4, 7, 5]

 

3. 삽입 정렬 (Insertion Sort)

 

현재 값을 앞의 정렬된 부분과 비교하면서 알맞은 위치에 삽입한다. (보통 우리가 생각하는 정렬방식)

 

시간 복잡도:

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

[4, 6, 2, 7, 5] → 6은 4보다 크니 그대로 → 2는 4보다 작으니 앞으로 → [2, 4, 6, 7, 5]

 

버블 정렬 코드 

 

#include <stdio.h>
#include <stdlib.h>

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

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


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

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


    return 0;
}

• arr[10]은 10개의 정수를 가진 배열이다.
• temp는 두 값을 교환할 때 사용할 임시 변수이다.

 

1. for문으로 초기 배열을 출력한다.

 

2. 이중 반복문

• • 바깥 루프 i는 9회 반복 
  • 정렬된 큰 수는 뒤로 가므로 안쪽 루프는 점점 비교 횟수가 줄어든다 
  • arr[j] > arr[j + 1]일 때 자리 교환

 

3. 정렬 완료 후 배열을 출력하면 아래와 같다.

입력 배열: 4 6 2 7 5 1 8 9 10 3
정렬 결과: 1 2 3 4 5 6 7 8 9 10

---

선택 정렬 구현해보기

#include <stdio.h>

int main() {
    int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int min_idx, temp;

    // 초기 배열 출력
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    // 선택 정렬 코드
    for (int i = 0; i < 9; i++) {
        min_idx = i;
        for (int j = i + 1; j < 10; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 최솟값을 현재 위치(i)와 교환
        temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }

    printf("\n");

    // 정렬된 배열 출력
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}

삽입 정렬 구현해보기

#include <stdio.h>

int main() {
    int arr[10] = { 4, 6, 2, 7, 5, 1, 8, 9, 10, 3 };
    int key, j;

    // 초기 배열 출력
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    // 삽입 정렬
    for (int i = 1; i < 10; i++) {
        key = arr[i];
        j = i - 1;

        // key보다 큰 값을 오른쪽으로 이동
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // key를 알맞은 위치에 삽입
        arr[j + 1] = key;
    }

    printf("\n");

    // 정렬된 배열 출력
    for (int i = 0; i < 10; i++) {
        printf("%d ", arr[i]);
    }

    return 0;
}