Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #12677 > unrolled thread

direct insertion sort

Back to article view | Back to comp.lang.c

Contents

  direct insertion sort karen tonantzin <cortesaguilar.karen@gmail.com> - 2011-11-04 07:43 -0700
    Re: direct insertion sort "osmium" <r124c4u102@comcast.net> - 2011-11-04 10:14 -0500
    Re: direct insertion sort Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-11-04 10:59 -0700
      Re: direct insertion sort pete <pfiland@mindspring.com> - 2011-11-07 18:06 -0500
    Re: direct insertion sort Martin Ambuhl <mambuhl@earthlink.net> - 2011-11-04 15:42 -0400
    Re: direct insertion sort Keith Thompson <kst-u@mib.org> - 2011-11-04 14:52 -0700

#12677 — direct insertion sort

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

[toc] | [next] | [standalone]

#12681

"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

[toc] | [prev] | [next] | [standalone]

#12716

On Nov 4, 4:43 pm, karen tonantzin <cortesaguilar.ka...@gmail.com>
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])
    {
      printf("Bad\n");
      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

[toc] | [prev] | [next] | [standalone]

#12858

Malcolm McLean wrote:
 
> 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 *))

That's not exactly the same parameters as qsort.
It makes no sense for (base) 
to be a pointer to a const qualified type.


> {
>   /* 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().

To write a stable insertionsort in C 
as a function of the same type as qsort:
you don't need to use a cast,
you don't need to get the i'th element,
you don't need a temporary buffer,
you don't need to use a multiplication operator,
you don't need to copy,
you don't need to use malloc,
you don't need to use memcpy or memmove.
  


#include <stddef.h>

void 
insertionsort(void *base, size_t N, size_t size, 
              int (*compfunc)(const void *, const void *))
{
    unsigned char *cbase, *low, *high, *p1, *p2, swap;

    if (N-- > 1) {
        cbase = base;
        do {
            low = cbase;
            high = low + size;
            cbase = high;
            while (compfunc(low, high) > 0) {
                p1 = high;
                p2 = low;
                do {
                    swap = *p1;
                    *p1++ = *p2;
                    *p2++ = swap;
                } while (p2 != high);
                if (low == base) {
                    break;
                }
                high = low;
                low -= size;
            }
        } while (--N != 0);
    }
}

-- 
pete

[toc] | [prev] | [next] | [standalone]

#12718

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.

[toc] | [prev] | [next] | [standalone]

#12729

karen tonantzin <cortesaguilar.karen@gmail.com> 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) kst-u@mib.org  <http://www.ghoti.net/~kst>
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web