Velocity Reviews > direct insertion sort

# direct insertion sort

karen tonantzin
Guest
Posts: n/a

 11-04-2011
i need to know the funcion for this algoritm. I need to do a program
with it. please somebody help me.

osmium
Guest
Posts: n/a

 11-04-2011
"karen tonantzin" write:

>i need to know the funcion for this algoritm. I need to do a program
> with it. please somebody help me.

Wikipedia is often helpful on questions such as this. Try giving this to
Google and looking at the first few responses, very likely the first one. .

"insertion sort" wiki

Malcolm McLean
Guest
Posts: n/a

 11-04-2011
On Nov 4, 4:43*pm, karen tonantzin <(E-Mail Removed)>
wrote:
> i need to know the funcion for this algoritm. I need to do a program
> with it. please somebody help me.
>

Start the code like this

int main(void)
{
int array1[100];
int array2[100];
int i;

?* set upa rray1 and array2 identically */
for(i=0;i<100;i++)
{
array1[i] = rand() % 100;
array2[i] = array1[i];
}

qsort(array1, 100, sizeof(int), compfunc);
insertionsort(array2, 100, sizeof(int), compfunc);
for(i=0;i<100;i++)
{
printf("% 2d, % 2d\n", array1[i], array2[i]);
}
for(i=0;i<100;i++)
if(array1[i] != array2[i])
{
exit(EXIT_FAILURE);
}
printf("Function seems to work\n");
return 0;
}

Now you've got a test bed.

Compfunc is easy to write

int compfunc(const void *e1, const void *e2)
{
const int *iptr1 = e1;
const int *iptr2 = e2;

if(*iptr1 > *iptr2)
return 1;
if(*iptr1 == *iptr2)
return 0;
if(*iptr` < *iptr2)
return -1;
}

If you make some sort of mistake here, it will be caught because qsort
won't sort the data correctly.

Now we write insertionsort. Give it exactly the same parameters as
qsort

void insertionsort(const void *base, size_t N, size_t size, int
(*compfunc)(const void *, const void *))
{
/* code goes here */
}

The first thing you will need to do is to cast base to an unsigned
char *, call it cbase. That's just a little quirk of C, you can't
manipulate a void *. To get the i'th element, write cbase + i * size.
To copy, call memcpy (you'll need a temporary buffer for a temporary
element, call malloc(size) to create it). To compare two elements, i
and j, call (*compfunc)(cbase + i * size, cbase + j * size). To shift
a large number of elements, call memmove().

I can't provide the actual code, however. That's your job. However if
you post an attempt someone will be sure to help you with it.
--
Basic Algorithms (alas, does not include insertion sort)
http://www.malcolmmclean.site11.com/www

Martin Ambuhl
Guest
Posts: n/a

 11-04-2011
On 11/4/2011 10:43 AM, karen tonantzin wrote:
> i need to know the funcion for this algoritm. I need to do a program
> with it. please somebody help me.

There is no standard library function for "direct insertion sort" (next
time place your question in the body of your message). You need to
write it yourself. No doubt that is what your teacher intended.

Keith Thompson
Guest
Posts: n/a

 11-04-2011
karen tonantzin <(E-Mail Removed)> writes:
> i need to know the funcion for this algoritm. I need to do a program
> with it. please somebody help me.

Please give us your instructor's e-mail address so we can submit our
solutions directly.

Or consider doing your own homework. We're willing to help, but only if
you show some effort.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"