an implementation of insertion sort, insert without move element

Suppose we have an array a[N], the idea is: build another array, int next[N], for each 0<i<N, next[i] = next position of a[i] in the sorted array, if a[i] is the max, then next[i] is undefined. For example, let the unsorted array is a[] = {5, 4, 2, 1, 3}; then next[] would be {undefined, 0, 4, 2, 1} after sorted. The process of sort is the process of building array next[]. Finally, build sorted a[] according to next[]. But at the last step, I cannot build a[] according to next[] directly, so I have to build another array tmp[N] to store the sorted sorted result, then copy it back to array a[], but I believe there is some way to do it. Does anyone who does well in algo analysis can help me to analyze my algo？I want to know if my algo is more efficient than the original one. And is there any way to build a[] directly at the last step? Thanks! The following is my code, we assume that the element type is int. #include<stdio.h> 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[0]; 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; }

Gestorm wrote: > Suppose we have an array a[N], the idea is: build another array, int > next[N], for each 0<i<N, next[i] = next position of a[i] in the sorted > array, if a[i] is the max, then next[i] is undefined. For example, let > the unsorted array is > a[] = {5, 4, 2, 1, 3}; > then > next[] > would be > {undefined, 0, 4, 2, 1} > after sorted. > The process of sort is the process of building array next[]. Finally, > build sorted a[] according to > next[]. But at the last step, I cannot build a[] according to next[] > directly, so I have to build another array tmp[N] to store the sorted > sorted result, then copy it back to array a[], but I believe there is > some way to do it. Does anyone who does well in algo analysis can > help me to analyze my algo？I want to know if my algo is more efficient > than the original one. And is there any way to build a[] directly at > the last step? Thanks! > The following is my code, we assume that the element type is int. > #include<stdio.h> > 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[0]; 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; > } There is a way to do what you want, but as far as I can guess, it's an O(N * N) operation, at which point I start to lose interest in working out the details. To do the equivalent of what your code does, using qsort, I would make a copy of the original array and then I would make an array of pointers to the copy array elements, and then sort the array of pointers, and then use that array to rewrite the original array. To do it with only (N + 1) element copy operations, you would need a temp buffer for a single array element. You would copy the original value of the first element to be overwritten to the buffer. You would then need to follow a list of source and destination elements, so that whichever element was the source in the last write operation, would become the destination for the next write operation. I think that working out that list, would be an O(N*N) operation. -- pete

Gestorm wrote: > Suppose we have an array a[N], the idea is: build another array, int > next[N], for each 0<i<N, next[i] = next position of a[i] in the sorted > array, if a[i] is the max, then next[i] is undefined. For example, let > the unsorted array is > a[] = {5, 4, 2, 1, 3}; > then > next[] > would be > {undefined, 0, 4, 2, 1} > after sorted. > The process of sort is the process of building array next[]. Finally, > build sorted a[] according to > next[]. But at the last step, I cannot build a[] according to next[] > directly, so I have to build another array tmp[N] to store the sorted > sorted result, then copy it back to array a[], but I believe there is > some way to do it. Does anyone who does well in algo analysis can > help me to analyze my algo？I want to know if my algo is more efficient > than the original one. And is there any way to build a[] directly at > the last step? Thanks! > The following is my code, we assume that the element type is int. > #include<stdio.h> > 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[0]; 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; > } Much better than a sort function definition where everything is type int, like this: void myInsertionSort(int a[], int size); is one in which the indexes and the element types are clearly distinct, and in which macros are used for operations between array elements, like this: #define E_TYPE int #define GT(A, B) (*(A) > *(B)) #define MOV(A, B) (*(A) = *(B)) typedef E_TYPE e_type; void myInsertionSort(e_type a[], size_t size); That makes it much easier to analyze the function algorithmically. I rewrote myInsertionSort that way. I found that it was better to declare (max) as a pointer rather than as an element type. I also added some error handling and made some small personal stylistic changes. /* BEGIN myInsertionSort.c */ #include <stdio.h> #include <stdlib.h> #define E_TYPE int #define GT(A, B) (*(A) > *(B)) #define MOV(A, B) (*(A) = *(B)) #define ARRAY_LENTH(array) (sizeof (array) / sizeof*(array)) typedef E_TYPE e_type; void myInsertionSort(e_type a[], size_t size) { e_type *max; e_type *tmp; size_t *next; size_t i,j; size_t first = 0; size_t last = 0; next = malloc(size * sizeof *next); tmp = malloc(size * sizeof *tmp); if (size != 0 && (next == NULL || tmp == NULL)) { free(next); free(tmp); puts("(next == NULL || tmp == NULL)"); exit(EXIT_FAILURE); } max = a; for (i = 1; size > i; ++i) { if (GT(max, a + i)) { if (GT(a + i, a + first)) { j = first; while (GT(a + i, a + next[j])) { j = next[j]; } next[i] = next[j]; next[j] = i; } else { next[i] = first; first = i; } } else { max = a + i; next[last] = i; last = i; } } j = first; for (i = 0; size != i; ++i) { MOV(tmp + i, a + j); j = next[j]; } for (i = 0; size != i; ++i) { MOV(a + i, tmp + i); } free(next); free(tmp); } int main(void) { size_t i; e_type a[] = { 3, 9, 6, 4, 1, 5, 7, 2, 10, 8, 87, 95, 456, 127, 54, 784, 65, 313, 75 }; myInsertionSort(a, ARRAY_LENTH(a)); for (i = 0; ARRAY_LENTH(a) != i; ++i) { printf("%d, ", a[i]); } putchar('\n'); return 0; } /* END myInsertionSort.c */ -- pete

pete wrote: > Gestorm wrote: >> void myInsertionSort(int a[], int size) >> { >> int *next, *tmp; > Much better than a sort function definition > where everything is type int, like this: > > void myInsertionSort(int a[], int size); > > is one in which the indexes and the element types > are clearly distinct, and in which macros are used > for operations between array elements, like this: > > #define E_TYPE int > #define GT(A, B) (*(A) > *(B)) > #define MOV(A, B) (*(A) = *(B)) > typedef E_TYPE e_type; > > void myInsertionSort(e_type a[], size_t size); > > That makes it much easier > to analyze the function algorithmically. > I rewrote myInsertionSort that way. > I found that it was better to declare (max) as a pointer > rather than as an element type. .... and that way, I was able to use your function to sort an array of pointers to strings, and I discovered that your "insertion sort", if that's what it really is, is not stable. /* BEGIN myInsertionSort2.c output */ Original order of strings: one two three four five six seven eight nine ten Nonstable sorting of strings by length, by myInsertionSort(): ten six one two nine five four three seven eight Stable sorting of strings by length, by sisort(): one two six ten four five nine three seven eight /* END myInsertionSort2.c output */ /* BEGIN myInsertionSort2.c */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define E_TYPE char * #define GT(A, B) (lencomp((A), (B)) > 0) #define MOV(A, B) (*(A) = *(B)) #define NMEMB(array) (sizeof (array) / sizeof*(array)) typedef E_TYPE e_type; int lencomp(const void *a, const void *b) { const size_t a_len = strlen(*(const char **)a); const size_t b_len = strlen(*(const char **)b); return b_len > a_len ? -1 : b_len != a_len; } void myInsertionSort(e_type a[], size_t size) { e_type *max; e_type *tmp; size_t *next; size_t i,j; size_t first = 0; size_t last = 0; next = malloc(size * sizeof *next); tmp = malloc(size * sizeof *tmp); if (size != 0 && (next == NULL || tmp == NULL)) { free(next); free(tmp); puts("(next == NULL || tmp == NULL)"); exit(EXIT_FAILURE); } max = a; for (i = 1; size > i; ++i) { if (GT(max, a + i)) { if (GT(a + i, a + first)) { j = first; while (GT(a + i, a + next[j])) { j = next[j]; } next[i] = next[j]; next[j] = i; } else { next[i] = first; first = i; } } else { max = a + i; next[last] = i; last = i; } } j = first; for (i = 0; size != i; ++i) { MOV(tmp + i, a + j); j = next[j]; } for (i = 0; size != i; ++i) { MOV(a + i, tmp + i); } free(next); free(tmp); } void sisort(e_type *array, size_t nmemb) { e_type temp, *base, *low, *high; if (nmemb-- > 1) { base = array; do { low = array++; if (GT(low, array)) { high = array; MOV(&temp, high); do { MOV(high, low); if (--high == base) { break; } --low; } while (GT(low, &temp)); MOV(high, &temp); } } while (--nmemb != 0); } } int main(void) { size_t i; e_type original[] = { "one", "two","three","four","five", "six","seven","eight","nine", "ten" }; e_type copy[NMEMB(original)]; puts("/* BEGIN myInsertionSort2.c output */\n"); puts("Original order of strings:"); for (i = 0; NMEMB(original) != i; ++i) { puts(original[i]); } puts("\nNonstable sorting of strings by length,\n" "by myInsertionSort():"); memcpy(copy, original, sizeof copy); myInsertionSort(copy, NMEMB(copy)); for (i = 0; NMEMB(copy) != i; ++i) { puts(copy[i]); } puts("\nStable sorting of strings by length,\n" "by sisort():"); memcpy(copy, original, sizeof copy); sisort(copy, NMEMB(copy)); for (i = 0; NMEMB(copy) != i; ++i) { puts(copy[i]); } puts("\n/* END myInsertionSort2.c output */"); return 0; } /* END myInsertionSort2.c */ -- pete

pete wrote: > Gestorm wrote: >> Suppose we have an array a[N], the idea is: build another array, int >> next[N], for each 0<i<N, next[i] = next position of a[i] in the sorted >> array, if a[i] is the max, then next[i] is undefined. For example, let >> the unsorted array is >> a[] = {5, 4, 2, 1, 3}; >> then >> next[] >> would be >> {undefined, 0, 4, 2, 1} >> after sorted. >> The process of sort is the process of building array next[]. Finally, >> build sorted a[] according to >> next[]. But at the last step, I cannot build a[] according to next[] >> directly, so I have to build another array tmp[N] to store the sorted >> sorted result, then copy it back to array a[], but I believe there is >> some way to do it. Does anyone who does well in algo analysis can >> help me to analyze my algo？I want to know if my algo is more efficient >> than the original one. And is there any way to build a[] directly at >> the last step? Thanks! >> The following is my code, we assume that the element type is int. >> #include<stdio.h> >> 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[0]; 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; >> } > To do the equivalent of what your code does, using qsort, > I would make a copy of the original array and then > I would make an array of pointers to the copy array elements, > and then sort the array of pointers, > and then use that array to rewrite the original array. I can code that much. At least that way, you have the advantage of being able to use qsort or another sorting alorithm which can be better that insertion sort. /* BEGIN pointersort.c */ #include <stdio.h> #include <stdlib.h> #define E_TYPE int #define GT(A, B) (*(A) > *(B)) #define MOV(A, B) (*(A) = *(B)) #define NMEMB(array) (sizeof (array) / sizeof*(array)) typedef E_TYPE e_type; void myInsertionSort(e_type a[], size_t size) { e_type *max; e_type *tmp; size_t *next; size_t i,j; size_t first = 0; size_t last = 0; next = malloc(size * sizeof *next); tmp = malloc(size * sizeof *tmp); if (size != 0 && (next == NULL || tmp == NULL)) { free(next); free(tmp); puts("(next == NULL || tmp == NULL)"); exit(EXIT_FAILURE); } max = a; for (i = 1; size > i; ++i) { if (GT(max, a + i)) { if (GT(a + i, a + first)) { j = first; while (GT(a + i, a + next[j])) { j = next[j]; } next[i] = next[j]; next[j] = i; } else { next[i] = first; first = i; } } else { max = a + i; next[last] = i; last = i; } } j = first; for (i = 0; size != i; ++i) { MOV(tmp + i, a + j); j = next[j]; } for (i = 0; size != i; ++i) { MOV(a + i, tmp + i); } free(next); free(tmp); } int int_cmp(const void *a, const void *b) { const int int_a = *(int *)a; const int int_b = *(int *)b; return int_b > int_a ? -1 : int_b != int_a; } int int_ptr_cmp(const void *a, const void *b) { const int int_a = **(int **)a; const int int_b = **(int **)b; return int_b > int_a ? -1 : int_b != int_a; } int main(void) { size_t i; e_type a[] = { 3, 9, 6, 4, 1, 5, 7, 2, 10, 8, 87, 95, 456, 127, 54, 784, 65, 313, 75 }; e_type copy[NMEMB(a)]; e_type *ptr[NMEMB(a)]; puts("/* BEGIN pointersort.c output */\n"); puts("Original order of array:"); for (i = 0; NMEMB(a) != i; ++i) { printf("%d, ", a[i]); } puts("\n\nSorted by myInsertionSort:"); for (i = 0; NMEMB(copy) != i; ++i) { copy[i] = a[i]; } myInsertionSort(copy, NMEMB(copy)); for (i = 0; NMEMB(copy) != i; ++i) { printf("%d, ", copy[i]); } puts("\n\nSorted by qsort:"); qsort(copy, NMEMB(copy), sizeof *copy, int_cmp); for (i = 0; NMEMB(copy) != i; ++i) { printf("%d, ", copy[i]); } puts("\n\nPointer array sorted by qsort:"); for (i = 0; NMEMB(copy) != i; ++i) { copy[i] = a[i]; } for (i = 0; NMEMB(a) != i; ++i) { ptr[i] = a + i; } qsort(ptr, NMEMB(ptr), sizeof *ptr, int_ptr_cmp); for (i = 0; NMEMB(copy) != i; ++i) { printf("%d, ", *ptr[i]); } puts("\n\nint array sorted by pointer array:"); for (i = 0; NMEMB(copy) != i; ++i) { copy[i] = *ptr[i]; } for (i = 0; NMEMB(copy) != i; ++i) { printf("%d, ", copy[i]); } puts("\n\n/* END pointersort.c output */"); return 0; } /* END pointersort.c */ -- pete

"pete" <pfiland@mindspring.com> wrote in message news:raidnVjEaJwDNBbVnZ2dnUVZ_jKdnZ2d@earthlink.com... [snip] > /* BEGIN pointersort.c */ > > #include <stdio.h> > #include <stdlib.h> > > #define E_TYPE int > #define GT(A, B) (*(A) > *(B)) > #define MOV(A, B) (*(A) = *(B)) > > #define NMEMB(array) (sizeof (array) / sizeof*(array)) > > typedef E_TYPE e_type; > > void myInsertionSort(e_type a[], size_t size) > { > e_type *max; > e_type *tmp; > size_t *next; > size_t i,j; > size_t first = 0; > size_t last = 0; > > next = malloc(size * sizeof *next); > tmp = malloc(size * sizeof *tmp); > if (size != 0 && (next == NULL || tmp == NULL)) { > free(next); > free(tmp); > puts("(next == NULL || tmp == NULL)"); > exit(EXIT_FAILURE); > } > max = a; > for (i = 1; size > i; ++i) { > if (GT(max, a + i)) { > if (GT(a + i, a + first)) { > j = first; > while (GT(a + i, a + next[j])) { > j = next[j]; > } > next[i] = next[j]; > next[j] = i; > } else { > next[i] = first; > first = i; > } > } else { > max = a + i; > next[last] = i; > last = i; > } > } > j = first; > for (i = 0; size != i; ++i) { > MOV(tmp + i, a + j); > j = next[j]; > } > for (i = 0; size != i; ++i) { > MOV(a + i, tmp + i); > } > free(next); > free(tmp); > } > > int int_cmp(const void *a, const void *b) > { > const int int_a = *(int *)a; > const int int_b = *(int *)b; > > return int_b > int_a ? -1 : int_b != int_a; > } > > int int_ptr_cmp(const void *a, const void *b) > { > const int int_a = **(int **)a; > const int int_b = **(int **)b; > > return int_b > int_a ? -1 : int_b != int_a; > } > > int main(void) > { > size_t i; > e_type a[] = { > 3, 9, 6, 4, 1, 5, > 7, 2, 10, 8, 87, 95, > 456, 127, 54, 784, 65, 313, 75 > }; > e_type copy[NMEMB(a)]; > e_type *ptr[NMEMB(a)]; > > puts("/* BEGIN pointersort.c output */\n"); > puts("Original order of array:"); > for (i = 0; NMEMB(a) != i; ++i) { > printf("%d, ", a[i]); > } > puts("\n\nSorted by myInsertionSort:"); > for (i = 0; NMEMB(copy) != i; ++i) { > copy[i] = a[i]; > } > myInsertionSort(copy, NMEMB(copy)); > for (i = 0; NMEMB(copy) != i; ++i) { > printf("%d, ", copy[i]); > } > puts("\n\nSorted by qsort:"); > qsort(copy, NMEMB(copy), sizeof *copy, int_cmp); > for (i = 0; NMEMB(copy) != i; ++i) { > printf("%d, ", copy[i]); > } > puts("\n\nPointer array sorted by qsort:"); > for (i = 0; NMEMB(copy) != i; ++i) { > copy[i] = a[i]; > } > for (i = 0; NMEMB(a) != i; ++i) { > ptr[i] = a + i; > } > qsort(ptr, NMEMB(ptr), sizeof *ptr, int_ptr_cmp); > for (i = 0; NMEMB(copy) != i; ++i) { > printf("%d, ", *ptr[i]); > } > puts("\n\nint array sorted by pointer array:"); > for (i = 0; NMEMB(copy) != i; ++i) { > copy[i] = *ptr[i]; > } > for (i = 0; NMEMB(copy) != i; ++i) { > printf("%d, ", copy[i]); > } > puts("\n\n/* END pointersort.c output */"); > return 0; > } > > /* END pointersort.c */ I make a wild guess that what he really wants is simply a version of insertion sort that operates on pointers to objects instead of objects. ** Posted from http://www.teranews.com **