삽입 정렬

이번에 소개 드릴 삽입 정렬은 별도의 메모리를 필요로 하지 않는 '개선된 선택 정렬'과 유사하다고 느끼실 수 있습니다. 

하지만 개선된 선택 정렬과는 전혀 다른 방법으로 정렬을 이뤄 나가는데 아래의 그림을 통해 설명해 드리도록 하겠습니다.

위 그림의 배열은 정렬이 완료된 부분과 그렇지 않은 부분으로 니뉘어져 있습니다. 즉 삽입 정렬은 정렬 대상을 두 부분

으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부븐의 특정 위치에 '삽입'해 가면서  정렬을 진행하는 알고리즘입니다.

다음 그림을 통해 5, 3, 2, 4, 1의 오름차순 정렬과정을 보도록 합시다.

첫 번째 데이터와 두 번째 데이터를 비교하여, 정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬이 시작됩니다.

그리고 이로 인해 첫 번째 데이터와 두 번째 데이터가 정렬이 완료된 영역(회색 부분)을 형성하게 됩니다.

이어서 세 번째, 네 번째 데이터가 정렬이 완료된 영역으로 삽입이 되면서 정렬을 이어 나가는데, 

정렬된 상태로 삽입하기 위해서는 특정 위치를 바꿔야 하고, 비우기 위해서는 데이터들을 한 칸씩 뒤로 미는 연산을 수행해야 합니다.

참고로 구현에 도움이 되는 말을 하자면

"정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬대상이다."

"삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있다."

위에서 언급한 '데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾는다'라는 것이 무엇을 의미하는지는 아래의 그림을 보시면 됩니다.

위 이미지를 보시면 삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 없어지는데, 

이 이유는 어차피 정렬된 영역에서 삽입의 위치를 찾는 것이니, 삽입위치를 찾으면서 삽입을 위한 공간의 

마련을 병행할 수 있게 되기 때문입니다.

그럼 코드를 보고 마치도록 하겠습니다.

#include

void InsertionSort(int arr[], int Len) {
	int j = 0, DataSave = 0;
	for (int i = 1; i < Len; i++) {
		DataSave = arr[i];
		for (int j = i - 1; j >= 0; j--) {
			if (DataSave < arr[j]) {
				DataSave = arr[j];
			}
			else {
				break;
			}
		}
		arr[j] = DataSave;
	}
}

int main(){
    int arr[5] = { 5, 3, 2, 4, 1 };
    
    InsertionSort(arr,sizeof(arr)/sizeof(int));

    for(int i=0;i<5;i++) {
        printf('%d  ",arr[i]);
    }
    puts("");

    return 0;
}