삽입정렬 , 선택정렬, 버블정렬 비교

삽입 정렬 (insertion sort)

자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교. 위치를 찾아 삽입.

두번째 자료부터 시작해서 앞 자료들과 비교해 삽입할 위치를 지정 후 나머지 자료를 뒤로 옮기고 선택 자료를 삽입.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
    int x[5] = { 0 };
    int key;
    int size = sizeof(x) / sizeof(int);
    int tmp;
    int j;
    for (int i = 0; i < size; i++)
    {
        scanf("%d", &x[i]);
    }
    for (int i = 1; i < size; i++)
    {
        key = x[i];
        for (j = i - 1; j >= 0 && x[j] > key; j--)
        {

                x[j + 1] = x[j];
        }
        x[j + 1] = key;
    }
    for (int i = 0; i < size; i++)
    {
        printf("%d", x[i]);
    }

}

선택 정렬 (selection sort)

 

제자리정렬 알고리즘

-입력한 배열 외 추가 메모리 필요 X

순서마다 원소의 위치는 정해져있음. 어떤 원소를 넣을지 결정.

가장 작은 값을 맨 앞으로 둔다.

index 0 부터 그 뒷 숫자들과 비교해서 가장 작은 숫자와 위치를 swap

index가 증가될수록 앞에서부터 비교 횟수는 줄어든다.

 

배열의 N-1개의 아이템을 모든 싸이클마다 비교해야함 시간복잡도 O(n^2)

싸이클마다 1회 교환한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
    int x[5] = { 0 };
    int size = sizeof(x) / sizeof(int);

    int small;
    int tmp;
    for (int i = 0; i < size; i++)
    {
        scanf("%d", &x[i]);
    }
    for (int i = 0; i < size-1; i++)
    {
        small = i;
        for (int j = i+1; j < size; j++)
        {
            if (x[j] < x[small])
            {
                small = j;
            }
        }
        if (small != i)
        {
            tmp = x[i];
            x[i] = x[small];
            x[small] = tmp;
        }
    }
    for (int i = 0; i < size; i++)
    {
        printf("%d\n", x[i]);
    }
}

 

버블정렬

인접한 두 원소 비교

자료를 비교하며 교환하면서 정렬함.

가장 큰 자료를 맨 뒤로 보냄.

회차가 지날수록 정렬을 맨뒤에서부터 하나씩 제외함.

 

최악의 경우에는 모든 아이템을 교환해야 함.

시간 복잡도는 O(n^2)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
    int x[5] = { 0 };
    int size = sizeof(x) / sizeof(int);
    int tmp;
    for (int i = 0; i < size; i++)
    {
        scanf("%d", &x[i]);
    }
    for (int i = size-1; i> 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (x[j + 1] < x[j])
            {
                tmp = x[j+1];
                x[j + 1] = x[j];
                x[j] = tmp;
            }
        }
    }
    for (int i = 0; i < size; i++)
    {
        printf("%d", x[i]);
    }
    
}

 

 

삽입>선택>버블

시간복잡도는 모두 O(N^2)

 

버블정렬은 N-1 비교에 N번 교환. 

선택정렬은 비교수는 같지만 교환은 사이클당 한번. 버블정렬보다 2배 빠를 수도 있다.

삽입정렬은 모두 비교하지 않고 필요한 부분만 비교하기 때문에 가장 빠르다.

 

삽입정렬은 최선의 경우에선 시간복잡도가 O(N)이 될 수 있다.

삽입정렬, 선택정렬 모두 최악의경우, 평균적 경우 에서 O(N^2)

셋중에 제일 빠른 삽입정렬도 배열이 길어질수록 효율성이 떨어진다.