[C언어 선택정렬 알고리즘] 삽입정렬 구현하기

💡 이번에는 삽입정렬 하는 법을 배워보았다.

문제

💡 사용자가 입력한 값이 오름차순으로 삽입정렬되게 코드를 구현하시오

당연히 없는 문제기에 대충 내가 만들었다.

해답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000

int a [SIZE];

int swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0 ; i < n - 1 ; i++) {
        int j = i;
        while (j >=0 && a[j] > a[j + 1]) {
            swap(&a[j], &a[j + 1]);
            j--;
        }
    }
    for (int i = 0 ; i < n ; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

설명

삽입정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다.

들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번이므로 $O(N제곱)$의 시간 복잡도를 가진다.

선택정렬과 흡사한 시간복잡도를 가지고 있다고 볼 수 있지만 삽입정렬은 일반적으로 선택정렬보다 조금 더 빠르다.

[C언어 선택정렬 알고리즘] 선택정렬 구현하기 와 비교해서 볼 수 있다.

main 함수

int main(void) {
    int n;
    scanf("%d", &n);

    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = 0 ; i < n - 1 ; i++) {
        int j = i;  // 어디에 들어갈지 정하는 대상원소

				// 현재 왼쪽에 있는 값이 오른쪽에 있는 원소보다 크다면 위치를 서로 바꾸도록 해줌
        while (j >=0 && a[j] > a[j + 1]) {
            swap(&a[j], &a[j + 1]);
            j--;
        }
    }

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

    return 0;
}

여기서도 n 의 정체가 무엇인지 전혀 모르겠다.

printf 로 찍어봐도 모르겠다 데헷-! _〆(ﾟ▽ﾟ*)

---

마치며..

자료구조가 뭐 이렇게 많은지..

컴퓨터야 알아서 해주면 안되겠니..?