Selection-Sort in C

[arnuld]

Here is the C implementation of Selection-Sort. Any advice for
improvement will be apppreciated:


/* A C program to sort an array of characters using bubble sort algorithm
*
* VERSION 0.0
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void sort_bubble(char* );

int main(void)
{
char arrc[] = "heathfield";

printf("array(unsorted): %s\n", arrc);
sort_bubble(arrc);
printf("array(sorted): %s\n", arrc);

return 0;
}


void sort_bubble(char* c)
{
size_t i, j;
size_t s = strlen(c);

for(i = 0; i < s; ++i)
{
for(j = s-1; j != i; --j)
{
if( c[j] < c[j-1] )
{
char temp = c[j];
c[j] = c[j - 1];
c[j - 1] = temp;
}
}
}
}

========================== OUTPUT ==============================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra selection-sort.c
[arnuld@dune programs]$ ./a.out
Original Array = arnuld
Sorted Array = adlnru
[arnuld@dune programs]$

 

[Edwin van den Oetelaar]

Here is the C implementation of Selection-Sort. Any advice for
improvement will be apppreciated:


/* A C program to sort an array of characters using bubble sort algorithm
*
* VERSION 0.0
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>


void sort_bubble(char* );

int main(void)
{
char arrc[] = "heathfield";

printf("array(unsorted): %s\n", arrc);
sort_bubble(arrc);
printf("array(sorted): %s\n", arrc);

return 0;
}

If this is your source how can it give this answer. Do you want bubble-sort or selection-sort ?

[arnuld@dune programs]$ ./a.out
Original Array = arnuld
Sorted Array = adlnru

this hurts my head.

 

[arnuld]

If this is your source how can it give this answer. Do you want
bubble-sort or selection-sort ?

I really don't have any idea. I just look at the given O(n) notation and
decide.

this hurts my head.

Why ?

 

[bartc]

I really don't have any idea. I just look at the given O(n) notation and
decide.

You posted code which you said was for selection sort, but which looked
remarkably like bubble sort, even to the extent of being called
"bubble-sort" in the code.

 

[Mark Bluemel]

[Reordered for clarity (sort of)]

Here is the C implementation of Selection-Sort. ....
/* A C program to sort an array of characters using bubble sort algorithm

bubble != selection

void sort_bubble(char* c)
{
size_t i, j;
size_t s = strlen(c);

for(i = 0; i < s; ++i)
{
for(j = s-1; j != i; --j)
{
if( c[j] < c[j-1] )
{
char temp = c[j];
c[j] = c[j - 1];
c[j - 1] = temp;
}
}
}

}

That looks like a bubble sort to me...

  char arrc[] = "heathfield";

  printf("array(unsorted): %s\n", arrc);
  sort_bubble(arrc);
  printf("array(sorted):  %s\n", arrc);

========================== OUTPUT ==============================

Original Array = arnuld
Sorted Array   = adlnru

How could the code you posted produce this output?

 

[Eric Sosman]

I really don't have any idea. I just look at the given O(n) notation and
decide.




Why ?

Maybe because bubble sort is the worst[*][**] sorting
algorithm known to Man?

[*] Not true, of course: Any algorithm can be disimproved,
and then the worse algorithm can be further disimproved, and
so on ad infinitum. But bubble sort is surely the worst "basic"
sort algorithm known.[***]

[**] Much depends on the model, of course. Knuth mentions
an idealized machine imagined by H.B. Demuth for which bubble
sort is in fact optimal. He also shows that given sufficient
parallelism of the right kind, bubble sort is equivalent to
straight insertion. But for C's abstract machine ... No: bubble
sort is The Worst.

[***] Yes, despite my own ferreting out of an O(N*N*logN)
sort in actual production code. The sort algorithm itself was
fine, O(N*logN), but the careless programmer had handed it an
O(N) comparison function ...

 

[arnuld]

You posted code which you said was for selection sort, but which looked
remarkably like bubble sort, even to the extent of being called
"bubble-sort" in the code.

My apologies, here is the actual code I wrote:


/* A C Implementation of Selection Sort.
* Section 8.2 of "Data Structures and Algorithms by Aho, Hopcraft and
Ullman"
*
* VERSION 0.0.
*
*/


#include <stdio.h>
#include <string.h>

void sort_selection(char [], const size_t);


int main(void)
{
char arrc[] = "arnuld";

const size_t arr_size = strlen(arrc);

printf("Original Array = %s\n", arrc);
sort_selection(arrc, arr_size);
printf("Sorted Array = %s\n", arrc);


return 0;
}


void sort_selection(char c[], const size_t sz)
{
size_t i, j;


if(0 == sz)
{
printf("Nothig to sort!\n");
return;
}
else if(1 == sz)
{
printf("There is no need to sort a single element\n");
return;
}

for(i = 0; i != sz; ++i)
{
for(j = i + 1; j != sz; ++j )
{
if(c[j] < c)
{
char temp = c;
c = c[j];
c[j] = temp;
}
}
}
}

 

[James Kuyper]

Eric Sosman wrote:
....

so on ad infinitum. But bubble sort is surely the worst "basic"
sort algorithm known.[***]

Bubble sort is generally immensely faster than bogosort. ;-} Unless
you're able to implement the quantum version of bogosort, which is the
fastest sorting method I've ever heard of.

 

[user923005]

On Tue, 29 Sep 2009 13:18:26 +0000, bartc wrote:
You posted code which you said was for selection sort, but which looked
remarkably like bubble sort, even to the extent of being called
"bubble-sort" in the code.

My apologies, here is the actual code I wrote:

/* A C Implementation of Selection Sort.
 * Section 8.2 of "Data Structures and Algorithms by Aho, Hopcraft and
Ullman"
 *
 * VERSION 0.0.
 *
 */

#include <stdio.h>
#include <string.h>

void sort_selection(char [], const size_t);

int main(void)
{
  char arrc[] = "arnuld";

  const size_t arr_size = strlen(arrc);

  printf("Original Array = %s\n", arrc);
  sort_selection(arrc, arr_size);
  printf("Sorted Array   = %s\n", arrc);

  return 0;

}

This sort interface is vary bad as the only thing it can sort is a
zero terminated character string:

void sort_selection(char c[], const size_t sz)
{
  size_t i, j;

  if(0 == sz)
    {

This is a bug -- there is nothing wrong with sorting zero items:

      printf("Nothig to sort!\n");
      return;
    }
  else if(1 == sz)
    {

This is a bug -- there is nothing wrong with sorting a single element:

      printf("There is no need to sort a single element\n");
      return;
    }

  for(i = 0; i != sz; ++i)
    {
      for(j = i + 1; j != sz; ++j )
        {

Since you are studying O(f(N)), why not count the comparisons?

          if(c[j] < c)
            {

Since you are studying O(f(N)), why not count the exchanges?

              char temp = c;
              c = c[j];
              c[j] = temp;
            }
        }
    }

}

If you called the qsort() library interface in your code and a
customer passed a list with a single item in it using your software,
and the library printed messages on the console complaining about the
item count, how would you like it?

It's not a bug to call a sort routine with zero or one items. It *is*
a bug to write messages to standard output complaining about it.

If you write software, general purpose routines such as sorting
interfaces should be generic if at all possible. Your interfaces are
designed to sort a single thing: a character string. Interfaces
designed to sort only a list of integers are just as bad (and you will
see that a lot in C books) but that does not mean that you should copy
their bad methodology.

Some kinds of things (sorting, searching, summation, averaging,
finding partitions, finding medians...) are generic operations that
will be useful on any kind of data. If you design your programs so
that any sort of list can be used, then your software will not have to
be rewritten every time you need to do something with it. So I
suggest that an attempt at being more generic would be valuable.

Now, if the only thing you care about with these routines is to
understand O(f(N)) behavior, then you won't need to fix it for that
purpose. But practice makes perfect only if we practice what is
perfect. If we practice bad ideas it will lead to bad habits.

IMO-YMMV

 

[Mark]

This sort interface is vary bad as the only thing it can sort is a
zero terminated character string:

If a string is not zero terminated, it probably would not be a string as C
understands it?

 

[Squeamizh]

This sort interface is vary bad as the only thing it can sort is a
zero terminated character string:
void sort_selection(char c[], const size_t sz)

The char array does not have to be null-terminated.

 

[user923005]

This sort interface is vary bad as the only thing it can sort is a
zero terminated character string:
void sort_selection(char c[], const size_t sz)

The char array does not have to be null-terminated.

It does with his driver:
const size_t arr_size = strlen(arrc);

 

[user923005]

Right. Still, a sort interface that can only sort a string isn't much
use to anyone.

However, if the only purpose is for O(f(N)) calculations, then it is
adequate, however.

 

[Tim Rentsch]

I really don't have any idea. I just look at the given O(n) notation
and decide.




Why ?

Maybe because bubble sort is the worst[*][**] sorting
algorithm known to Man?

Bubble sort has these advantages. It is easy to understand,
easy to program, easy to get right, and relies solely on
local operations. It is also stable.

Selection sort is easy to understand, and not too bad to
program, but it is not stable.

Insertion sort is stable and easy to understand, but
programming it takes just a little more care than
bubble sort. The natural desire to improve the
search for insertion points (by using binary search)
makes it more complicated.

Quick sort is easy to understand, at least conceptually,
but programming it takes a certain amount of care,
especially if an effort is made to minimize the chances
for N**2 behavior or use of linear stack space. It
also isn't stable.

Heap sort isn't easy to understand, isn't nearly so easy
to program, is easy to get wrong, and /always/ is doing
non-local operations; it also isn't stable. Heap sort
is a great sorting algorithm.

Merge sort is usually dismissed because of needing extra
space. Yes it's possible to do a stable merge sort on an
array and use only O(1) extra space, but programming that is
horrendous.

[***] Yes, despite my own ferreting out of an O(N*N*logN)
sort in actual production code. The sort algorithm itself was
fine, O(N*logN), but the careless programmer had handed it an
O(N) comparison function ...

Even that's not as bad as the O(N**3) sort algorithm used
many years ago in a certain operating system's "help"
command...

 

[Tim Rentsch]

Eric Sosman wrote:
...

so on ad infinitum. But bubble sort is surely the worst "basic"
sort algorithm known.[***]

Bubble sort is generally immensely faster than bogosort. ;-} Unless
you're able to implement the quantum version of bogosort, which is the
fastest sorting method I've ever heard of.

Even quantum-bogosort can't keep up with Intelligent Design Sort.

(IDS makes no changes to its input, on the theory that
"they are already sorted according to a higher purpose.")

 

[Keith Thompson]

Eric Sosman wrote:
...

so on ad infinitum. But bubble sort is surely the worst "basic"
sort algorithm known.[***]

Bubble sort is generally immensely faster than bogosort. ;-} Unless
you're able to implement the quantum version of bogosort, which is the
fastest sorting method I've ever heard of.

Even quantum-bogosort can't keep up with Intelligent Design Sort.

(IDS makes no changes to its input, on the theory that
"they are already sorted according to a higher purpose.")

Similar to Miracle sort.

Check whether the array is already sorted.
If it is, you're done.
If it's not, wait a while and check again, and hope for cosmic rays to
modify the array in memory.

 

[Tim Rentsch]

Eric Sosman wrote:
...
so on ad infinitum. But bubble sort is surely the worst "basic"
sort algorithm known.[***]

Bubble sort is generally immensely faster than bogosort. ;-} Unless
you're able to implement the quantum version of bogosort, which is the
fastest sorting method I've ever heard of.

Even quantum-bogosort can't keep up with Intelligent Design Sort.

(IDS makes no changes to its input, on the theory that
"they are already sorted according to a higher purpose.")

Similar to Miracle sort.

Check whether the array is already sorted.
If it is, you're done.
If it's not, wait a while and check again, and hope for cosmic rays to
modify the array in memory.

I like it! A sorting algorithm that's O(n),
if only you have faith...

 

[Keith Thompson]

Many years ago there was a crackpot posting here who claimed that
sorting was O(n). It turns out that if you think about it
properly, it is.

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().

 

[Eric Sosman]

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().

Sorting is O(1) no matter what you count, provided the
sort runs on a machine with finite resources and that it
terminates.

 

[Keith Thompson]

(e-mail address removed) (Richard Harter) writes:
[...]

Many years ago there was a crackpot posting here who claimed that
sorting was O(n). It turns out that if you think about it
properly, it is.

Sorting is O(1) if, rather than counting comparisons or swaps,
you count calls to qsort().

True, but no cigar. A more precise statement is that the time
required for sorting is O(n) - omega(n) if you prefer.

I don't see how your statement is more precise than mine; it's just
a different statement. (My statement is admittedly silly.)