Selection sort in C C++
Swapping with the smallest element in the array.
Important points
- Start from the first element and iterate the array to find smallest element and swap first and that element. Continue with second element, find the smallest available and swap it with second element. Continue till last element of the array
- After each iteration/pass , smallest element is moved to the front.
- K smallest elements can be obtained after k passes.
- Why name? As we select the smallest element and swap.
- Time complexity – O(n^2)
- Swaps in each iteration is 1. Algorithm with minimum number of swaps.
- Not adaptive
- Not stable
Program for selection sort in C language
#include<stdio.h>
#include<stdlib.h>
void swap(int *p, int *q)
{
int temp;
temp = *p;
*p = *q;
*q = temp;
}
void SelectionSort(int A[],int n)
{
int i,j,k;
for(i=0;i<n;i++){
for(j=k=i;j<n;j++)
{
if(A[k]>A[j])
k=j;
}
swap(&A[i],&A[k]);
}
}
int main()
{
int A[10] = {1,5,2,1,6,3,6,2,5,10};
int i;
SelectionSort(A,10);
for(i=0;i<10;i++)
{
printf("%d ",A[i]);
}
return 0;
}
