Indirect Insert Sorting Algorithm

1. 간접 정렬이란 본래 레코드의 배열은 전혀 손대지 않고,
따로 만든 인덱스(index)의 배열을 조작하는 방법.

void inderect_insert_sort(int a[], int index[], int n)
{
int i, j, t;

for (i = 0; i < n; i++) //인덱스 배열 초기화
index[i] = i;
for (i = 1; i < n; i++) //삽입정렬
{
t = index[i];
j = i;

while (a[index[j-1]] > a[t] && j > 0) //삽입위치 찾음
{
index[j] = index[j-1] //인덱스 배열 조정
j--;
}
index[j] = t; //삽입
}
}

2. indirect_insert_sort()는 비교를 위해서는 a배열을 사용하지만, while 루프 내의 실제 교환 작업은 index배열을 사용한다.
이렇게 간접정렬을 하고 나면 실제로 a배열에는 아무 변동이 없다. 그러나 그 정렬된 순서는 index배열에 저장되어 있다.

3. 정렬된 상태라고 가정하고, 제일 첫번째 레코드가 무엇인지 알고자 한다면, a[index[0]]와 같이 하면 되고, i번째 레코드가 무엇인지 알려면 a[index[i]]와 같이 간접적으로 접근한다.