- **C Programming**
(*http://www.velocityreviews.com/forums/f42-c-programming.html*)

- - **insertion sort in C**
(*http://www.velocityreviews.com/forums/t698349-insertion-sort-in-c.html*)

insertion sort in CIt 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. |

Re: insertion sort in COn Sep 15, 7:11*am, arnuld <sunr...@invalid.address> 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/...ectionSort.ppt [snip] |

Re: insertion sort in COn Sep 15, 7:11*am, arnuld <sunr...@invalid.address> 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. |

Re: insertion sort in Carnuld 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 |

Re: insertion sort in COn Sep 15, 5:38*pm, "Mark" <mark_cruzNOTFORS...@hotmail.com> 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 |

Re: insertion sort in C> On Sep 16, 2:18*am, user923005 <dcor...@connx.com> 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 ? |

Re: insertion sort in C> On Sep 16, 2:18*am, user923005 <dcor...@connx.com> 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 ? |

Re: insertion sort in C> On Sep 16, 2:18*am, user923005 <dcor...@connx.com> 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 ? |

Re: insertion sort in Carnuld wrote:
>> On Sep 16, 2:18ï¿½am, user923005 <dcor...@connx.com> 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. |

Re: insertion sort in Carnuld <arnuld.mizong@gmail.com> writes:
>> On Sep 16, 2:18Â*am, user923005 <dcor...@connx.com> 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) kst-u@mib.org <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" |

All times are GMT. The time now is 07:34 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.