정렬 알고리즘 (Sort Algorithm) - 삽입 정렬 (Insertion Sort)

  삽입 정렬로 자기 앞의 값들을 보면서 자기보다 작은 값이 있을 때 까지 교환을 합니다. 각 단계별로 기준 값의 index는 하나씩 늘어나게 되고 index-1까지의 값들은 이미 정렬이 되어진 상태입니다.

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

typedef int boolean;
const boolean FALSE = 0;
const boolean TRUE = 1;

// comment와 함께 배열 내용을 출력 
void printArray(char* comment, int A[], int N);
// 정렬 알고리즘 
void insertionSort(int A[], int N);

int main(int argc, char *argv[])
{
	int A[] = {22, 37, 15, 19, 12};
	
	printf("Insertion Sort\n");
	printArray("Input  : ", A, 5);
	insertionSort(A, 5);
	printArray("Output : ", A, 5);
	printf("\n");
	
	system("PAUSE");	
	return 0;
}

void insertionSort(int A[], int N)
{
	int i, j, temp;
	
	for(i=1 ; i<N ; i++) {
		/* 수정 전 Version 
		for(j=i ; j>0 j--) {
			if(A[j]<A[j-1]) {
				temp = A[j-1];
				A[j-1] = A[j];
				A[j] = temp;
			} else {
				break;
			}		
		}
		*/
		for(j=i ; (j>0&&A[j]<A[j-1]) ; j--) {
			temp = A[j-1];
			A[j-1] = A[j];
			A[j] = temp;
		}
	}
}

void printArray(char* comment, int A[], int N)
{
	int i;
	
	printf("%s", comment);
	for(i=0 ; i<N ; i++) {
		printf("%d\t", A[i]);
	}
	printf("\n");
}