selection sort

                                     

                                            SELECTION SORT

Definition:  
A Selection Sort is a Sorting algorithm which finds the smallest element in the array and swaps with the first element then with the second element and continues until the entire array is sorted. It sorts an array by repeatedly finding the minimum element from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.

***It sorts the  numbers of an array in ascending order. With a little modification, it arranges numbers in descending order.
Algorithm For Selection Sort in C:

Algorithm Selectl(a, n, k):
 // Selects the kth-smallest element in a[1:n] and places it
 // in the kth position of a[].The remaining elements are
 // rearranged such that a[m] <a[k] for 1< m <k, and
 // a[m] >a[k] for k < m <n.
 {
 low :=1; up :=n +1;
 a[n+ 1]:=infinity;  // a[n+1] is set  to infinity.
repeat 
 {
// Each time the loop is entered,
// 1<low <k <up<n+ 1.
 j :=Partition(a,low,up)',
 // j is such that a[j] is the jth-smallest value in a[].
 if (k = j) then return; 
 else if (k <j) then up :=j;   // j is the new upper  limit.
else  low :=j +1;   // j +1is the new lower  limit.
}
until(false); } 
Programming of Selection Sort On Code Blocks :
#include<stdio.h>
int main()
{
    int n,a[20],i,j,m,t;
    printf("How many elements do you want to execute.");
    scanf("%d",&n);
    printf("Enter the elements ");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        m=i;
        for(j=i;j<n;j++)
            {
            if(a[m]>a[j])
                m=j;
        }
            t=a[m];
            a[m]=a[i];
            a[i]=t;
    }
    for(i=0;i<n;i++)
    printf("%d  ",a[i]);
    return 0;
} 
Output of the Program:

Example:

Time Complexity For Selection Sort:     
Worst-case space complexity: O(n2) 
Best-case performance: О(n2) 
Worst-case performance: О(n2)
Space Complexity :O(1)

by :Rani