Sorting – Straight Selection Sort

Sorting – Straight Selection Sort

• Begin from the first element, taking i=0 to n-1.
• Find the minimum number in the first scan.
• Interchange i^th element with the minimum number.
• Start searching minimum element again from i+1 to n.
• The number of scans is equal to the number of elements.
• Stop scan when the last element remains to be replaced with min.
• Display the output which is now sorted.

Though this method requires only half the number of comparisons required by simple selection sort, but the time complexity is still O(n²).

Program to implement Straight Selection Sort:

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

#define MAX 5

void straightselectionsort(int arr[],int n)
{
int i,j,k;
float min,temp;
for(i=0;i<n-1;i++)
{
min=arr[i];
k=i;
for(j=i+1;j<n;j++)
{if(arr[j]<min)
{min=arr[j];
k=j;
}
}
arr[k]=arr[i];
arr[i]=min;
}
}

void main()
{
int arr[MAX];
int i,n;
clrscr();
printf(“\nEnter the value of n?”);
scanf(“%d”,&n);
for(i=0;i<n;i++)
{printf(“\nEnter the value of x?”);
scanf(“%d”,&arr[i]);
}
printf(“\n\nArray you have entered is:\n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
straightselectionsort(arr,n);
printf(“\n\nSorted Array is: \n”);
for(i=0;i<n;i++)
printf(“%d\t”,arr[i]);
getch();
}