//Insertion Sort 2 - Optimization

* 최적화1 - 비교조건 줄이기

#include <stdio.h>
#include <malloc.h>

#define MAX 10

void optimized1_insertion_sort(int arr[], int n) {

    for (int i = 1; i <= n; ++i) {
        int j = i;
        int tmp = arr[i];

        // 1~10 index 를 사용하기 때문에 j > 0 조건이 필요없음
        while (arr[j - 1] > tmp) {
            arr[j] = arr[j - 1];
            --j;
        }

        arr[j] = tmp;
    }
}

void print(int arr[], int n) {
    printf("Result :");
    for (int i = 1; i <= n; ++i) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}
   
int main()
{
    int arr[MAX + 1] = {-1, 10, 5, 1, 4, 9, 2, 6, 8, 7, 3 };

    optimized1_insertion_sort(arr, MAX);

    print(arr, MAX);

    return 0;
}

---

* 최적화2 - Indirect Sort 사용 (Memory 연산으로만 동작하는 경우가 아닌, File I/O 등의 Data 연산이 이루어질 때)

- 실제 데이터가 아닌 Index를 정렬 후에, Data 를 정렬하는 방법

#include <stdio.h>
#include <malloc.h>

#define MAX 10

void indirect_insertion_sort(int arr[], int index[], int n) {

    for (int i = 0; i < n; ++i) {
        index[i] = i;
    }

    for (int i = 1; i < n; ++i) {
        int j = i;
        int tmp = index[i];

        while (j > 0 && arr[index[j - 1]] > arr[tmp]) {
            index[j] = index[j - 1];
            --j;
        }

        index[j] = tmp;
    }
}

void rearrange(int arr[], int index[], int n) {
    int *p = (int*)malloc(sizeof(int) * n);

    for (int i = 0; i < n; ++i) {
        p[i] = arr[index[i]];
    }

    for (int i = 0; i < n; ++i) {
        arr[i] = p[i];
    }

    free(p);
}

void print(int arr[], int n) {
    printf("Result :");
    for (int i = 0; i < n; ++i) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}
   
int main()
{
    int arr[MAX] = { 10, 5, 1, 4, 9, 2, 6, 8, 7, 3 };
    int index[MAX];

    indirect_insertion_sort(arr, index, MAX);
    rearrange(arr, index, MAX);

    print(arr, MAX);

    return 0;
}

---

* 최적화3 - Binary Search 사용