[lnkForumImage]
TotalShareware - Download Free Software

Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c

selection-sort in C

arnuld

8/16/2011 11:09:00 AM

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
27 Answers

Phil Carmody

8/16/2011 11:25:00 AM

0

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)

arnuld

8/16/2011 11:36:00 AM

0

> 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

Ben Bacarisse

8/16/2011 12:23:00 PM

0

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.

Gene

8/16/2011 12:28:00 PM

0

On Aug 16, 7:08 am, arnuld <sunr...@invalid.address> wrote:
> 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;
>
> }
,
The C style looks fine, but the most general answer to your question
must include the fact that if you are implementing an O(n^2) sort,
insertion sort will do no worse than the others, and it is
significantly better on many data.

arnuld

8/16/2011 1:45:00 PM

0

> 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

Malcolm McLean

8/16/2011 2:24:00 PM

0

On Aug 16, 2:08 pm, arnuld <sunr...@invalid.address> wrote:
> Just wrote selection-sort in C. Is it the right way to do this in C ?
>

Write a sort like this

void selection_sort(void *data, size_t N, size_t elsize, int (*comp)
(const void *e1, const void *e2));

Now you have several advantages. You can sort any data as long as it
fits in an array and you can write a comparator for it. Also, the
paramaters match qsort. So when testing your function, you can toggle
between selection_sort and qsort()

--
Get Basic Algorithms, full of C routines.
http://www.malcolmmclean.site...


Anand Hariharan

8/16/2011 2:36:00 PM

0

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

Thomas Boell

8/16/2011 4:04:00 PM

0

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.

karnath

8/16/2011 4:26:00 PM

0

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?

Keith Thompson

8/16/2011 4:28:00 PM

0

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.ne...
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"