정렬되었을 때 새로운 수가 입력되었을 때 빅오는 O(n) = n-1;
정렬되지 않았을 때 정렬할 때 빅오는 O(n)= n^2
insertSort(void *data, int size, int esize, int (*compare)(const void *key1, const void *key2))
{
정렬되지 않았을 때 정렬할 때 빅오는 O(n)= n^2
insertSort(void *data, int size, int esize, int (*compare)(const void *key1, const void *key2))
{
char *a = data;
void *key;
if((key = (char *)malloc(esize)) == NULL)
void *key;
if((key = (char *)malloc(esize)) == NULL)
return -1;
int i,j;
for(j=0; j < size; j++)
{
for(j=0; j < size; j++)
{
memcpy(key, &a[j*esize], esize);
i = j - 1;
//복사할 위치 결정
while( i >= 0 && compare(&a[i * esize] , key) > 0)
{
i = j - 1;
//복사할 위치 결정
while( i >= 0 && compare(&a[i * esize] , key) > 0)
{
memcpy(&a[(i+1) * esize], &a[i*esize],esize);
i--;
i--;
}
//자기보다 큰 작은 수가 나왓으므로 i의 다음번째 인덱스에 값을 복사한다.
memcpy(&a[(i+1)*esize], key, esize);
//자기보다 큰 작은 수가 나왓으므로 i의 다음번째 인덱스에 값을 복사한다.
memcpy(&a[(i+1)*esize], key, esize);
}
free(key);
return 0;
free(key);
return 0;
}
'OS이야기' 카테고리의 다른 글
| container_of 매크로 (1) | 2011.10.11 |
|---|---|
| 커널 (0) | 2011.10.11 |
| 커널 시작 과정 (0) | 2011.09.22 |
| 실시간 CPU 스케줄링 - Proportional Share 스케줄링 (0) | 2010.07.30 |
| OS이야기 - 분산 조정 (1) | 2010.07.27 |
