7. 선택 정렬과 삽입 정렬 - 선택 정렬 배열선언/ 정렬 수행하기/ 삽입 정렬의 과정/삽입 배열 선언 /삽입 정렬 수행

선택정렬

선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로, O(N^2)의 시간 복잡도를 가진다.

선택정렬 - 배열 선언

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

int a[SIZE];

int swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
//정렬은 두개의 원소의 위치를 바꾸는 경우가 많으므로, 미리 swap 함수를 만들어 두는게 현명하다.

선택정렬 수행하기

int main(void){
    int n, min, index; // min = 한번 검색 할 때마다 발견되는 가장 작은 값
    scanf("%d", &n); //원소의 갯수 n값 입력 받기
    for (int i = 0; i <n ; i++) scanf("%d", &a[i]);
    for (int i = 0; i <n-1 ; i++){
        min = INT_MAX;
        for(int j = i; j < n; j++){
            if (min > a[j]){
                min = a[j];
                index = j; //index는 가장 작은 값이 존재하는 위치(인덱스)
            }
        }
        swap(&a[i], &a[index]); //자리 바꾸기
    }
    for(int i = 0; i < n ; i++) printf("%d ", a[i]);
    system("pause");
    return 0;
}

삽입 정렬

삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수로 N번이므로, O(N^2)의 시간 복잡도를 가진다. 이론상으론 선택 정렬과 동일한 시간 복잡도를 가지나, 일반적으론 삽입 정렬의 처리 속도가 더 빠르다.

 

삽입정렬 - 배열 선언

#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;
    sacnf("%d",&n);
    for (int i = 0; i < n ; i++){
        int j = i; //j:어디에 들어갈지 고르는 대상 원소
        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]);
    system("pause");
    return 0;
}

 

요약

선택정렬과 삽입 정렬은 시각복잡도가 O(N^2)으로, 시간상으론 다소 비 효율적이지만, 그 구현이 가장 간단한 형태의 정렬 알고리즘이다.