Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   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)

arnuld 09-15-2009 02:11 PM

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


user923005 09-15-2009 06:45 PM

Re: insertion sort in C
 
On 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]


user923005 09-15-2009 09:18 PM

Re: insertion sort in C
 
On 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.



Mark 09-16-2009 12:38 AM

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


user923005 09-16-2009 03:40 AM

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


arnuld 09-16-2009 09:16 AM

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 ?

arnuld 09-16-2009 09:19 AM

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 ?

arnuld 09-16-2009 10:50 AM

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 ?

James Kuyper 09-16-2009 11:12 AM

Re: insertion sort in C
 
arnuld 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.

Keith Thompson 09-16-2009 03:27 PM

Re: insertion sort in C
 
arnuld <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.