an implementation of insertion sort, insert without move element

[Gestorm]

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$B!)(BI 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;
}

[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$B!)(BI 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

[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$B!)(BI 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