Selection sort

[Rahul.menon]

#include<stdio.h>
#include<conio.h>

void main()
{
  int num[50],i,i1,j,temp = 1,cnt = 0;
  printf("How many elements ");
  scanf("%d",&i);
  printf("Enter the elements ");
  for(j = 0;j<i;j++)
	{
	 scanf("%d",&num[j]);
	}

	i1 = 0;
	j=1;
	while(i1 < i )
	{
		for( ;j<i;j++)
		  {                    
			if((num[j] < num[i1])&& (i1<i))
			  {
				 temp = num[j];          //algorithm for sel sort
				 num[j] = num[i1];
				 num[i1] = temp;
			  }
			  cnt++;   //counting iterations
		  }
		  i1++;
		  j=1;
		  j+=i1;
	}
	for(j = 0 ;j<i;j++)
	 printf("\n%d",num[j]);

	 printf("\n%d ",cnt);
}

Hi,
the sel sort algorithm takes n^2 time as per the wiki and what is taught generally(pls correct if wrong) .
where each element is checked every time(i:e loop runs n*n times and values are swapped) . but when i modified the code a bit the algo becomes log n and running more efficiently than bubble sort. so is it that the change has changed meaning and its no more selection sort.

[Adak]

Selection sort does NOT compare every element, with every other element, every time through the loop - you misunderstood the algorithm.

Selection sort is always a step better than bubble sort, in my tests on both random and real life data.

Bubble sort and Gnome sort, are the slowest non-joke sorting algorithms, that I've ever seen. There's nothing to recommend either one of them, frankly.

This is a simplified version of Selection sort, and note how the j variable starts with i+1, on every pass through the inner loop:

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

I like this version because it's easy to memorize, and use. It doesn't select anything, so I call it Easy or EZ sort, but it's based on Selection sort. Compare it with your version.

[Rahul.menon]

My doubt was how the order of sel sort algo becomes n^2(ref in wiki,cprg.com....) whereas it shows linear behaviour. for 4 elements, irrespective of order the iterations are 6 for 5-10 and so on. its never square.

[Adak]

Excuse my earlier post, when you start talking about a new sorting algorithm, I easily get a new focus.

Yes, Selection sort is stated as an O(n^2) algo. This has NOTHING to do with your own hybrid algorithm, however efficient it may be. The Wikipedia article that you referred to spells out the reason why -- I can certainly do no better.

Where Selection sort shines, is when you have a situation like this:

Say you have a sorting job where the comparisons are quickly made, but the swaps are incredibly time-consuming due to network constraints. Selection sort is the algo you want to use, in that case. It ALWAYS makes the fewest swaps of any sorting algorithm.

In everyday life, it's the sorting algo you would use if you had a job of sorting out a huge yard of vehicles, according to type, and currently they were all mixed up. Any other algorithm would have you moving cars FOREVER, to get things right. But using Selection sort, it would be as easy as it can be. Because the comparisons are cheap (you can tell just be looking), but the time and effort to swap vehicle parking spaces, is very high comparatively.

Aside from this huge efficiency with minimal swapping, Selection sort has nothing to recommend it, imo.

To judge it accurately, be sure you're using the REAL Selection sort, and not a hybrid algorithm. Just for fun, count the number of comparisons made while sorting out an array of 100 random integers, AND the number of actual swaps made. Do it with Selection sort, Bubble sort, and any other sorting algo of your choice.

You'll be amazed at the differences in the number of low swaps by Selection sort, compared to all the others. Quite stunning, really. Comparisons are a completely different result, however! Very educational.

[Rahul.menon]

Thanx Adak Good Explanation