[정렬] 삽입정렬

삽입할 인덱스를 기준으로 왼쪽은 정렬이 되어있다고 가정

 

삽입할 인덱스 보다 우선순위가 높은 인덱스의 위치를 발견하면 해당 인덱스 다음의 위치에 삽입함

반대로 자기보다 우선순위가 낮으면 해당 인덱스를 +1인덱스의 위치로(한칸)옆으로 이동시킴

 

 

ex) 3,4,2,1

인덱스 1의 위치하는 값 4는 3보다 크므로 인덱스 변하지 않음.

 

인덱스 2의 위치한 값 2는 인덱스 1에 위치한 값 4보다 우선수위가 높음 4는 +1 인덱스로 위치함.  3441 (2는 다른 변수에 값을 저장하고 있음)

 

인덱스 0의 값 3은 2보다 우선순위가 낮음 그러므로 +1 인덱스오 위치함 3341(마찬가지로 2는 다른 변수에 값을 저장하고 있음)

 

배열에 인덱스 0보다 작은 값을 나타내는 부분이 생각날텐데 그래서 두번째 for의 조건을 보면 j는 -1이 되고 조건이 맞지 않아 두번째 for문을 벗어나면서 현재 j 값인 -1의 +1값인 arr[0]에 2값을 대입할 수 있음

 

위과정 반복

 

 

void InsertSort(int arr[], int n){
    int i, j, insertIdx;
 
    for (i = 1; i < n; i++){
        insertIdx = arr[i];
        for (j = i - 1; j >= 0; j--){
            if (arr[j] > insertIdx){
                arr[j + 1] = arr[j];
            }
            else
                break;
        }
        arr[j + 1] = insertIdx;
    }
}
 
 
int main(){
 
    int arr[4] = { 3, 4, 2, 1 };
 
    InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
 
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        printf("%d: %d\n", i+1, arr[i]);
    return 0;
}