정렬 - 선택 정렬과 삽입 정렬

선택 정렬

- 선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법

- 가장 작은 것을 선택하는 데에 n번, 앞으로 보내는 데에 n번의 연산으로 O(n2)의 시간 복잡도를 가짐

 

* 배열 선언

#define _CRT_SECUCRE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <limits.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, min, index;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < n; i++) {
        min = INT_MAX;
        for (int j = i; j < n; j++) {
            if (min > a[j]) {
                min = a[j];
                index = j;
            }
        }
        swap(&a[i], &a[index]);
    }
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    system("pause");
    return 0;
}

삽입 정렬

 

 

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

- 들어갈 위치를 선택하는 데에 n번, 선택하는 횟수로 n번이므로 O(n2)의 시간 복잡도를 가짐

 

* 삽입 정렬 수행하기

int main(void) {
    int n, min, index;
    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 + i]);
            j--;   
        }
    }
    
    for (int i = 0; i < n; i++) 
    printf("%d ", a[i]);
    system("pause");
}