WHAT IS selection sort??

[srinivasan106]

for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
count++;
}
}
}

void select(int a[],int n)
{
for(i=0;i<=n;i++)
{
k=i;
min=a[i];
for(j=i+1;j<=n-1;j++)
{
if(a[j]<min)
{
min=a[j];
k=j;
count++;
}
else count++;
}
a[k]=a[i];
a[i]=min;
}
}

which one is selection sort???first or sec??

[Ancient Dragon]

Neither one is selection sort. Read this for an algorithm.
The second one is not a sort of any kind because it contains errors

>>for(i=0;i<=n;i++)

Arrays are numbered 0, 1, 2, ... N-1. So i <= n should be just i<n

[srinivasan106]

Neither one is selection sort. Read this for an algorithm.
The second one is not a sort of any kind because it contains errors

>>for(i=0;i<=n;i++)

Arrays are numbered 0, 1, 2, ... N-1. So i <= n should be just i<n

actuAlly sec algorithm computes minimum of the array each time and inserting it at first..
finding minimum in an array in linear time.. then inserting it at first by swapping the a[position of minimum] with the a[first] so it turns to be o(n2).. also i thought selecting minimum for each time and hence the name selection sort>??

[Momerath]

actuAlly sec algorithm computes minimum of the array each time and inserting it at first..

Unless you pass parameters that are wrong, the second example generates an error. For example, let's say you have an array of 10 items. If you call your method with select(myArray, 10) You will get an error when j becomes 10 in line 9. There are 10 elements to the array, but they are from 0 to 9. j being 10 causes problems. The same holds true for your i variable.

This is why the previous poster said it wasn't anything, since it won't work.

[Adak]

The first sort you listed is one I use as an "Easy" sorter. It's like a bubble sort, but simpler to remember and quicker to keyboard also. Performance is similar to, but slightly faster than, bubble sort.

You can tell it's NOT bubble sort, because bubble sort compares only adjacent values in the array. That's why it "bubbles", as it sorts. ;)

I now call the first sort program "Easy sort", but it's a hybrid of Bubble and Selection sort (but without the selection of a minimum, so it's no selection sort, either.)

The only advantage of Selection sort, imo, is that it limits swaps to the absolute minimum. It does a LOT of comparisons, but swaps are WAY less than other sorting algorithms.

If you were given the task of putting all the cars in a large car yard, into some kind of sorted order (maybe by make and color groups), then you would naturally use Selection sort, yourself (if you were smart). Because comparing the cars is quick (just by looking), but driving each car for every swap, is very time consuming (you have to get car keys, walk around, find a place for temporary parking, etc.).

[srinivasan106]

The first sort you listed is one I use as an "Easy" sorter. It's like a bubble sort, but simpler to remember and quicker to keyboard also. Performance is similar to, but slightly faster than, bubble sort.

You can tell it's NOT bubble sort, because bubble sort compares only adjacent values in the array. That's why it "bubbles", as it sorts. ;)

I now call the first sort program "Easy sort", but it's a hybrid of Bubble and Selection sort (but without the selection of a minimum, so it's no selection sort, either.)

The only advantage of Selection sort, imo, is that it limits swaps to the absolute minimum. It does a LOT of comparisons, but swaps are WAY less than other sorting algorithms.

If you were given the task of putting all the cars in a large car yard, into some kind of sorted order (maybe by make and color groups), then you would naturally use Selection sort, yourself (if you were smart). Because comparing the cars is quick (just by looking), but driving each car for every swap, is very time consuming (you have to get car keys, walk around, find a place for temporary parking, etc.).

thank you adak.. but i still have a confusion,... the first algorithm ,i was taught as the bubble sort,.. can you exactly tell where easy algorithm and bubble sort differs???. and selection sort do n comparisons and also easy sort (as you say) also swaps n times.

[Adak]

Easy sort is ALMOST the same as a bubble sort, but the inner loop of a bubble sort ONLY compares ADJACENT values in the array. n with n+1, for instance.

Now look at Easy sort's inner loop. It STARTS the inner loop comparing n to n+1, but then it compares n to n+2, then to n+3, and so on. Those are NOT all adjacent values in the array. Only one of them is adjacent, in fact, at the start of each inner loop.

Also, in the bubble sorts that I've seen, they use a flag variable like "sorted", and it's set to zero in the first lines of the bubble sort. When Bubble sort completes a pass, and it has found nothing to sort, it sets the "sorted" variable to 1, and subsequently leaves the outer sort loop.

So Easy sort is definitely in the same sorting class as Bubble sort, but it just doesn't "Bubble", the values up, like Bubble sort does.

Although the number of comparisons may be similar on a particular sort, Selection sort will ALWAYS have the lowest possible number of swaps made - that's what it was designed to do.

[srinivasan106]

Easy sort is ALMOST the same as a bubble sort, but the inner loop of a bubble sort ONLY compares ADJACENT values in the array. n with n+1, for instance.

Now look at Easy sort's inner loop. It STARTS the inner loop comparing n to n+1, but then it compares n to n+2, then to n+3, and so on. Those are NOT all adjacent values in the array. Only one of them is adjacent, in fact, at the start of each inner loop.

Also, in the bubble sorts that I've seen, they use a flag variable like "sorted", and it's set to zero in the first lines of the bubble sort. When Bubble sort completes a pass, and it has found nothing to sort, it sets the "sorted" variable to 1, and subsequently leaves the outer sort loop.

So Easy sort is definitely in the same sorting class as Bubble sort, but it just doesn't "Bubble", the values up, like Bubble sort does.

Although the number of comparisons may be similar on a particular sort, Selection sort will ALWAYS have the lowest possible number of swaps made - that's what it was designed to do.

thank u adak......very good explanation.

[localinternet]

you can use selection sort function.

void selection(int elements[], int array_size)
{
int i, j, k;
int min, temp;
for (i = 0; i < maxsize-1; i++)
{
min = i;
for (j = i+1; j < maxsize; j++)
{
if (elements[j] < elements[min])
min = j;
}
temp = elements;
elements = elements[min];
elements[min] = temp;
}