Straight Selection Sort

One of the easiest sorting methods is selection sort. Beginning with the first element of the given array, a search is made to find the largest element in the array. When the element is found this element is interchanged with the last element of the array. Now the size of the unsorted array will be reduced but one. A search for the largest element of the unsorted array is carried out. When this element is found it will be interchanged with the last element of the unsorted array. Once again the unsorted array will be reduced by 1 and the above process will be repeated till the entire array is sorted in ascending order.

ALGORITHM
1. Establish an array ‘a’ with ‘n’ elements
2. Repeat through step 6 for ‘n-1’ times
3. Repeat the position of the array already sorted
4. Repeat step 5 for the elements in unsorted position of the array
5. Record location of the largest element in the unsorted array
6. Exchange last element in the unsorted array with the largest element

PERFORMANCE OF THE ALGORITHM
During the first pass, in which the largest element is found, n-1 elements are compared. In general, for ith pass of the sort, n-I comparisons are required

So total number of comparisons
n-1 + n-2 + ……… + 1

Time Complexity = O(n²)

/**** C Program For Implementation Of Selection Sort ****/

#define MAX 10
char name[MAX][15];
void sort(int n)
{
int i,j,index;
char temp[15];
for(i=n;i >0;i--)
{
strcpy(temp,name[1]);
index=1;
for(j=1;j< =i;j++) { if(strcmp(name[j],temp) >0)
{
strcpy(temp,name[j]);
index=j;
}
}
strcpy(name[index],name[i]);
strcpy(name[i],temp);
}
}
void main()
{
int i,j,n;
clrscr();
A: printf("\n\nENTER HOW MANY NAMES: ");
scanf("%d",&n);
if(n >MAX)
{
printf("\n\t\tARRAY SIZE IS ONLY %d",MAX);
goto A;
}
else
{
printf("\n\t ENTER %d Names : \n",n);
for(i=1;i< =n;i++) { printf("\t\t"); scanf("%s",name[i]); } sort(n); printf("\n\n\t\t*********** SORTED LIST ************"); for(i=1;i< =n;i++) printf("\n \t\t\t\t%s",name[i]); } getch(); } /********** OUTPUT ************** ENTER HOW MANY NAMES: 12 ARRAY SIZE IS ONLY 10 ENTER HOW MANY NAMES: 4 ENTER 4 Names : Lionel Cyril Valerian Noronha *********** SORTED LIST ************ Cyril Lionel Noronha Valerian **************************************/