2021.2.20 TIL : [자료구조] 선택 정렬과 삽입정렬

선택 정렬이란 데이터 중에 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로 O(N^2)의 시간 복잡도를 가진다. 즉, 의사코드를 적어보면 다음과 같다. C언어로 구현한 선택 정렬 코드는 여기에서 확인할 수 있다. 

 

for(int i = 0; i < N; i++)
	i 번째 숫자부터 N번째 숫자까지 모두 확인하여 가장 작은 수를 찾아낸다. 
    가장 작은 숫자를 i번째 숫자와 바꾼다. 

 

삽입 정렬이란 각 숫자를 적절한 위치에 삽입하는 정렬 기법으로, 들어갈 위치를 선택하는 데에 N번, 선택하는 횟수가 N번이니까 O(n^2)의 시간 복잡도를 가진다. 즉, i가 0에서 N까지 1씩 증가하는 수라고 할 때, i번째 자리의 값이 i-1번째 값보다 작은 경우, i번째 값과 i-1번째 값을 바꾸는 과정을 반복하는 것이다. 코드를 C언어로 적어보면 다음과 같다. 

 

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

int a[SIZE];

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

int main(void){
    printf("How many elements: ");
    scanf("%d", &n);
    for(int i = 0; i < n ; i++){
        scanf("%i", &a[i]);
    }
	
    //들어갈 숫자를 선택하는 루프
    for (int i = 0; i < n; i++){
        int j = i;
        //들어갈 위치를 선택하는 루프
        //j < n-1 조건을 통해서 a[n-1]과 a[n](데이터에 포함되지 않는 값)이 swap되는 것을 막아줌
        while(j >= 0 && a[j] > a[j+1] && j < n - 1){
            swap(&a[j], &a[j+1]);
            j--;
        }
    }

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

 

 

선택 정렬과 삽입 정렬은 시간 복잡도가 O(N^2)이기 때문에 효율적으로 평가받지는 못하지만 구현하기에 가장 간단한 형태의 알고리즘이다.