# Sorting

1.Selection Sort

• Find the smallest element, and put it to the first position.
• Find the next smallest element, and put it to the second position.
• Repeat until all elements are in the right positions.

Code in C++

#include<iostream>
#include<conio.h>
using namespace std;
void main()
{
int a[100],i,n,p,k,min,loc,temp;

cout<<“\n– SELECTION SORT –\n\n”;
cout<<“Enter No. of Elements=”;
cin>>n;

cout<<“\nEnter Elements=\n”;
for(i=1;i<=n;i++)
{
cin>>a[i];
}

for(p=1;p<=n-1;p++)              // Loop for Pass
{
min=a[p];                        // Element Selection
loc=p;

for(k=p+1;k<=n;k++)              // Finding Min Value
{
if(min>a[k])
{
min=a[k];
loc=k;
}
}

temp=a[p];                        // Swap Selected Element and Min Value
a[p]=a[loc];
a[loc]=temp;

}

cout<<“\nAfter Sorting : \n”;

for(i=1;i<=n;i++)
{
cout<<a[i]<<endl;
}

getch();
}

2. Insertion Sort

• Take the first element as a sorted sub-array.
• Insert the second element into the sorted sub-array (shift elements if needed).
• Insert the third element into the sorted sub-array.
• Repeat until all elements are inserted.

Code in C++

#include<iostream>
#include<conio.h>
using namespace std;
void main()
{

int a[100],i,n,p,ptr,temp;

cout<<“\n– INSERTION SORT –\n\n”;

cout<<“Enter No. of Elements : “;
cin>>n;

cout<<“\nEnter Elements : \n”;
for(i=1;i<=n;i++)
{
cin>>a[i];
}

a[0]=0;

for(p=2;p<=n;p++)
{
temp=a[p];
ptr=p-1;

while(temp<a[ptr])
{
a[ptr+1]=a[ptr];                // Move Element Forward
ptr–;
}

a[ptr+1]=temp;                 // Insert Element in Proper Place
}

cout<<“\nAfter Sorting : \n”;
for(i=1;i<=n;i++)
{
cout<<a[i]<<endl;
}

getch();
}

3. Bubble Sort

• Scan the array, swapping adjacent pair of elements if they are not in relative order. This bubbles up the largest element to the end.
• Scan the array again, bubbling up the second largest element.
• Repeat until all elements are in order.

Code in C++

#include<iostream>
#include<conio.h>
using namespace std;
void main()
{
int a[100],i,n,p,k,min,loc,temp;

cout<<“\n– SELECTION SORT — \n\n”;
cout<<“Enter No. of Elements=”;
cin>>n;

cout<<“\nEnter Elements=\n”;
for(i=1;i<=n;i++)
{
cin>>a[i];
}

for(p=1;p<=n-1;p++)              // Loop for Pass
{
min=a[p];                        // Element Selection
loc=p;

for(k=p+1;k<=n;k++)              // Finding Min Value
{
if(min>a[k])
{
min=a[k];
loc=k;
}
}

temp=a[p];                        // Swap Selected Element and Min Value
a[p]=a[loc];
a[loc]=temp;

}

cout<<“\nAfter Sorting : \n”;

for(i=1;i<=n;i++)
{
cout<<a[i]<<endl;
}

getch();
}