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

Groups > comp.programming > #1321

Re: What algorithm is this? (Variant of Selection sort?)

Show all headers | View raw

R. Rajesh Jeba Anbiah wrote:
> 
> On Feb 14, 8:34 pm, pete <pfil...@mindspring.com> wrote:
> > R. Rajesh Jeba Anbiah wrote:
> > > On Feb 13, 12:47 pm, Zeljko Vrba <mordor.nos...@fly.srk.fer.hr> wrote:
> > > > On 2012-02-13, R. Rajesh Jeba Anbiah <ng4rrjanb...@rediffmail.com> wrote:
> > > > ><?php
> > > > > $arr = array(10,9,8,7,6,5,4,3,2,1);
> > > > > for($i=0, $len=count($arr); $i<$len-1; ++$i){
> > > > >   for($j=$i+1, $len=count($arr); $j<$len; ++$j){
> > > > >      if ($arr[$i] > $arr[$j]) {
> > > > >         $temp = $arr[$i];
> > > > >         $arr[$i] = $arr[$j];
> > > > >         $arr[$j] = $temp;
> > > > >      }
> > > > >   }
> > > > > }
> > > > > ?>
> >
> > > > >    As I understand, selection sort is
> > > > > about finding index first and
> > > > > doing the swap. What about the above? Is it a variant or sort with
> > > > > some name? TIA
> >
> > > > Looks like textbook implementation of Bubble sort.
> >
> > >    Yes, found in textbook only. But, it's not a Bubble sort. Right?
> > >http://en.wikipedia.org/wiki/Bubble_sort
> >
> > It looks a lot like bubble sort,
> > but it is not bubble sort.
> >
> > Bubble sort works by swapping adjacent elements.
> > The algorithm which you have shown,
> > swaps elements which are not adjacent.
> >
> > I would just call your algorithm "simple selection sort",
> > while realizing that there are variations
> > on the way that it can be implemented.
> >
> > Selection sorts, sort from one end to the other.
> >
> > Knuth classifies heapsort
> > as belonging to the selection sort family of algorithms.
> > As heapsort is typically implementd for sorting arrays:
> > the last element is sorted first,
> > and then the next to last,
> > and so on.
> 
>     Thanks for your valuable feedback. On a personal note I'm thinking
> why it's not officially documented and named--even though it's
> available in some textbooks as "bubble sort".

That is definitely not bubble sort.

This is bubble sort:

$arr = array(10,9,8,7,6,5,4,3,2,1);
for($i=0, $len=count($arr); $i<$len-1; ++$i){
  for($j=$len-1, $len=count($arr); $j>$i; --$j){
     if ($arr[$j-1] > $arr[$j]) {
        $temp = $arr[$j-1];
        $arr[$j-1] = $arr[$j];
        $arr[$j] = $temp;
     }
  }
}


Bubble sort is a stable sort,
simple selection sort is not.

A stable sort is one in which 
the original order of equal keys is preserved.

For sorting integers, 
it makes no difference whether or not a sort is stable.

But if say for example, 
you were sorting pointers to text strings by string length,
then there would be a difference.

If 
    "one","two","three","four","five",
    "six","seven","eight","nine","ten"
were to be sorted by string length
according to your posted algorithm,
then the output would be:
    one
    two
    six
    ten
    four
    nine
    five
    eight
    three
    seven
Note that nine and five are out of their original order 
relative to each other, even though they are the same length.
Also note that eight three and seven are out of their original order 
relative to each other, even though they are the same length.

A stable sort by string length
of the original order would yield instead:
    one
    two
    six
    ten
    four
    five
    nine
    three
    seven
    eight
Note that same length words retain their 
original order relative to each other.


/* BEGIN ss.c */

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

#define NMEMB(A)    (sizeof (A) / sizeof *(A))

#define GT(A, B)    (comp((A), (B)) > 0)

int comp(const void *a, const void *b);

int 
main(void)
{
    char *arr[] = {
        "one","two","three","four","five",
        "six","seven","eight","nine","ten"
    };
    unsigned i;
    unsigned j;
    unsigned len;
    char *temp;

    len = NMEMB(arr);
    for (i = 0; i < len -1; ++i) {
        for (j = i + 1; j < len; ++j) {
            if (GT(arr + i, arr + j)) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    puts("BEGIN ss.c output\n");
    for (i = 0; i != len; ++i) {
        puts(arr[i]);
    }
    puts("\nEND ss.c output");
    return 0;
}

int 
comp(const void *a, const void *b)
{    
    const size_t a_len = strlen(*(const char *const *)a);
    const size_t b_len = strlen(*(const char *const *)b);
    
    return b_len > a_len ? -1 : b_len != a_len;
}

/* END ss.c */





/* BEGIN bs.c */

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

#define NMEMB(A)    (sizeof (A) / sizeof *(A))

#define GT(A, B)    (comp((A), (B)) > 0)

int comp(const void *a, const void *b);

int 
main(void)
{
    char *arr[] = {
        "one","two","three","four","five",
        "six","seven","eight","nine","ten"
    };
    unsigned i;
    unsigned j;
    unsigned len;
    char *temp;

    len = NMEMB(arr);
    for (i = 0; i < len - 1; ++i) {
        for (j = len - 1; j > i; --j) {
            if (GT(arr + j - 1, arr + j)) {
                temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    puts("BEGIN bs.c output\n");
    for (i = 0; i != len; ++i) {
        puts(arr[i]);
    }
    puts("\nEND bs.c output");
    return 0;
}

int 
comp(const void *a, const void *b)
{    
    const size_t a_len = strlen(*(const char *const *)a);
    const size_t b_len = strlen(*(const char *const *)b);
    
    return b_len > a_len ? -1 : b_len != a_len;
}

/* END bs.c */

-- 
pete

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

What algorithm is this? (Variant of Selection sort?) "R. Rajesh Jeba Anbiah" <ng4rrjanbiah@rediffmail.com> - 2012-02-12 23:36 -0800
  Re: What algorithm is this? (Variant of Selection sort?) Zeljko Vrba <mordor.nospam@fly.srk.fer.hr> - 2012-02-13 07:47 +0000
    Re: What algorithm is this? (Variant of Selection sort?) "R. Rajesh Jeba Anbiah" <ng4rrjanbiah@rediffmail.com> - 2012-02-12 23:55 -0800
      Re: What algorithm is this? (Variant of Selection sort?) pete <pfiland@mindspring.com> - 2012-02-14 10:34 -0500
        Re: What algorithm is this? (Variant of Selection sort?) "R. Rajesh Jeba Anbiah" <ng4rrjanbiah@rediffmail.com> - 2012-02-14 21:04 -0800
          Re: What algorithm is this? (Variant of Selection sort?) pete <pfiland@mindspring.com> - 2012-02-15 01:41 -0500
            Re: What algorithm is this? (Variant of Selection sort?) pete <pfiland@mindspring.com> - 2012-02-22 22:52 -0500
          Re: What algorithm is this? (Variant of Selection sort?) Patricia Shanahan <pats@acm.org> - 2012-02-15 09:45 -0800
  Re: What algorithm is this? (Variant of Selection sort?) Robert Wessel <robertwessel2@yahoo.com> - 2012-02-13 03:59 -0600
    Re: What algorithm is this? (Variant of Selection sort?) "R. Rajesh Jeba Anbiah" <ng4rrjanbiah@rediffmail.com> - 2012-02-13 02:34 -0800

csiph-web