### C Program for sorting an array using Bubble Sort and Insertion Sort

#include<iostream>
using namespace std;
int main()
{
cout<<"manin()\n";
int arr,n,i,j,t;
cout<<"Enter the number of elements in array:"<<endl;
cin>>n;
cout<<"Enter the elements:";
for(i=0;i<n;i++)
cin>>arr[i];

cout<<"Entered the elements:"<<endl;
for(i=0;i<n;i++)
cout<<arr[i]<<" ";

/*
cout<<"Bubble sort to arrange in ascending order:"<<endl;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(arr[j]>arr[j+1])
{
cout<<n-i-1<<" "<<j<<" "<<j+1<<" "<<endl;
t=arr[j];
arr[j]=arr[j+1];
arr[j+1]=t;
}
}
}
*/
//OR
/*
Selection sort: By first scanning the entire list before locating the exact pair of numbers to swap, only two writes to memory are performed by Selection Sort for each O(n) scan,whereas
Bubble Sort does writes on each and every comparison. So, Bubble Sort does O(n^2) writes. while selection sort does O(n) writes to mwmory.
*/
cout<<"\nSelection sort to arrange in ascending order:"<<endl;
for(i=0;i<n-1;i++)//mind n-1
{
for(j=i+1;j<n;j++) //mind n
{
if(arr[i]>arr[j])
{
cout<<n<<" "<<i<<" "<<j<<" "<<endl;
t=arr[j];
t=arr[i];
arr[i]=arr[j];
arr[j]=t;
}
}
}

cout<<"Sorted array elements are:"<<endl;
for(i=0;i<n;i++)
cout<<arr[i]<<" ";

cout<<endl;
return 0;
}
/*
//Selection Sort:
manin()
Enter the number of elements in array:
5
Enter the elements:5
4
3
2
1
Entered the elements:
5 4 3 2 1
Selection sort to arrange in ascending order:
4 1 2
4 2 3
4 3 4
4 4 5
3 2 3
3 3 4
3 4 5
2 3 4
2 4 5
1 4 5
Sorted array elements are:
1 2 3 4 5

//Bubble sort

manin()
Enter the number of elements in array:
5
Enter the elements:5
4
3
2
1
Entered the elements:
5 4 3 2 1
Selection sort to arrange in ascending order:
5 0 1
5 0 2
5 0 3
5 0 4
5 1 2
5 1 3
5 1 4
5 2 3
5 2 4
5 3 4
Sorted array elements are:
1 2 3 4 5
*/
/*
In Bubble sort , at every iteration you find a largest number and push it to bottom (Bubble out larger number)
In Insertion sort you have two regions one sorted and another unsorted.
At Every Iteration you pick up an element from unsorted region and insert at proper location in Sorted region.

Insertion Sort and Bubble sort both have Worst Case O(N^2).
But if the array is mostly sorted Insertion Sort will perform better
For both insertion and bubble sort worst case is O(n^2)
*/