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 2 of 2 — ← Prev page 1 [2]

#9497

In article <j2f23m$4n4$1@news.albasani.net>, BGB  <cr88192@hotmail.com> wrote:
>
>interesting, I had thought all initializers had to be constant in C89, 
>oh well...

The subtle difference that you're half-remembering is that C89 required
aggregate initializers to be constant (resolvable at link-time).

int get_an_int(void);

void foo(void)
{
  int item0 = get_an_int(), item1 = get_an_int(); /* valid C89 and C99 */
  int item[] = { get_an_int(), get_an_int() }; /* valid C99 only */
}

-- 
Alan Curry

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

#9474

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.

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

#9479

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.site11.com/www

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

#9495

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

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

#9498

> On Tue, 16 Aug 2011 19:22:18 -0400, pete wrote:

>> arnuld wrote:
>>   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.

I wonder how it happens but I will use this :)


 
> 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;
>         }
>     }
> }

This was good. i don't understand why these techniques don't come to my 
mind:

 (1) to sort N elements you need to sort only N-1 elements 
 (2) i and i != idx replaced by i+1 and s[i] > s[idx] 


Is there some special kind of practice/study needed to think like that ? 
(I have just started Cormen et al. )







-- 
  arnuld
www.LispMachine.Wordpress.com

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

#9499

On 2011-08-17, arnuld <sunrise@invalid.address> wrote:
>
> This was good. i don't understand why these techniques don't come to my 
> mind:
>
>  (1) to sort N elements you need to sort only N-1 elements 
>  (2) i and i != idx replaced by i+1 and s[i] > s[idx] 
>
> Is there some special kind of practice/study needed to think like that ? 
> (I have just started Cormen et al. )

Knowing the basics of algebra and formal Boolean logic helps a great deal,
IMHO. But other than that, it's just experience and practice. Much like
learning a human language, actually. You can learn the basics in school
but the only way to speak it fluently is to use it for real.

Or, I suppose, you could be "Apsie" to whom this sort of thinking comes
naturally. At least, that's how things are for me. ;-)


-- 
"C provides a programmer with more than enough rope to hang himself.
C++ provides a firing squad, blindfold and last cigarette."
- seen in comp.lang.c

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

#9500

arnuld <sunrise@invalid.address> writes:
> > On Tue, 16 Aug 2011 19:22:18 -0400, pete wrote:
> 
> >> arnuld wrote:
> >>   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.
> 
> I wonder how it happens but I will use this :)

It's perhaps better to say that in order to sort N elements
you only need to place N-1 of them in the correct positions.
There's nowhere else for the N-th element to go apart from 
its correct position. However, you are actually still sorting 
all N items.

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]

#9509

arnuld wrote:
> 
> > On Tue, 16 Aug 2011 19:22:18 -0400, pete wrote:
> 
> >> arnuld wrote:
> >>   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.
> 
> I wonder how it happens but I will use this :)

If an array has two elements, 
and the first element has been sorted into place by swapping,
then that means that the whole array has been sorted; right?

Phil Carmody phrased it better than I did.

> This was good.
> i don't understand why these techniques don't come to my
> mind:
> 
>  (1) to sort N elements you need to sort only N-1 elements
>  (2) i and i != idx replaced by i+1 and s[i] > s[idx]
> 
> Is there some special kind of practice/study needed to think like that ?

Writing sorting functions in C,
has been one of my hobbies for more than a few years.

http://www.mindspring.com/~pfilandr/C/q_sort/

http://www.mindspring.com/~pfilandr/C/e_driver/

I've also read some of Volume 3, Sorting And Searching,
from The Art Of Computer Programming, by Knuth.

Knuth considers Selection Sort, 
as being a category of sorts
in which the array is sorted from one end, 
one element at a time.
Heapsort is one kind of selection sort.
The sort that we have been looking at here in this thread,
I would call "simple selection sort".

-- 
pete

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web