[Sort] 삽입정렬

1. 소개

삽입정렬은 배열의 모든 요소를 앞부터

차례로 비교하여 자신의 위치를 찾아 정렬을 완성하는 알고리즘입니다.

2. 장점 & 단점

구현이 간단합니다.

배열이 길어질수록 효율이 떨어집니다. ( 최악의경우 n(n-1) /2, O(n²) ) 

3. 정렬 순서

< 조건 >

오름차순

- 정렬되지 않은 임의의 수가 있습니다.

- Key 값은 2번째부터 시작합니다.

- 그리고 자신의 앞부터 검사를 하여 조건에 맞으면 교환을 합니다.

- 조건에 맞으므로 교환!

- 다음 key 값은 4, 조건 찾기

- 조건에 맞는게 없으므로 다음 key값 

- 5를 key값으로, 당연히 다없겠네 ..

- 검사중

- 마지막 key 값인 3 !

- 5보다 작으므로 교환!

- 그다음 4도 조건에 부합되므로 교환!

- 이로써 모든 부분이 오름차순으로 정렬이 끝났습니다.

4. 코드

#include <stdio.h>
 
 
// key값을 잡아 조건을 검사한뒤 조건에 맞으면 하나씩 뒤로 밀어낸다음 
// 조건이 끝나면 밀어내고 남은 자리에 key 값을 넣는 형식
void InsertionSort(int data[], int dataSize, bool isAscending)
{
    int i, j, key;
 
    for (i = 1; i < dataSize; i++)
    {
        // 키값
        key = data[j = i];
 
        while (--j >= 0 && (isAscending ? key < data[j] : key > data[j]))
        {
            data[j + 1] = data[j];
        }
        data[j + 1] = key;
    }
 
}
 
 
 
int main()
{
    int data[] = {2,1,4,5,3};
    int dataSize = sizeof(data) / sizeof(data[0]);
    int i;
    InsertionSort(data, dataSize, true);
    for (int i = 0; i < dataSize; i++)
    {
        printf("%d ", data[i]);
    }printf("\n");
 
    return 0;
}