[Sort]삽입정렬

1.소개

삽입정렬은 배열의 이미 정렬된 배열를 검사하면서

자신의 자리를 찾아 가는 정렬입니다.

2. 장점

구현이 간단하다.

이미 정렬되있을 경우 효율이 좋다.

3 단점

배열이 길어질수록 효율이 떨어진다.

최악의 경우  복잡도가 O(n²)이 될 수 있다.

4. 정렬 방법

0123456789101112131415

- 제일 처음 요소는 정렬이 되있다고 가정한다.

- 점차 검사요소는 커진다.

- Key 값을 검사하다가 자신보다 큰수(오름차순)가 나오면

배열의 요소를 한요소씩 밀다가 작은수(오름차순) 이나오면

그 자리에다가 Key 값을 넣는다.

5. 코드

void InsertSort(int *data, int size);
 
int main()
{
    int testArr[] = { 4,3,2,1 };
    InsertSort(testArr, 4);
    for (int i = 0; i < 4; ++i) 
    {  
        cout << testArr[i] << " ";
    } 
    cout << endl;
    return 0;
}
 
void InsertSort(int *data, int size)
{
    int temp, i, j;
    for (i = 1; i < size; ++i)
    {
        temp = data[i];
        for (j = i - 1; j >= 0 && data[j] > temp; j--)
        {
            data[j + 1] = data[j];
        }
        data[j + 1] = temp;
    }
}