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

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

selection-sort in C

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

Contents

  selection-sort in C arnuld <sunrise@invalid.address> - 2011-08-16 11:08 +0000
    Re: selection-sort in C Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-08-16 14:24 +0300
      Re: selection-sort in C arnuld <sunrise@invalid.address> - 2011-08-16 11:36 +0000
        Re: selection-sort in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-16 13:22 +0100
          Re: selection-sort in C arnuld <sunrise@invalid.address> - 2011-08-16 13:44 +0000
            Re: selection-sort in C Anand Hariharan <mailto.anand.hariharan@gmail.com> - 2011-08-16 07:36 -0700
          Re: selection-sort in C Thomas Boell <tboell@domain.invalid> - 2011-08-16 18:03 +0200
            Re: selection-sort in C karnath <karnathtorjian@gmail.com> - 2011-08-16 16:25 +0000
              Re: selection-sort in C Willem <willem@toad.stack.nl> - 2011-08-16 16:33 +0000
            Re: selection-sort in C Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-08-16 20:03 +0100
          Re: selection-sort in C Keith Thompson <kst-u@mib.org> - 2011-08-16 09:27 -0700
        Re: selection-sort in C Jorgen Grahn <grahn+nntp@snipabacken.se> - 2011-08-17 20:17 +0000
          Re: selection-sort in C pete <pfiland@mindspring.com> - 2011-08-18 00:41 -0400
            Re: selection-sort in C Ben Pfaff <blp@cs.stanford.edu> - 2011-08-17 21:52 -0700
              Re: selection-sort in C pete <pfiland@mindspring.com> - 2011-08-18 01:07 -0400
                Re: selection-sort in C blp@cs.stanford.edu (Ben Pfaff) - 2011-08-17 22:36 -0700
                  Re: selection-sort in C pete <pfiland@mindspring.com> - 2011-08-18 07:00 -0400
      Re: selection-sort in C BGB <cr88192@hotmail.com> - 2011-08-16 14:41 -0700
        Re: selection-sort in C Ian Collins <ian-news@hotmail.com> - 2011-08-17 10:10 +1200
          Re: selection-sort in C BGB <cr88192@hotmail.com> - 2011-08-16 17:25 -0700
            Re: selection-sort in C pacman@kosh.dhis.org (Alan Curry) - 2011-08-17 01:53 +0000
    Re: selection-sort in C Gene <gene.ressler@gmail.com> - 2011-08-16 05:27 -0700
    Re: selection-sort in C Malcolm McLean <malcolm.mclean5@btinternet.com> - 2011-08-16 07:24 -0700
    Re: selection-sort in C pete <pfiland@mindspring.com> - 2011-08-16 19:22 -0400
      Re: selection-sort in C arnuld <sunrise@invalid.address> - 2011-08-17 07:52 +0000
        Re: selection-sort in C Angel <angel+news@spamcop.net> - 2011-08-17 10:15 +0000
        Re: selection-sort in C Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2011-08-17 13:22 +0300
        Re: selection-sort in C pete <pfiland@mindspring.com> - 2011-08-18 00:33 -0400

Page 1 of 2  [1] 2  Next page →

#9465 — selection-sort in C

Just wrote selection-sort in C. Is it the right way to do this in C ?

(definition of selection-sort taken from exercise 2.2-2 of Introduction 
to Algorithms, 2e)


/* Exercise 2.2-2, page 29, Selection Sort */

#include <stdio.h>

enum { SIZE_ARR = 6 };

void selectionSort(char s[], int len);
int findSmallest(char s[], const int idx_cur, const int len);


int main(void)
{
  char arr[SIZE_ARR+1] = {'a', 'r', 'n', 'u', 'l', 'd'};
  
  printf("%s\n", arr);
  selectionSort(arr, SIZE_ARR); 
  printf("%s\n", arr);

  return 0;
}


void selectionSort(char s[], int len)
{
  int i, idx;
  char tmp;
  for(i = 0; i != len; ++i)
    {
      idx = findSmallest(s, i, len);
      /*      printf("i = %d, Smallest Index = %d, s[%d] = %c\n", i, idx, 
idx, s[idx]); */
      tmp = s[i];
      s[i] = s[idx];
      s[idx] = tmp;
    }
}


int findSmallest(char s[], const int idx_cur, const int len)
{
  int j, ret_index;
  char smallest = s[idx_cur];
  ret_index = idx_cur;

  for(j = idx_cur+1; j != len; ++j)
    {
      /*      printf("idx_cur = %d, j = %d\n", idx_cur, j); */
      if(smallest > s[j])
	{
	  smallest = s[j];
	  ret_index = j;
	}
    }

  return ret_index;
}

===================== OUTPUT =======================
[arnuld@dune Intro-to-Algos]$ gcc -ansi -pedantic -Wall -Wextra 2.2-2.c
[arnuld@dune Intro-to-Algos]$ ./a.out 
arnuld
adlnru
[arnuld@dune Intro-to-Algos]$


 
-- arnuld
www.LispMachine.Wordpress.com

[toc] | [next] | [standalone]

#9467

arnuld <sunrise@invalid.address> writes:

> Just wrote selection-sort in C. Is it the right way to do this in C ?
> 
> (definition of selection-sort taken from exercise 2.2-2 of Introduction 
> to Algorithms, 2e)
> 
> 
> /* Exercise 2.2-2, page 29, Selection Sort */
> 
> #include <stdio.h>
> 
> enum { SIZE_ARR = 6 };
> 
> void selectionSort(char s[], int len);
> int findSmallest(char s[], const int idx_cur, const int len);

The consts on those parameters don't do much, but aren't actually
wrong.

> 
> 
> int main(void)
> {
>   char arr[SIZE_ARR+1] = {'a', 'r', 'n', 'u', 'l', 'd'};
>   
>   printf("%s\n", arr);
>   selectionSort(arr, SIZE_ARR); 
>   printf("%s\n", arr);
> 
>   return 0;
> }
> 
> 
> void selectionSort(char s[], int len)
> {
>   int i, idx;
>   char tmp;

Schools of thought vary, but some prefer variables that are only
going to be used in a small scope to be declared within that scope.

>   for(i = 0; i != len; ++i)
>     {
>       idx = findSmallest(s, i, len);

so that could be 
        int idx = findSmallest(s, i, len);

>       /*      printf("i = %d, Smallest Index = %d, s[%d] = %c\n", i, idx, 
> idx, s[idx]); */
>       tmp = s[i];

and that could be 
        char tmp = s[i];

>       s[i] = s[idx];
>       s[idx] = tmp;

Note that the swap is only necessary if(i != idx).

>     }
> }
> 
> 
> int findSmallest(char s[], const int idx_cur, const int len)
> {
>   int j, ret_index;
>   char smallest = s[idx_cur];
>   ret_index = idx_cur;
> 
>   for(j = idx_cur+1; j != len; ++j)
>     {
>       /*      printf("idx_cur = %d, j = %d\n", idx_cur, j); */
>       if(smallest > s[j])

Again, it's a matter of taste, but some prefer the object
you're testing to be first in the comparison. And here you're
testing s[j]. So:

        if(s[j] < smallest)

> 	{
> 	  smallest = s[j];
> 	  ret_index = j;
> 	}
>     }
> 
>   return ret_index;
> }

The sort looks fine. You might want to write a simple test 
harness to test arbitrary inputs.

Phil
-- 
Humans will have advanced a long, long, way when religious
belief has a cozy little classification in the DSM.
-- David Melville (on r.a.s.f1)

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

#9470

> On Tue, 16 Aug 2011 14:24:45 +0300, Phil Carmody wrote:

>> arnuld <sunrise@invalid.address> writes:
>> void selectionSort(char s[], int len); int findSmallest(char s[], const
>> int idx_cur, const int len);
 
> The consts on those parameters don't do much, but aren't actually wrong.

Just to show that function is not supposed to change its arguments.

 
> and that could be
>         char tmp = s[i];

I like to keep things in as small scope as possible but then here it will 
initialize the variable on each looping. I thought assignment is less 
expensive than initialization.


 
>>       s[i] = s[idx];
>>       s[idx] = tmp;
> 
> Note that the swap is only necessary if(i != idx).


humm.. did not think about it

 
>>   for(j = idx_cur+1; j != len; ++j)
>>     {
>>       /*      printf("idx_cur = %d, j = %d\n", idx_cur, j); */
>>       if(smallest > s[j])
 
> Again, it's a matter of taste, but some prefer the object you're testing
> to be first in the comparison. And here you're testing s[j]. So:

I will add this advice to my own style (unless I am comparing with some 
enum constant)


 
-- arnuld
www.LispMachine.Wordpress.com

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

#9473

arnuld <sunrise@invalid.address> writes:

>> On Tue, 16 Aug 2011 14:24:45 +0300, Phil Carmody wrote:
>
>>> arnuld <sunrise@invalid.address> writes:
>>> void selectionSort(char s[], int len); int findSmallest(char s[], const
>>> int idx_cur, const int len);
>  
>> The consts on those parameters don't do much, but aren't actually wrong.
>
> Just to show that function is not supposed to change its arguments.

The terminology is wrong here.  No C function can change its
arguments -- arguments are the things you pass to a function.  Your
declarations tell the reader that the function does not change its
*parameters*.

>> and that could be
>>         char tmp = s[i];
>
> I like to keep things in as small scope as possible but then here it will 
> initialize the variable on each looping. I thought assignment is less 
> expensive than initialization.

Why do you think that?  I am genuinely interested.  I never thought
about it one way or the other so I wonder where the idea comes from.

With automatic variables of aggregate types, any initialisation implies
full initialisation of whole object.  I.e.

  char str[100] = "";

is more expensive than

  char str[100]; 
  str[0] = 0;

but that's because the two don't do the same thing.  It's not assignment
is any cheaper.

<snip>
-- 
Ben.

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

#9477

> On Tue, 16 Aug 2011 13:22:59 +0100, Ben Bacarisse wrote:

> The terminology is wrong here.  No C function can change its arguments
> -- arguments are the things you pass to a function.  Your declarations
> tell the reader that the function does not change its *parameters*.


Okay, today my confusion of parameter vs argument is cleared.


 
> Why do you think that?  I am genuinely interested.  I never thought
> about it one way or the other so I wonder where the idea comes from.

genuinely, I don't know but see down here. 

 
> With automatic variables of aggregate types, any initialisation implies
> full initialisation of whole object.  I.e.
> 
>   char str[100] = "";
> 
> is more expensive than
> 
>   char str[100];
>   str[0] = 0;
> 
> but that's because the two don't do the same thing.  It's not assignment
> is any cheaper.

Holy cow, on different occasions, I was told by few experienced 
programmers that 1st version is much, much more expensive than 2nd. And I 
think this is from where my initialization vs assignment idea came from.




-- 
  arnuld
www.LispMachine.Wordpress.com

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

#9480

On Aug 16, 8:44 am, arnuld <sunr...@invalid.address> wrote:
> > On Tue, 16 Aug 2011 13:22:59 +0100, Ben Bacarisse wrote:
(...)
> > With automatic variables of aggregate types, any initialisation implies
> > full initialisation of whole object.  I.e.
>
> >   char str[100] = "";
>
> > is more expensive than
>
> >   char str[100];
> >   str[0] = 0;
>
> > but that's because the two don't do the same thing.  It's not assignment
> > is any cheaper.
>
> Holy cow, on different occasions, I was told by few experienced
> programmers that 1st version is much, much more expensive than 2nd. And I
> think this is from where my initialization vs assignment idea came from.
>

Like Ben indicated, the two statements do different things, so you
cannot compare them and make conclusions regarding which is "cheaper".

In the sibling language C++, the distinction between assignment and
initialisation is much more important than it is in C, and assignment
is typically more expensive than initialisation.

Regardless of any performance issues, giving variables a value at
definition (i.e., initialisation) is a good habit to develop.  Which
is why Phil's advice of declaring your variables in the tightest scope
possible also makes sense because you will define them only just
before you need them (and thereby give them a 'good' starting value).

- Anand

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

#9482

On Tue, 16 Aug 2011 13:22:59 +0100
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:

> arnuld <sunrise@invalid.address> writes:
> 
> >[...]
> >
> > I like to keep things in as small scope as possible but then here it will 
> > initialize the variable on each looping. I thought assignment is less 
> > expensive than initialization.
> 
> Why do you think that?  I am genuinely interested.  I never thought
> about it one way or the other so I wonder where the idea comes from.

If the compiler would do the allocation (i. e. reserving space on the
stack) exactly where it's requested, it would be more expensive to
declare the variable inside the loop. But I doubt that any optimizing
compiler would do that in this case; the allocation would be moved
outside the loop, or possibly the variable is allocated in a free
register, so allocating the variable inside the loop isn't any more
expensive than outside.

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

#9483

On 2011-08-16, Thomas Boell <tboell@domain.invalid> wrote:
> On Tue, 16 Aug 2011 13:22:59 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>> arnuld <sunrise@invalid.address> writes:
>> 
>> >[...]
>> >
>> > I like to keep things in as small scope as possible but then here it will 
>> > initialize the variable on each looping. I thought assignment is less 
>> > expensive than initialization.
>> 
>> Why do you think that?  I am genuinely interested.  I never thought
>> about it one way or the other so I wonder where the idea comes from.
>
> If the compiler would do the allocation (i. e. reserving space on the
> stack) exactly where it's requested, it would be more expensive to
> declare the variable inside the loop. But I doubt that any optimizing
> compiler would do that in this case; the allocation would be moved
> outside the loop, or possibly the variable is allocated in a free
> register, so allocating the variable inside the loop isn't any more
> expensive than outside.
>

Asking for clearance.

If we are using compiler without optimization it would be right to
put initialization before scope in topic case, won't it?

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

#9485

karnath wrote:
) On 2011-08-16, Thomas Boell <tboell@domain.invalid> wrote:
)> If the compiler would do the allocation (i. e. reserving space on the
)> stack) exactly where it's requested, it would be more expensive to
)> declare the variable inside the loop. But I doubt that any optimizing
)> compiler would do that in this case; the allocation would be moved
)> outside the loop, or possibly the variable is allocated in a free
)> register, so allocating the variable inside the loop isn't any more
)> expensive than outside.
)>
)
) Asking for clearance.
)
) If we are using compiler without optimization it would be right to
) put initialization before scope in topic case, won't it?

No.

If you are using compiler without optimization you obviously don't care
about performance, so it would not be right.  You should write code in
the most clear way, and keeping declarations close to usage is clearer
according to most opinions.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

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

#9488

Thomas Boell <tboell@domain.invalid> writes:

> On Tue, 16 Aug 2011 13:22:59 +0100
> Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
>
>> arnuld <sunrise@invalid.address> writes:
>> 
>> >[...]
>> >
>> > I like to keep things in as small scope as possible but then here it will 
>> > initialize the variable on each looping. I thought assignment is less 
>> > expensive than initialization.
>> 
>> Why do you think that?  I am genuinely interested.  I never thought
>> about it one way or the other so I wonder where the idea comes from.
>
> If the compiler would do the allocation (i. e. reserving space on the
> stack) exactly where it's requested, it would be more expensive to
> declare the variable inside the loop. But I doubt that any optimizing
> compiler would do that in this case; the allocation would be moved
> outside the loop, or possibly the variable is allocated in a free
> register, so allocating the variable inside the loop isn't any more
> expensive than outside.

That's relevant if you include allocation with initialisation.  I
assumed that arnuld meant exactly what he said.  To me that means he
thought that

  int x;
  x = 1;

is less expensive than

  int x = 1;

The allocation occurs in both cases.

-- 
Ben.

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

#9484

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> arnuld <sunrise@invalid.address> writes:
>>> On Tue, 16 Aug 2011 14:24:45 +0300, Phil Carmody wrote:
[...]
>>> The consts on those parameters don't do much, but aren't actually wrong.
>>
>> Just to show that function is not supposed to change its arguments.
>
> The terminology is wrong here.  No C function can change its
> arguments -- arguments are the things you pass to a function.  Your
> declarations tell the reader that the function does not change its
> *parameters*.

(I think the attribution levels got messed up a bit.)

Here's a program that illustrates the distiction:

#include <stdio.h>

void func_with_const(const int param)
{
    printf("In func_with_const, param = %d\n", param);
    /* param = 100; */ /* would be illegal */
    *(int*)&param = 200; /* undefined behavior! */
    printf("    Now param = %d\n", param);
}

void func_without_const(int param)
{
    printf("In func_with_const, param = %d\n", param);
    param = 300; /* perfectly legal */
    printf("    Now param = %d\n", param);
}

int main(void)
{
    int argument = 10;
    printf("In main, argument = %d\n", argument);
    func_with_const(argument);
    func_without_const(argument);
    printf("Back in main, argument is still %d\n", argument);
    return 0;
}

In func_with_const(), the "const" on the parameter declaration is a
promise not to modify the value of the parameter, which is a local
variable to the function.  It's relevant only within the body of the
function itself, and is of no interest to the caller.  In this case, the
fucntion uses a pointer cast to violate that promise, but even that
doesn't affect the argument.

func_without_const() doesn't promise not to modify its parameter, but
again, the modification has no effect on the caller.

You could have a *declaration* like
    void func1(int param);
and a *definition* like
    void func1(const int param) { ... param = ...; ... }
so the promise is made only where it's relevant, but it's questionable
whether that's worth the effort and potential confusion.

Note that "const" *can* meaningfully appear in a pointer parameter
declaration:

    void func2(const int *param);

Here the "const" applies to the object (if any) that the parameter
points to, not to the parameter itself.  A caller can pass func2() a
pointer to some data with the assurance that the pointed-to data won't
be modified.

You could make the parameter itself read-only like this:

    void func3(int *const param);

but, like the "const param" declaration, this isn't meaningful for the
caller.

-- 
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"

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

#9504

On Tue, 2011-08-16, arnuld wrote:
>> On Tue, 16 Aug 2011 14:24:45 +0300, Phil Carmody wrote:
>
>>> arnuld <sunrise@invalid.address> writes:
>>> void selectionSort(char s[], int len); int findSmallest(char s[], const
>>> int idx_cur, const int len);
>  
>> The consts on those parameters don't do much, but aren't actually wrong.
>
> Just to show that function is not supposed to change its arguments.

That makes sense in the /definition/ of the function, provided you
want them to be const just like you might want any local variable to
be const.

It does not make sense in the /declaration/.  The compiler will just
go "of course you can't change the argument, stupid -- C uses call by
value!"

/Jorgen

-- 
  // Jorgen Grahn <grahn@  Oo  o.   .     .
\X/     snipabacken.se>   O  o   .

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

#9510

Jorgen Grahn wrote:
> 
> On Tue, 2011-08-16, arnuld wrote:
> >> On Tue, 16 Aug 2011 14:24:45 +0300, Phil Carmody wrote:
> >
> >>> arnuld <sunrise@invalid.address> writes:

> >>> int findSmallest(char s[], const int idx_cur, const int len);
> >
> >> The consts on those parameters don't do much,
> >> but aren't actually wrong.
> >
> > Just to show that function is not supposed to change its arguments.
> 
> That makes sense in the /definition/ of the function, provided you
> want them to be const just like you might want any local variable to
> be const.
> 
> It does not make sense in the /declaration/.  The compiler will just
> go "of course you can't change the argument, stupid -- C uses call by
> value!"

Regardless of how arnuld phrased things,
the const qualifiers which are shown above, 
apply to the parameters.

Also, 
if the parameters are const qualified 
in the definition of a function, 
then they should also be const qualified in any prototype
of that function.

-- 
pete

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

#9511

pete <pfiland@mindspring.com> writes:

> Also, 
> if the parameters are const qualified 
> in the definition of a function, 
> then they should also be const qualified in any prototype
> of that function.

Are you are expressing a style preference here?  I do not think
that the C standard makes that requirement.

GCC 4.4 doesn't warn about the following translation unit, even
with -Wall -Wextra -ansi -pedantic:

    int f(int);
    int f(const int x) { return x; }

    int g(const int);
    int g(int x) { return x; }

-- 
Ben Pfaff 
http://benpfaff.org

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

#9512

Ben Pfaff wrote:
> 
> pete <pfiland@mindspring.com> writes:
> 
> > Also,
> > if the parameters are const qualified
> > in the definition of a function,
> > then they should also be const qualified in any prototype
> > of that function.
> 
> Are you are expressing a style preference here?  I do not think
> that the C standard makes that requirement.

That's what a prototype is.

ISO/IEC 9899:1999 (E)

6.2.1 Scopes of identifiers
2
(A function prototype is a declaration of a function
 that declares the types of its parameters.)

6.2.5 Types
25
The qualified or unqualified
versions of a type are distinct types

-- 
pete

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

#9513

pete <pfiland@mindspring.com> writes:

> Ben Pfaff wrote:
>> 
>> pete <pfiland@mindspring.com> writes:
>> 
>> > Also,
>> > if the parameters are const qualified
>> > in the definition of a function,
>> > then they should also be const qualified in any prototype
>> > of that function.
>> 
>> Are you are expressing a style preference here?  I do not think
>> that the C standard makes that requirement.
>
> That's what a prototype is.

I think that you have missed the following parenthetical in
6.7.5.3 "Function declarators (including prototypes)":

      (In the determination of type compatibility and of a
      composite type, each parameter declared with function or
      array type is taken as having the adjusted type and each
      parameter declared with qualified type is taken as having
      the unqualified version of its declared type.)
-- 
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}

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

#9522

Ben Pfaff wrote:
> 
> pete <pfiland@mindspring.com> writes:
> 
> > Ben Pfaff wrote:
> >>
> >> pete <pfiland@mindspring.com> writes:
> >>
> >> > Also,
> >> > if the parameters are const qualified
> >> > in the definition of a function,
> >> > then they should also be const qualified in any prototype
> >> > of that function.
> >>
> >> Are you are expressing a style preference here?  I do not think
> >> that the C standard makes that requirement.
> >
> > That's what a prototype is.
> 
> I think that you have missed the following parenthetical in
> 6.7.5.3 "Function declarators (including prototypes)":
> 
>       (In the determination of type compatibility and of a
>       composite type, each parameter declared with function or
>       array type is taken as having the adjusted type and each
>       parameter declared with qualified type is taken as having
>       the unqualified version of its declared type.)

Yes, I did miss that.

-- 
pete

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

#9493

On 8/16/2011 4:24 AM, Phil Carmody wrote:
> arnuld<sunrise@invalid.address>  writes:
>
>> Just wrote selection-sort in C. Is it the right way to do this in C ?
>>
>> (definition of selection-sort taken from exercise 2.2-2 of Introduction
>> to Algorithms, 2e)
>>
>>
>> /* Exercise 2.2-2, page 29, Selection Sort */
>>
>> #include<stdio.h>
>>
>> enum { SIZE_ARR = 6 };
>>
>> void selectionSort(char s[], int len);
>> int findSmallest(char s[], const int idx_cur, const int len);
>
> The consts on those parameters don't do much, but aren't actually
> wrong.
>

yep.


>>
>>
>> int main(void)
>> {
>>    char arr[SIZE_ARR+1] = {'a', 'r', 'n', 'u', 'l', 'd'};
>>
>>    printf("%s\n", arr);
>>    selectionSort(arr, SIZE_ARR);
>>    printf("%s\n", arr);
>>
>>    return 0;
>> }
>>
>>
>> void selectionSort(char s[], int len)
>> {
>>    int i, idx;
>>    char tmp;
>
> Schools of thought vary, but some prefer variables that are only
> going to be used in a small scope to be declared within that scope.
>
>>    for(i = 0; i != len; ++i)
>>      {
>>        idx = findSmallest(s, i, len);
>
> so that could be
>          int idx = findSmallest(s, i, len);
>

however, this will not work on compilers which don't support C99, where 
declarations have to be at the start of a block and can only be 
initialized to compile-time constants.

IMO, it is better to stick with C89/C90 conventions unless there is a 
good reason to do otherwise, since then one can build, say, on Windows 
while using a certain Microsoft compiler (much like how one avoids MSVC 
or GCC  specific extensions except when necessary, and typically guarded 
with #ifdef's).



>>        /*      printf("i = %d, Smallest Index = %d, s[%d] = %c\n", i, idx,
>> idx, s[idx]); */
>>        tmp = s[i];
>
> and that could be
>          char tmp = s[i];
>

same issue...


>>        s[i] = s[idx];
>>        s[idx] = tmp;
>
> Note that the swap is only necessary if(i != idx).
>

yep.


>>      }
>> }
>>
>>
>> int findSmallest(char s[], const int idx_cur, const int len)
>> {
>>    int j, ret_index;
>>    char smallest = s[idx_cur];
>>    ret_index = idx_cur;
>>
>>    for(j = idx_cur+1; j != len; ++j)
>>      {
>>        /*      printf("idx_cur = %d, j = %d\n", idx_cur, j); */
>>        if(smallest>  s[j])
>
> Again, it's a matter of taste, but some prefer the object
> you're testing to be first in the comparison. And here you're
> testing s[j]. So:
>
>          if(s[j]<  smallest)
>
>> 	{
>> 	  smallest = s[j];
>> 	  ret_index = j;
>> 	}
>>      }
>>
>>    return ret_index;
>> }
>
> The sort looks fine. You might want to write a simple test
> harness to test arbitrary inputs.
>

yep.

typically, if I were writing it I would have done it all inline, for 
example:
for(i=0; i<len; i++)
     for(j=i+1; j<len; j++)
         if(str[j]<str[i])
             { tmp=str[i]; str[i]=str[j]; str[j]=tmp; }

or maybe this:
stre=str+len;
for(s=str; s<stre; s++) for(t=s+1; t<stre; t++)
     if(*t<*s) { tmp=*s; *s=*t; *t=tmp; }

but, again, this is also a matter of personal preference...

granted, this would usually be because if I am resorting to selection 
sort, it means:
I want a fairly simple / easy-to-type sort;
I don't really care whether or not it performs all that well.


or such...

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

#9494

On 08/17/11 09:41 AM, BGB wrote:
> On 8/16/2011 4:24 AM, Phil Carmody wrote:
>> arnuld<sunrise@invalid.address>   writes:
>>>
>>> void selectionSort(char s[], int len)
>>> {
>>>     int i, idx;
>>>     char tmp;
>>
>> Schools of thought vary, but some prefer variables that are only
>> going to be used in a small scope to be declared within that scope.
>>
>>>     for(i = 0; i != len; ++i)
>>>       {
>>>         idx = findSmallest(s, i, len);
>>
>> so that could be
>>           int idx = findSmallest(s, i, len);
>>
>
> however, this will not work on compilers which don't support C99, where
> declarations have to be at the start of a block and can only be
> initialized to compile-time constants.

Not so, the above is perfectly legal old C.  You are confusing file 
scoped and function scoped variables, where the same rules apply to both 
old C and C99.

>>>         /*      printf("i = %d, Smallest Index = %d, s[%d] = %c\n", i, idx,
>>> idx, s[idx]); */
>>>         tmp = s[i];
>>
>> and that could be
>>           char tmp = s[i];
>>
>
> same issue...

Same non-issue!

-- 
Ian Collins

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

#9496

On 8/16/2011 3:10 PM, Ian Collins wrote:
> On 08/17/11 09:41 AM, BGB wrote:
>> On 8/16/2011 4:24 AM, Phil Carmody wrote:
>>> arnuld<sunrise@invalid.address> writes:
>>>>
>>>> void selectionSort(char s[], int len)
>>>> {
>>>> int i, idx;
>>>> char tmp;
>>>
>>> Schools of thought vary, but some prefer variables that are only
>>> going to be used in a small scope to be declared within that scope.
>>>
>>>> for(i = 0; i != len; ++i)
>>>> {
>>>> idx = findSmallest(s, i, len);
>>>
>>> so that could be
>>> int idx = findSmallest(s, i, len);
>>>
>>
>> however, this will not work on compilers which don't support C99, where
>> declarations have to be at the start of a block and can only be
>> initialized to compile-time constants.
>
> Not so, the above is perfectly legal old C. You are confusing file
> scoped and function scoped variables, where the same rules apply to both
> old C and C99.
>

interesting, I had thought all initializers had to be constant in C89, 
oh well...


>>>> /* printf("i = %d, Smallest Index = %d, s[%d] = %c\n", i, idx,
>>>> idx, s[idx]); */
>>>> tmp = s[i];
>>>
>>> and that could be
>>> char tmp = s[i];
>>>
>>
>> same issue...
>
> Same non-issue!
>

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web