direct insertion sort

Discussion in 'C Programming' started by karen tonantzin, Nov 4, 2011.

  1. i need to know the funcion for this algoritm. I need to do a program
    with it. please somebody help me.
     
    karen tonantzin, Nov 4, 2011
    #1
    1. Advertising

  2. karen tonantzin

    osmium Guest

    "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
     
    osmium, Nov 4, 2011
    #2
    1. Advertising

  3. On Nov 4, 4:43 pm, karen tonantzin <>
    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 = rand() % 100;
    array2 = array1;
    }

    qsort(array1, 100, sizeof(int), compfunc);
    insertionsort(array2, 100, sizeof(int), compfunc);
    for(i=0;i<100;i++)
    {
    printf("% 2d, % 2d\n", array1, array2);
    }
    for(i=0;i<100;i++)
    if(array1 != array2)
    {
    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
     
    Malcolm McLean, Nov 4, 2011
    #3
  4. 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.
     
    Martin Ambuhl, Nov 4, 2011
    #4
  5. karen tonantzin <> 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.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Nov 4, 2011
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim923

    insertion sort java code

    Tim923, Apr 12, 2005, in forum: Java
    Replies:
    11
    Views:
    12,177
    bugbear
    Apr 13, 2005
  2. N.
    Replies:
    3
    Views:
    8,798
    charles8784
    Sep 22, 2007
  3. Jochus
    Replies:
    3
    Views:
    532
    Jochus
    Apr 21, 2005
  4. Java Newbie

    Insertion Sort on a linked list

    Java Newbie, Feb 4, 2007, in forum: Java
    Replies:
    2
    Views:
    3,442
    Mark Space
    Feb 9, 2007
  5. Navin
    Replies:
    1
    Views:
    762
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page