Re: selection-sort in C

Path	csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail
NNTP-Posting-Date	Tue, 16 Aug 2011 18:22:18 -0500
Message-ID	<4E4AFBAA.6AD2@mindspring.com> (permalink)
Date	Tue, 16 Aug 2011 19:22:18 -0400
From	pete <pfiland@mindspring.com>
Reply-To	pfiland@mindspring.com
Organization	PF
X-Mailer	Mozilla 3.04Gold (WinNT; I)
MIME-Version	1.0
Newsgroups	comp.lang.c
Subject	Re: selection-sort in C
References	<4e4a4fc9$0$313$14726298@news.sunsite.dk>
Content-Type	text/plain; charset=us-ascii
Content-Transfer-Encoding	7bit
Lines	57
X-Usenet-Provider	http://www.giganews.com
NNTP-Posting-Host	4.154.216.115
X-Trace	sv3-ZmtFFoXhPJB/yzgeByLyELXCu3LIwYVSqKVrIjlNzlJJv0OA8A26n+Rg/JUn45JxHdWlU+Fpxm7z5eb!mbNh1vEDaZVotZtyrRil5HV9PvlY+SHNjXvYq95VO7TXNx44F8sGctA0VvmZsz4zw9+yluju+j1y!OqFtWvw1s9E=
X-Abuse-and-DMCA-Info	Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info	Otherwise we will be unable to process your complaint properly
X-Postfilter	1.3.40
X-Original-Bytes	2102
Xref	x330-a1.tempe.blueboxinc.net comp.lang.c:9495

Show key headers only | View raw

arnuld wrote:
 
> void selectionSort(char s[], int len)
> {
>   int i, idx;
>   char tmp;
>   for(i = 0; i != len; ++i)

That loop is too long.

To sort an array of (N) elements,
you only have to sort the first (N - 1) elements.

void selectionSort(char s[], int len)
{
    int i, idx;
    char tmp;
    
    for(i = 0; i != len - 1; ++i) {
        idx = findSmallest(s, i, len);
        tmp = s[i];
        s[i] = s[idx];
        s[idx] = tmp;
    }
}

>     {
>       idx = findSmallest(s, i, len);

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

For an array of (N) elements
you could decrease the number of swaps to less than (N),
and you could also lighten the load 
on the findSmallest() function.

void selectionSort(char s[], int len)
{
    int i, idx;
    char tmp;
    
    for(i = 0; i != len - 1; ++i) {
        idx = findSmallest(s, i + 1, len);
        if (s[i] > s[idx]) {
            tmp = s[i];
            s[i] = s[idx];
            s[idx] = tmp;
        }
    }
}

-- 
pete

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