[C언어] 삽입 정렬(Insertion Sort)

최악의 경우로 정렬되어있는 경우엔 버블 정렬과 총 비교횟수가 같으나 ( n(n-1)/2 ) ,

최선일 경우엔 (n-1)번의 비교만 이루어지기 때문에 

 

평균 비교횟수로 따지면 버블정렬보다 살짝 더 낫다. ( 평균 비교횟수 = (n^2+n-2)/4 ) 

memmove(&a,&b,c) : b에 있는걸 a로 이동시키되 c만큼의 크기를 옮긴다  (#include <string.h>)

------------------------------------------------------------------------------------------------

#include <stdio.h>
#include <string.h>
 
void InsertionSort(int DataSet[],int Length){
    int i=0;
    int j=0;
    int value=0;
 
    for(i=1;i<Length;i++){
        if(DataSet[i-1]<=DataSet[i]){
            continue;
        }
 
        value=DataSet[i];
 
        for(j=0;j<i;j++){
            if(DataSet[j]>value){
                memmove(&DataSet[j+1],&DataSet[j],sizeof(DataSet[0])*(i-j));
                DataSet[j]=value;
                break;
            }
        }
    }
}
 
int main(){
    int DataSet[]={6,4,2,3,1,5};
    int Length=sizeof(DataSet)/sizeof(DataSet[0]);
    int i=0;
 
    InsertionSort(DataSet,Length);
 
    for(i=0;i<Length;i++){
        printf("%d ",DataSet[i]);
    }
    printf("\n");
    
    return 0;
}