실력키우기 - 자료처리 [Insertion Sort]

필요한 지식

Memmove

함수의 원형

void * memmove ( void * destination, const void * source, size_t num );

source가 가리키는 곳 부터 num바이트 만큼을 destination이 가리키는 곳으로 옮긴다.

삽입정렬

삽입 정렬 (insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void Insertion_sort(int* res, int index);
void Print(int *res,int index);
 
int main(int argc, char** argv){
    
    int n;
    int *res;
    int index=0;
    
    scanf("%d",&n);
    res = (int *)malloc(sizeof(int *)*n);
    if (!(n>=4&&n<=100)) {
        return -1;
    }
    while (n>0) {
        scanf("%d",&res[index]);
        index++;
        n--;
    }
    Insertion_sort(res, index);
    
    
    return 0;
}
 
void Insertion_sort(int* res, int index){
    
    int value = 0;
    int i,j;
    
    for (i=1; i<index; i++) {
        if (res[i-1]<res[i])continue;
        
        value = res[i];
        
        for (j=0; j<i; j++) {
            if (res[j]>value) {
                memmove(&res[j+1], &res[j], sizeof(res[0]*(i-j)));
                
                res[j]=value;
                break;
            }
        }
        Print(res, index);        
    }    
}
 
 
void Print(int *res,int index){
    int i;
    for (i=0; i<index; i++) {
        printf("%d ",res[i]);
    }
    printf("\n");
}