뇌를 자극하는 알고리즘 - 5. 정렬 : Insertion Sort

구현 소스

InsertionSort.h

#ifndef INSERTIONSORT_H
#define INSERTIONSORT_H

#include <stdio.h>
#include <string.h>

void InsertionSort(int Data[], int size);

#endif

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

InsertionSort.cpp

#include "InsertionSort.h"


void InsertionSort(int Data[], int size){
	int i;
	int j;
	int value;

	int k;

	for(i=1 ; i<size ; i++)
	{
		if(Data[i-1] <= Data[i])
			continue;

		value = Data[i];

		for(j=0; j<i ; j++)
		{
			if(Data[j] > value)
			{
				memmove(&Data[j+1], &Data[j], sizeof(int) * (i-j));
				// memmove 함수
				// - 첫 번째 매개 변수는 원본 데이터가 옮길 새로운 메모리의 주소
				// - 두 번째 매개 변수는 원본 데이터가 있는 주소
				// - 세 번째 매개 변수는 이동시킬 데이터의 양(byte)
				Data[j] = value;
				break;
			}
		}
		printf("  -- Current Array : ");
		for(k=0; k<size ; k++)
			printf("%d, ",Data[k]);
		printf("\n");
	}

}

// Data[] = {5,4,1,2,3}
// - 첫번째 루프 i=1
//  ~ Data[0] <= Data[1] (5<=4) 이 성립하지 않으므로 value = Data[1] = 4
//  ~ j=0 ; j<1; j++ 
//    ~ Data[0] > value (5>4)이므로
//    ~ memmove( &Data[1] , &Data[0], 4 * (1-0))
//      ~ Current Array : 5 5 1 2 3
//    ~ Data[0] = value = 4 
//    ~ Array : 4, 5, 1, 2, 3

//  - 두번째 루프 i=2
//   ~ Data[1] <= Data[2] (5<=1) 이 성립하지 않으므로 value = Data[2] = 1
//   ~ j=0; j<2; j++
//    ~ Data[0] > value (4>1)이므로
//    ~ memmove( &Data[1], &Data[0], 4 * (2-0)
//      ~ Current Array : 4, 4, 5, 2, 3
//    ~ Data[0] = value = 1
//    ~ Array : 1, 4, 5, 2, 3

//  - 세번째 루프 i=3
//   ~ Data[2] <= Data[3] (5<=2) 가 성립하지 않으므로 value = Data[3] = 2
//   ~ j=0; j<3; j++
//   ~ Data[1] > value (4>2) 이므로
//   ~ memmove( &Data[2], &Data[1], 4 * (3-1) )
//     ~ Current Array : 1, 4, 4, 5, 3
//   ~ Data[1] = value = 2
//   ~ Array : 1, 2, 4, 5, 3

//  - 네번째 루프 i=4
//   ~ Data[3] <= Data[4] (5<=3) 가 성립하지 않으므로 value = Data[4] = 3
//   ~ j=0; j<4; j++
//   ~ Data[2] > value (4>3) 이므로
//   ~ memmove( &Data[3], &Data[2], 4 * (4-2) )
//     ~ Current Array : 1, 2, 4, 4, 5
//   ~ Data[2] = value = 3
//   ~ Array : 1, 2, 3, 4, 5

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

main.cpp

#include "InsertionSort.h"


int main(){
	int i;
	int Data[] = {5,4,1,2,3};

	printf(" Data : ");
	for(i=0;i<5;i++)
		printf("%d, ",Data[i]);
	printf("\n");

	

	printf("--- Insertion sorting ---- \n");
	InsertionSort(Data, sizeof(Data)/sizeof(int));
	printf(" Data : ");
	for(i=0;i<5;i++)
		printf("%d, ",Data[i]);
	printf("\n");

	return 0;
}

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

실행 결과