Hello! Guys. I always thought of starting my blog on algorithms for Computer Science Enthusiasts but could never get over my lazy melodrama. So, finally I get over my laziness and I am presenting to you the first post of my blog. I will constantly blog about famous algorithms which would help you all. Please drop in your comments and suggestions.
In this post I have implemented Insertion Sort in C++ using Vectors.
#include<iostream> // including the input/output library
#include<vector> // including the vector template
using namespace std;
int main(){
vector<int>v = {2,5,3,1,6,4,0,7}; // list initializing the vector
int key,j; // declaring the key and j
for(auto i=1; i<=v.size();++i){ /* iterating from 2nd number in the vector till the last,
key = v[i]; because we assume the first number to be sorted in itself
j = i - 1; which shows that loop invariant holds before first iteration
of the loop*/
while(j>=0 && v[j]>key){ we compare key with all the numbers from i-1 to 0,
v[j+1]=v[j];
--j;
}
v[j+1]=key; // inserting the key at its proper position
}
for(auto &k:v) // printing the vector once sorted
cout<<k<<" ";
return 0;
}
Explanation of the Insertion Sort Algorithm:
I will take a practical example to explain the sorting. Have you people played a Game of Cards before? What a stupid question I'm asking. We all have played it. So assume, that Sunday evening you are evening you are playing Cards. And You wish to place cards in sorted order of their numbers. So, How you will you start?
1. You will pick a card from a deck of cards face down on the table.
2. You pick the first card and luckily got your favorite number - 5.
3. So you hold that card in your left hand.
4. Without any further delay, you pick the second card and you got your girlfriends favorite number-2
5.You know very well what to do, as you love your girlfriend very much, so you will place her favorite number in your left hand, but as you love her and the number 2 is less than 5, you gotta insert 2 numbered card before the 5. And you find that that your girlfriend becomes more happy because you have successfully sorted the two cards in increasing sequence.Woaa!
6.Pick the next card, the next card turns out be 3, now you compare first compare 3 with 5. You can insert 3 before 5 but wait you gotta compare with all the cards in the hand. So, you compare 3 with 2 and you find that you are done completing checks with all the cards. As 3 is greater than 2 and less than 5. So you insert 3 between 2 and 5. And you again successfully sorted the order.
7.Continue doing it till there is no card left on the table.
And you will happily sort the cards in increasing order of their numbers.
In this post I have implemented Insertion Sort in C++ using Vectors.
#include<iostream> // including the input/output library
#include<vector> // including the vector template
using namespace std;
int main(){
vector<int>v = {2,5,3,1,6,4,0,7}; // list initializing the vector
int key,j; // declaring the key and j
for(auto i=1; i<=v.size();++i){ /* iterating from 2nd number in the vector till the last,
key = v[i]; because we assume the first number to be sorted in itself
j = i - 1; which shows that loop invariant holds before first iteration
of the loop*/
while(j>=0 && v[j]>key){ we compare key with all the numbers from i-1 to 0,
v[j+1]=v[j];
--j;
}
v[j+1]=key; // inserting the key at its proper position
}
for(auto &k:v) // printing the vector once sorted
cout<<k<<" ";
return 0;
}
Explanation of the Insertion Sort Algorithm:
I will take a practical example to explain the sorting. Have you people played a Game of Cards before? What a stupid question I'm asking. We all have played it. So assume, that Sunday evening you are evening you are playing Cards. And You wish to place cards in sorted order of their numbers. So, How you will you start?
1. You will pick a card from a deck of cards face down on the table.
2. You pick the first card and luckily got your favorite number - 5.
3. So you hold that card in your left hand.
4. Without any further delay, you pick the second card and you got your girlfriends favorite number-2
5.You know very well what to do, as you love your girlfriend very much, so you will place her favorite number in your left hand, but as you love her and the number 2 is less than 5, you gotta insert 2 numbered card before the 5. And you find that that your girlfriend becomes more happy because you have successfully sorted the two cards in increasing sequence.Woaa!
6.Pick the next card, the next card turns out be 3, now you compare first compare 3 with 5. You can insert 3 before 5 but wait you gotta compare with all the cards in the hand. So, you compare 3 with 2 and you find that you are done completing checks with all the cards. As 3 is greater than 2 and less than 5. So you insert 3 between 2 and 5. And you again successfully sorted the order.
7.Continue doing it till there is no card left on the table.
And you will happily sort the cards in increasing order of their numbers.
No comments:
Post a Comment