Insertion sort(삽입 정렬)

Insertion Sort

- 밀어서 삽입정렬이라고 이해하자

#include <stdio.h>
#include <stdlib.h>

void insertionSort(int* arr, int size)
{
    int i, j;
    int key;

    for( i=1; i<size; i++ )
    {
        key = arr[i];
        for( j=i-1; j>=0; j-- )
        {
            if( key < arr[j] )
                arr[j+1] = arr[j];

            else {
                //arr[j+1] = key; (X)
                break;
            }
        }
        arr[j+1] = key; // key가 제일 작아서 맨 앞애까지 오는 경우
    }

    for( i=0; i<size; i++ )
        printf("%d ", arr[i]);

}
int main (void)
{
    int size;
    int* arr;

    scanf("%d", &size);

    for ( int i=0; i<size; i++ )
        scanf("%d", &arr[i]);

    insertionSort(arr, size);
}