COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### an implementation of insertion sort, insert without move element

• Email
• Follow

```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;
}
```
 0

See related articles to this posting

```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
```
 0
Reply pfiland (6614) 7/26/2008 9:32:04 PM

```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
```
 0
Reply pfiland (6614) 7/26/2008 10:24:55 PM

```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
```
 0
Reply pfiland (6614) 7/26/2008 10:43:17 PM

```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
```
 0
Reply pfiland (6614) 7/26/2008 10:47:56 PM

```"pete" <pfiland@mindspring.com> wrote in message
[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 **
```
 0
Reply dcorbit (2698) 7/28/2008 8:28:36 PM

5 Replies
36 Views

Similar Articles

12/21/2013 2:16:37 PM
[PageSpeed]

Similar Artilces:

Insertion Sort : C++ implementation 100 times slower than C implementation
Hello everyone, I implemented the insertion sort algorithm in C and C++ and tried comparing the performance. Here are the implementations 1. C++ # include<iostream> # include<vector> # include<iterator> # include<algorithm> # include<cstdlib> #include <boost/progress.hpp> using namespace std; typedef std::vector<int> t1; void insertionsort(t1& vin) { t1::iterator it1; t1::iterator it2; t1::iterator begin = vin.begin(); t1::iterator end = vin.end(); for(it1 = begin + 1; it1 != end; it1++) { int key = *it1; it2 = it1 - 1; while(*it2...

DOM: Re-inserting an element without removing it first
I've wondered if it is right thing to do: element.parentNode.insertBefore(element, beforeElement); where 'beforeElement' is one of the 'element.parentNode.childNodes'? First, I've used: var parentElement = element.parentNode; parentElement.removeChild(element); parentElement.insertBefore(element, beforeElement); but then I've noticed it works without the remove statement, too. -- Stanimir Stanimir Stamenkov wrote: > I've wondered if it is right thing to do: > > element.parentNode.insertBefore(element, beforeElement); > > where 'be...

probability of where a random element goes when inserted into an already sorted list?
Here is a cute little problem that was posed to me... Suppose you have a sorted list of N integers. What is the expected position where a new element is found after the insertion? Looking at the problem from a stats point of view, assume a uniform distribution. ...

Inserting elements of array into nonlinear function without using for loop
I want to find a way to optimize this: for snrdb=0:10 snr=10^(snrdb/10); y(snrdb+1,:)=awgn(sqrt(snr)*(-1).^encbits,snrdb); end where encbits is an array of zeros and ones. Is there a way to do this without using the for loop? Arne Arne wrote: > > > I want to find a way to optimize this: > > for snrdb=0:10 > snr=10^(snrdb/10); > y(snrdb+1,:)=awgn(sqrt(snr)*(-1).^encbits,snrdb); > end > > where encbits is an array of zeros and ones. Is there a way to do > this without using the for loop? > > Arne I don't know about removing the 'for&#...

stl::map: return default value without inserting a new element?
When using STL's map container, if operator[] is used to access the value associated with a given key which wasn't inserted then a new key:value pair will be created and a reference to the value will be returned. This means that, although operator[] is a convenient way to add new key:value pairs to a map, it may end up needlessly adding useless key:value pairs into the map. In order to avoid wasting resources populating a map with useless key:value pairs, is there a clean, unencumbered way to get the value associated with a given key without being forced to insert new e...

insertion sort and string sorting
I have a structure with a numeric field and a pointer to char: typedef struct s { int numero; char *carattere; } strutt; I have created, then, an array of structure: strutt *arr; arr = (strutt *)malloc(32 * sizeof(strutt)); I can insert a new element as: arr[0].numero = 5; arr[0].carattere = "qwerty" When this dynamic array of structure will be full, it can be necessary to sort it. I need to sort it with insertion sort algorithm, this is how I have implemented: void insertion_sort(strutt *x, int length) { strutt key; int i,j=1,scambi=0; for(j=1;j<leng...

Insertion sort...
I'm continuing (see my post "Counting sort") to implement the sorting algorithms you can find in "The Art of Computer Programming", volume 3, by D. Knuth. I'm posting the implementation of the insertion family sort algorithms. I didn't implement: - binary insertion sort - binary insertion with two-way insertion sort - multiple list insertion sort Thanks for your comments, Alberto Santini (defun straight-insertion-sort (vec) "Straight insertion sort as TAOCP, vol. 3, page 80 It's a simplified insertion sort with the gaps between the elements equ...

Insertion Sort
http://softwareandfinance.com/CPP_Insertion_Sort.html #include <iostream> #include <string> int InsertionSort() { int max; std::cout << "\nProgram for Ascending order of Numeric Values using INSERTION SORT"; std::cout << "\n\nEnter the total number of elements: "; std::cin >> max; int *numarray = new int[max]; for(int i = 0; i < max; i++) { std::cout << "\nEnter [" << i + 1 << "] element: "; std::cin >> numarray[i]; } ...

insert elements li in other element div
if I have one div bar01; is possible when mouse is hover class level-1 insert (to see) sez1 and sez2 inner other div, example bar-02 ? <div class="bar01"> <ul class="horiz"> <li class="level-1"><a href="" >MENU1</a> <ul> <li><a href="">sez1</a></li> <li><a href="">sez2</a></li> </ul> </li> <li class="level-1"><a href="" >MENU2</a> </li> .... other menus ... MENU3 how ME...

Element Insertion question
I am trying to insert Javascript code with grease monkey so it would insert to a page a call to a parent frame function al() I tried (portion of the code): x.document.createElement('script'); x.setAttribute("language", "javascript"); x.setAttribute("type", "text/javascript"); x.innerHTML ="window.load = parent.al();"; document.getElementsByTagName('head')[0].appendChild(x); And (another try): document.getElementsByTagName('body')[0].setAttribute("onload", "javascript:parent.al();"); ...