insertion sort in C

Discussion in 'C Programming' started by arnuld, Sep 15, 2009.

  1. arnuld

    arnuld Guest

    It works fine. The Ullman's book does not have the check for (j > 0) in
    inner loop which I have put myself. Any advice for improvement ?

    One thing I don't get is how it is less expansive than bubble sort, we
    have 2 loops and we exchange values and we do it only once. The only
    difference is bubble starts for the bottom while insertion sort start
    from the top but numbers of iterations are same.



    /* A C program to learn insertion sort algorithm
    *
    * VERSION 0.0
    *
    */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    void sort_insertion(char* );

    int main(void)
    {
    char arrc[] = "kandr";

    printf("array(unsorted): %s\n", arrc);
    sort_insertion(arrc);
    printf("array(sorted): %s\n", arrc);


    return 0;
    }


    void sort_insertion(char c[])
    {
    size_t i,j;
    const size_t s = strlen(c);

    if( 0 == s )
    {
    printf("oops!, nothing to sort\n");
    return;
    }

    /* leave the first element for comparison, basis of insertion sort */
    for(i = 1; i != s; ++i)
    {
    for(j = i; (j > 0) && (c[j] < c[j - 1]); --j)
    {
    char temp = c[j];
    c[j] = c[j - 1];
    c[j - 1] = temp;

    }
    }
    }

    =================== OUTPUT ==================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra insertion-sort.c
    [arnuld@dune programs]$ ./a.out
    array(unsorted): kandr
    array(sorted): adknr
    [arnuld@dune programs]$



    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Sep 15, 2009
    #1
    1. Advertising

  2. arnuld

    user923005 Guest

    On Sep 15, 7:11 am, arnuld <> wrote:
    > It works fine. The Ullman's book does not have the check for (j > 0) in
    > inner loop which I have put myself. Any advice for improvement ?
    >
    > One thing I don't get is how it is less expansive than bubble sort, we
    > have 2 loops and we exchange values and we do it only once. The only
    > difference is bubble starts for the bottom while insertion sort start
    > from the top but numbers of iterations are same.

    Read this:
    http://www.cse.unr.edu/~bebis/CS477/Lect/InsertionSortBubbleSortSelectionSort.ppt
    [snip]
     
    user923005, Sep 15, 2009
    #2
    1. Advertising

  3. arnuld

    user923005 Guest

    On Sep 15, 7:11 am, arnuld <> wrote:
    > It works fine. The Ullman's book does not have the check for (j > 0) in
    > inner loop which I have put myself. Any advice for improvement ?
    >
    > One thing I don't get is how it is less expansive than bubble sort, we
    > have 2 loops and we exchange values and we do it only once. The only
    > difference is bubble starts for the bottom while insertion sort start
    > from the top but numbers of iterations are same.
    >
    > /* A C program to learn insertion sort algorithm
    >  *
    >  * VERSION 0.0
    >  *
    >  */
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    > void sort_insertion(char* );


    Suggestion code generically and use a typedef:

    void sort_insertion( e_type[], size_t n );

    >
    > int main(void)
    > {
    >   char arrc[] = "kandr";
    >
    >   printf("array(unsorted): %s\n", arrc);
    >   sort_insertion(arrc);
    >   printf("array(sorted):   %s\n", arrc);
    >
    >   return 0;
    >
    > }
    >
    > void sort_insertion(char c[])
    > {
    >   size_t i,j;
    >   const size_t s = strlen(c);
    >
    >   if( 0 == s )
    >     {
    >       printf("oops!, nothing to sort\n");


    This is a mistake. Sorting 0 or 1 items is not much work, but
    perfectly valid.

    >       return;
    >     }
    >
    >   /* leave the first element for comparison, basis of insertion sort */
    >   for(i = 1; i != s; ++i)
    >     {
    >       for(j = i; (j > 0) && (c[j] < c[j - 1]); --j)
    >         {
    >           char temp = c[j];
    >           c[j] = c[j - 1];
    >           c[j - 1] = temp;
    >
    >         }
    >     }
    >
    > }


    Perhaps something along these lines:

    #ifdef USE_INTEGER
    typedef int e_type;
    #define GT(a,b) (((a) > (b)) ? 1 : 0)
    #else
    /* Add your other types here... */
    #endif

    void linear_insertion(e_type a[], size_t n)
    {
    size_t i,
    j;
    e_type tmp;

    for (i = 1; i < n; i++)
    for (j = i; j > 0 && GT(a[j - 1], a[j]); j--) {
    tmp = a[j];
    a[j] = a[j - 1];
    a[j - 1] = tmp;
    }
    }

    > =================== OUTPUT ==================
    > [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra insertion-sort.c
    > [arnuld@dune programs]$ ./a.out
    > array(unsorted): kandr
    > array(sorted):   adknr
    > [arnuld@dune programs]$
    >
    > --www.lispmachine.wordpress.com
    > my email is @ the above blog.
     
    user923005, Sep 15, 2009
    #3
  4. arnuld

    Mark Guest

    arnuld wrote:
    > It works fine. The Ullman's book does not have the check for (j > 0)
    > in inner loop which I have put myself. Any advice for improvement ?


    [OT] What is the book you are using? Could you provide its title and
    authors? [/OT]
    Thanks.

    --
    Mark
     
    Mark, Sep 16, 2009
    #4
  5. arnuld

    user923005 Guest

    On Sep 15, 5:38 pm, "Mark" <> wrote:
    > arnuld wrote:
    > > It works fine. The Ullman's book does not have the check for (j > 0)
    > > in inner loop which I have put myself. Any advice for improvement ?

    >
    > [OT] What is the book you are using? Could you provide its title and
    > authors? [/OT]


    "Data Structures and Algorithms"
    by Alfred V. Aho, J. D. Ullman, J. E. Hopcroft
    ISBN:9780201000238

    http://product.half.ebay.com/_W0QQprZ67453QQcpidZ83146
     
    user923005, Sep 16, 2009
    #5
  6. arnuld

    arnuld Guest

    > On Sep 16, 2:18 am, user923005 <> wrote:

    > ..SNIP..
    > #define GT(a,b) (((a) > (b)) ? 1 : 0)
    > ..SNIP...


    Why use a macro when a function with return type int can do the job ?
     
    arnuld, Sep 16, 2009
    #6
  7. arnuld

    arnuld Guest

    > On Sep 16, 2:18 am, user923005 <> wrote:

    > ..SNIP..
    > #define GT(a,b) (((a) > (b)) ? 1 : 0)
    > ..SNIP...


    Why use a macro when a function with return type int can do the job ?
     
    arnuld, Sep 16, 2009
    #7
  8. arnuld

    arnuld Guest

    > On Sep 16, 2:18 am, user923005 <> wrote:

    > ..SNIP..
    > #define GT(a,b) (((a) > (b)) ? 1 : 0)
    > ..SNIP...


    Why use a macro when a function with return type int can do the job ?
     
    arnuld, Sep 16, 2009
    #8
  9. arnuld

    James Kuyper Guest

    arnuld wrote:
    >> On Sep 16, 2:18�am, user923005 <> wrote:

    >
    >> ..SNIP..
    >> #define GT(a,b) (((a) > (b)) ? 1 : 0)
    >> ..SNIP...

    >
    > Why use a macro when a function with return type int can do the job ?


    Because the macro will work regardless of the types of a and b, so long
    as they are types for which the expression a>b is permitted.
     
    James Kuyper, Sep 16, 2009
    #9
  10. arnuld <> writes:
    >> On Sep 16, 2:18 am, user923005 <> wrote:

    >
    >> ..SNIP..
    >> #define GT(a,b) (((a) > (b)) ? 1 : 0)
    >> ..SNIP...

    >
    > Why use a macro when a function with return type int can do the job ?


    Valid reasons have been presented for using a macro.

    But why use the ?: operator? The above could be written as:

    #define GT(a, b) ((a) > (b))

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    Nokia
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Sep 16, 2009
    #10
  11. arnuld

    user923005 Guest

    On Sep 16, 3:50 am, arnuld <> wrote:
    > > On Sep 16, 2:18 am, user923005 <> wrote:
    > > ..SNIP..
    > > #define GT(a,b) (((a) > (b)) ? 1 : 0)
    > > ..SNIP...

    >
    > Why use a macro when a function with return type int can do the job ?


    Actually, when I write data structures and algorithms, I almost always
    use C++ and would use a template.

    I actually despise function macros and just typed in something off the
    top of my head.

    A function call would be better (and the remarks about the simple
    comparison being superior to the ? operator are also correct.)
     
    user923005, Sep 16, 2009
    #11
  12. arnuld

    arnuld Guest

    > On Wed, 16 Sep 2009 10:50:40 +0000, Richard Heathfield wrote:

    > ...SNIP..


    > Personally, I prefer to use functions for comparisons (when it makes
    > sense). But advocates of the macro are likely to point out that the same
    > macro does the trick for any numerical types - float, double, long
    > double, char, short, int, long, long long, very long, and extremely
    > long.



    And I heard that this feature is the cause of lots of bugs but the
    primary reason I heard is "macros cheat the compiler"


    > Try this program:
    >
    > #include <stdio.h>
    >
    > #define GTF(a, b) int gt_ ## a ## _ ## b(a x, b y) { return x > y; }
    >
    > GTF(double, double)
    > GTF(int, unsigned)
    >
    > int main(void)
    > {
    > printf("%d\n", gt_double_double(42.1, 6.1)); printf("%d\n",
    > gt_int_unsigned(17, 112U)); return 0;
    > }


    First thing that came to my mind when I saw that code is "comparison
    between signed and unsigned (I have little experience with gcc now :)


    #include <stdio.h>

    #define GTF(a, b) int gt_ ## a ## _ ## b(a x, b y) { return x > y; }

    GTF(double, double)
    GTF(int, unsigned)


    int main(void)
    {
    printf("%d\n", gt_double_double(42.1, 6.1));
    printf("%d\n", gt_int_unsigned(17, 112U));
    return 0;
    }

    ==================== OUTPUT ============================
    [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra macro-trick.c
    macro-trick.c: In function ‘gt_int_unsigned’:
    macro-trick.c:6: warning: comparison between signed and unsigned
    [arnuld@dune programs]$ ./a.out
    1
    0
    [arnuld@dune programs]$


    A function does the same thing (except we need 2 functions for that) and
    they will not be evil: http://www.parashift.com/c -faq-lite/misc-
    technical-issues.html#faq-39.4





    --
    www.lispmachine.wordpress.com
    my email is @ the above blog.
     
    arnuld, Sep 17, 2009
    #12
  13. arnuld

    Norm Mann Guest

    "arnuld" <> wrote in message
    news:p...
    > It works fine. The Ullman's book does not have the check for (j > 0) in
    > inner loop which I have put myself. Any advice for improvement ?
    >
    > One thing I don't get is how it is less expansive than bubble sort, we
    > have 2 loops and we exchange values and we do it only once. The only
    > difference is bubble starts for the bottom while insertion sort start
    > from the top but numbers of iterations are same.


    I believe that your confusion is that you haven't really written an
    insertion sort routine, but a highly modified bubble sort. It can be
    improved by exiting the loop once the data swaps end.
    In essence, an insertion sort is comprised of two operations:
    1. finding the insertion point - in large arrays, a binary search is often
    used.
    2. moving the sorted data until the insertion point is open and moving the
    data to be inserted there.
    While operation 1. will result in less comparisons for larger arrays,
    operation 2. has 1/3 the number of data moves as the data swaps of a bubble
    sort (remember - a swap is 3 data moves).

    > /* A C program to learn insertion sort algorithm
    > *
    > * VERSION 0.0
    > *
    > */
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    > void sort_insertion(char* );
    >
    > int main(void)
    > {
    > char arrc[] = "kandr";
    >
    > printf("array(unsorted): %s\n", arrc);
    > sort_insertion(arrc);
    > printf("array(sorted): %s\n", arrc);
    >
    >
    > return 0;
    > }
    >
    >
    > void sort_insertion(char c[])
    > {
    > size_t i,j;
    > const size_t s = strlen(c);
    >
    > if( 0 == s )
    > {
    > printf("oops!, nothing to sort\n");
    > return;
    > }
    >
    > /* leave the first element for comparison, basis of insertion sort */
    > for(i = 1; i != s; ++i)
    > {
    > for(j = i; (j > 0) && (c[j] < c[j - 1]); --j)
    > {
    > char temp = c[j];
    > c[j] = c[j - 1];
    > c[j - 1] = temp;
    >
    > }
    > }
    > }
    >
    > =================== OUTPUT ==================
    > [arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra insertion-sort.c
    > [arnuld@dune programs]$ ./a.out
    > array(unsorted): kandr
    > array(sorted): adknr
    > [arnuld@dune programs]$
    >
    >
    >
    > --
    > www.lispmachine.wordpress.com
    > my email is @ the above blog.
    >
     
    Norm Mann, Sep 17, 2009
    #13
  14. arnuld

    Nobody Guest

    On Tue, 15 Sep 2009 14:11:09 +0000, arnuld wrote:

    > It works fine. The Ullman's book does not have the check for (j > 0) in
    > inner loop which I have put myself. Any advice for improvement ?
    >
    > One thing I don't get is how it is less expansive than bubble sort, we
    > have 2 loops and we exchange values and we do it only once. The only
    > difference is bubble starts for the bottom while insertion sort start
    > from the top but numbers of iterations are same.


    Bubble sort scans the entire array in the inner loop, while insertion sort
    only scans a portion of it. This results in bubble sort performing roughly
    twice as many comparisons.

    Bubble sort performs between 1 and N iterations of the outer loop, and N
    iterations of the inner loop, resulting in n^2 comparisons in the worst
    case.

    Insertion sort performs N-1 iterations of the outer loop, and between 1
    and i iterations (average = i/2) of the inner loop, where i is the
    iteration number of the outer loop, resulting in n*(n-1)/2 comparisons in
    the worst case.
     
    Nobody, Sep 17, 2009
    #14
  15. arnuld

    Tim Rentsch Guest

    Nobody <> writes:

    > On Tue, 15 Sep 2009 14:11:09 +0000, arnuld wrote:
    >
    >> It works fine. The Ullman's book does not have the check for (j > 0) in
    >> inner loop which I have put myself. Any advice for improvement ?
    >>
    >> One thing I don't get is how it is less expansive than bubble sort, we
    >> have 2 loops and we exchange values and we do it only once. The only
    >> difference is bubble starts for the bottom while insertion sort start
    >> from the top but numbers of iterations are same.

    >
    > Bubble sort scans the entire array in the inner loop, while insertion sort
    > only scans a portion of it. This results in bubble sort performing roughly
    > twice as many comparisons.
    >
    > Bubble sort performs between 1 and N iterations of the outer loop, and N
    > iterations of the inner loop, resulting in n^2 comparisons in the worst
    > case.


    The bubble sort that I'm used to performs N-k comparisons on pass k,
    with k going from 1 to N-1. That's N*(N-1)/2 comparisons in the worst
    case. Maybe you're using a suboptimal bubble sort?

    > Insertion sort performs N-1 iterations of the outer loop, and between 1
    > and i iterations (average = i/2) of the inner loop, where i is the
    > iteration number of the outer loop, resulting in n*(n-1)/2 comparisons in
    > the worst case.


    Actually insertion sort can do better -- using binary search to find
    insertion points, insertion sort can use O( n log n ) compares, and
    n*(n-1)/2 moves in the worst case. Besides needing fewer compares,
    insertion sort beats bubble sort because data movement in insertion
    sort is easier to optimize than it is in bubble sort.
     
    Tim Rentsch, Sep 30, 2009
    #15
    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,139
    bugbear
    Apr 13, 2005
  2. N.
    Replies:
    3
    Views:
    8,754
    charles8784
    Sep 22, 2007
  3. Jochus
    Replies:
    3
    Views:
    519
    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,393
    Mark Space
    Feb 9, 2007
  5. Navin
    Replies:
    1
    Views:
    729
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page