440,441 Members | 1,766 Online Need help? Post your question and get tips & solutions from a community of 440,441 IT Pros & Developers. It's quick & easy.

# an implementation of insertion sort, insert without move element

 P: n/a Suppose we have an array a[N], the idea is: build another array, int next[N], for each 0 void myInsertionSort(int a[], int size) { int *next, *tmp; next = malloc(size * sizeof(int)); tmp = malloc(size * sizeof(int)); int first = 0, last = 0, max; int i; for(i = 1, max = a; i < size; i++){ if(a[i] < max){ if(a[i] <= a[first]){ next[i] = first; first = i; }else{ int j = first; while(a[i] a[next[j]]) j = next[j]; next[i] = next[j]; next[j] = i; } }else{ next[last] = i; max = a[i]; last = i; } } int j; for(i = 0, j = first; i < size; i++){ tmp[i] = a[j]; j = next[j]; } for(i = 0; i < size; i++) a[i] = tmp[i]; free(next); free(tmp); } int main() { int a[] = {3, 9, 6, 4, 1, 5, 7, 2, 10, 8, 87, 95, 456, 127, 54, 784, 65, 313, 75}; #define ARRAY_LENTH(array) (sizeof ((array)) / sizeof(int)) myInsertionSort(a, ARRAY_LENTH(a)); int i; for(i = 0; i < ARRAY_LENTH(a); i++) printf("%d, ", a[i]); return 0; } Jul 25 '08 #1 