SELECTION SORTING: The selection sort starts from the first element and searches the entire list until it finds the minimum value. The sort places the minimum value i the first place, select the second element, and searches for the second smallest element. The process continues until the complete list is sorted. A selection sort is one in which successive elements are selected in order and placed into their proper sorted positions. The selection process needs to be done only from 1 to n – 1 rather than up to n. Analysis of the selection is so straightforward.
The first pass makes – 1 comparison, the second pass makes n – 2, and so on So total comparisons are (N – 1) + (N2) (NE -3) ++ 2 + 1 = N (N – 1) / 2 = 0 (N³) The little additional storage required (except to hold few temporary variables.). The sort may therefore be categorized as O (N³), although it is faster than the bubble sort there is no improvement if the input file is completely sorted or unsorted. Despite the fact that it is simple to code, it is unlikely that the straight selection sort would be used on any files but those for which n is small.
The selection sort algorithm for sorting works as follows. First, find the smallest element in the list and put it in the first position. Then find the second smaller element in the list and put it in the second position. It is to be noted that the number of comparisons in the selection sort algorithm is independent of the original sort of the elements. The selection sort method requires (n – 1) passes to sort an array.
Algorithm – Selection sorting in C
SELECTION SORT (A, N)
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1. Repeat Steps 2 to 5 for I = 1 to N – 1:
2. Set MIN : = A [U]
3. Set POS : = I.
4. Repeat Steps for J = 1 + 1 to N:
If A [J] < MIN, then :
(a) Set MIN : = A [J].
(b) Set POS : = J.
[End of If structure.]
[End of Step 4 loop.]
5. If I != POS, then
(a) Set TEMP : = A [ I ]
(b) Set A [ 1 ] = A [ POS ]
(c) Set A [ POS ] : = TEMP
[End of If structure.]
[End of step 1 loop.]
6. Return
Selection Sorting (First Logic) program in c.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void selection_sort(int [], int);
void main()
{
int a[SIZE],i,n;
clrscr();
printf("Enter how many elements");
scanf("%d",&n);
/* Input Array */
for(i=0;i<n;i++)
{
printf("Enter element %d",i+1);
scanf("%d",&a[i]);
}
selection_sort(a,n);
/* Output Array */
for(i=0;i<n;i++)
printf("%d ", a[i]);
getch();
}
void selection_sort(int a[], int n)
{
int i,j,t,min,minpos;
for(i=0;i<n-1;i++)
{
min = a[i];
minpos = i;
for(j=i+1;j<n;j++)
{
if(a[j] < min)
{
min = a[j];
minpos = j;
}
}
if(i != minpos)
{
t = a[i];
a[i] = a[minpos];
a[minpos] = t;
}
}
}Selection Sorting (Second Logic) program in c.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void selection_sort(int [], int);
void main()
{
int a[SIZE],i,n;
clrscr();
printf("Enter how many elements");
scanf("%d",&n);
/* Input Array */
for(i=0;i<n;i++)
{
printf("Enter element %d",i+1);
scanf("%d",&a[i]);
}
selection_sort(a,n);
/* Output Array */
for(i=0;i<n;i++)
printf("%d ", a[i]);
getch();
}
void selection_sort(int a[], int n)
{
int minpos;
int i,j,t;
for(i=0;i<n-1;i++)
{
minpos = i;
for(j=i+1;j<n-1;j++)
{
minpos = i;
for(j=i+1;j<n;j++)
{
if(a[minpos] > a[j])
minpos = j;
}
}
if(minpos != i)
{
t = a[i];
a[i] = a[minpos];
a[minpos] = t;
}
}
}