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

Groups > comp.lang.c > #9493

Re: selection-sort in C

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web