자료구조 InsertionSort

/*
1. 데이터 집합에서 대상이 되는 요소들을 선택한다.
이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 증가할 때 마다 1개씩 커집니다.
정렬대상의 최대 범위는 (크기-1)

2. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 갖고 잇는지 확인합니다.
그렇지 않다면 이 요소를 적절한 곳을 정렬대상 내에서 찾습니다.
적절한 곳은 데이터집합 가장 왼쪽부터 했을 때 자신보다 더 작은 요소가 없는 위치입니다.

3. 뽑아 든 요소를 삽입할 적절한 곳을 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를
한 자리씩 오른쪽으로 이동시키고, 새로 생긴 빈자리에 삽입합니다.

memmove(주소, 넣을 값의 주소, 크기)
*/

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

void InsertionSort(int DataSet[], int Length) {
        for (int i = 1; i < Length; i++) {
                if (DataSet[i] > DataSet[i - 1]) continue;
                int value = DataSet[i];
                for (int j = 0; j < i; j++) {
                        if (DataSet[i] == DataSet[j]) {
                                memmove(&DataSet[j + 1], &DataSet[j], sizeof(int));
                                DataSet[j] = value;
                                break;
                        }
                }
        }
}

void main() {
        int DataSet[] = { 6,4,2,3,1,5 };
        int Length= sizeof(DataSet) / sizeof(int);
        InsertionSort(DataSet, Length- 1);
        for (int i = 0; i < Length; i++)
                printf("%d", DataSet[i]);
        printf("\n");
}