## Insertion Sort asymptotic Analysis

Posted: January 2, 2015 in Programming
Tags: , , , , , , , , , , ,

##### Before the analysis , lets have a look at pseudo code of insertion sort. For input array A

```
INSERTION-SORT(A)

for j <-- 2 to length [A]

do key <-- A[j]

i <-- j - 1

while i > 0 and A[i] > key

do A[i + i] <-- A[i]

i <-- i - 1

A[i + 1] <-- key

&nbsp;

```

##### I tried implementing the same in C++. Here is the code

```#include <iostream>

using namespace std;

int main()
{
int arr[] = {5,2,4,6,1,3};
int arrSize =  sizeof(arr)/sizeof(arr[0]);
int key;
int i;
for(int j=1; j<arrSize; j++)
{
key = arr[j];
i = j - 1;
while(i >= 0 && arr[i] > key)
{
arr[i+1] = arr[i];
i = i - 1;
}

arr[i+1] = key;

}

for(int i=0; i<arrSize; i++)
cout << arr[i] << " " << endl;
return 0;
}
```

Output is :

##### Before we start our analysis of the insertion sort, we will see how many times each statement runs.

```
INSERTION-SORT(A)

for j <-- 2 to length [A] ----------------------------  runs n times

do key <-- A[j] --------------------------------------  runs n-1 times

i <-- j - 1     --------------------------------------  runs n-1 times
n
while i > 0 and A[i] > key --------------------------- ∑ tj
j=2
n
do A[i + i] <-- A[i]  -------------------------------- ∑ tj - 1
j=2

n
i <-- i - 1 ------------------------------------------ ∑ tj - 1
j=2
A[i + 1] <-- key ------------------------------------- n-1

&nbsp;

```

#### These 3 screenshots will explain how insertion sort is O(n) in best case and O(n square) in worst case.

##### This you tube video will be helpful to understand the same

https://www.youtube.com/watch?v=yXwFrc5GS6A — click the view the video

## Learning Year – 2014 !!!!

Posted: December 31, 2014 in Uncategorized

## Blogging

#### And at last, blogging.. Couldn’t post much.. Thats gonna be my new year resolution. Will try to share as much as i can . !!!

Happy Learning !!!

## Sorting variable length strings in lexicographic order C++

Posted: December 18, 2014 in Programming
Tags: , , , , ,

On an occasion i had a file with words listed one by one and i wanted to sort the file in lexicographic order. Since i work in linux machines , its just 1 command . `cat filename | sort ` to sort it in lexicographic order. But i wanted to do it in c++.  I tried googling for suggestions and found out that radix and bucket sort would help me out. And then i tried implementing the concept of Radix MSD to arrive the result. Sharing the code. I have added inline comments in the program. Hope it helps  (Note: i just wanted to arrive with the solution.. Not much concerned about efficiency of the program :-))

```#include <iostream>
#include <map>
#include <vector>
#include <fstream>

using namespace std;

int main()
{

vector<string> words;

map<char,vector<string> > bucket;
map<char,vector<string> > ::iterator it;
bucket.clear();
vector<string> tempVec;

// initializing map with null vector and empty for variable length string
bucket[' '] = tempVec;
char ch;
//for(int i=97; i<123; i++)
for(int i=65; i<91; i++)
{
ch = i;
bucket[ch] = tempVec;
}

words.push_back("jump");
words.push_back("sit");
words.push_back("carry");
words.push_back("run");
words.push_back("site");
words.push_back("runner");

/*cout << "init" << endl;
for(int k=0; k<words.size(); k++)
cout << words[k] << "  ";
cout << endl;*/

// finding the maximum character
int max = 0;
for(int i=0; i<words.size(); i++)
{
max = (max > words[i].length())?max:words[i].length();
}

// loop from max char till first char
for(int i=max-1; i>=0; i--)
{
//cout << "Running for Phase " << i << endl;
// loop through the entire vector
for(int j=0; j<words.size(); j++)
{
string word = words[j];
int temp_len = word.length();
// there may be possibility that word boundary is less than max
if(temp_len < i)
{
// push into the "" bucket
//cout << "Pushing " << word << " into bucket " << "[empty]" << endl;
bucket[' '].push_back(word);
}
else
{
// index exists .. Hence check the char
char temp_char;
temp_char = word[i];

// insert into map with temp_char, word
bucket[temp_char].push_back(word);
//cout << "Pushing " << word << " into bucket " << temp_char << endl;

}

}
// end of this loop, all the words are inserted into corresponding buckets
// clear the input vector -- because we are going to change the order
words.clear();

// iterate through the keys and write the order into input vector
for(it=bucket.begin(); it!=bucket.end(); it++)
{
tempVec = it->second;
for(int k=0; k<tempVec.size(); k++)
words.push_back(tempVec[k]);

tempVec.clear();
}

/*cout << "After bucket insertion words are  " << endl;
for(int k=0; k<words.size(); k++)
cout << words[k] << "  ";
cout << endl;
*/

// now we have the correct order of the phase .. hence clear the bucket
tempVec.clear();
for(it=bucket.begin(); it!=bucket.end(); it++)
{
it->second.clear();
}

//cout << endl;

}
cout << "Answer is " << endl;
for(int k=0; k<words.size(); k++)
cout << words[k] << endl;

return 0;
}

```

[ALGORITHM]
1. Read the words and push into vector
2. find the max value by iterating the vector and finding length of all words
3. Iterate from max to 0
4. take each words first letter and push into corresponding bucket
5. Iterate through the buckets and save it as input word list order
6. After 0th Iteration , input vector will have the result.

[EXPLANATION]

step – 1
words pushed into vector

jump, sit, carry, run, site , runner

step – 2

finding the maximum length string
it would be runner – 6

step – 3

Iterating from index 5 to 0

ITERATION – 5 :
Note : if the word length is less than index , we need to push in empty bucket(‘ ‘)

‘ ‘ – jump,sit,carry,run,site
r – runner

Hence, array order will be – jump, sit, carry, run, site

ITERATION – 4 :

4th index of the words carry and runner are [y] and [e]

‘ ‘ – jump, sit, run, site
e – runner
y – carry

Hence, array order will be – jump, sit, run, site, runner, carry

ITERATION – 3 :

3rd index for the words jump, carry, site, runner [p],[r],[e],[n]

‘ ‘ – sit, run
e – site
n – runner
p – jump
r – carry

Hence array would be sit, run, site, runner, jump, carry

ITERATION – 2 :

2nd index for the words sit, run , site, runner, jump, carry are [t],[n],[t],[n],[m], [r]

m – jump
n – run, runner
r – carry
t – sit, site

Hence array would be jump, run, runner, carry, sit, site

ITERATION – 1

1st index for the words jump, run, runner, carry, sit, site are [u],[u],[u],[a],[i],[i]
a – carry
i – sit , site
u – jump, run, runner

Hence array would be , carry, sit, site , jump, run, runner

ITERATION – 0

0th index of the words are [c], [s], [s], [j], [r], [r]

c – carry
s – sit, site
j – jump
r – run, runner

Hence OUPUT : carry, sit , site , jump, run, runner

## Good bye wake me up

Posted: November 19, 2014 in Health
Tags: , , ,

Are you the kind of person who keeps almost 10 to 15 alarms in your phone just to get up in the right time?

Are you the person to snooz alarm 5 to 10 times before getting up?

Forget it. . Thinks have changed.

Have you ever heard this quote “if you wanna get up in first alarm, just keep the alarm  clock away from your bed”

Now an android app made it real. From now there is no wake up alarm for us . Only we have a
WALK UP ALARM.

You can keep the phone near the bed , but once the alarm triggers it can be switched off only if you walk ten steps with your phone. Otherwise it ll be keep ringing.

I personally tried it today and i got up in the first ring . Thank you walk me up team for a great innovation.

## Find your Free time !!!!

Posted: October 18, 2014 in General Awareness
Tags: , , , , , , ,

“Are we really utilizing our time EFFICIENTLY ?”

Yesterday i watched “the last lecture” video by Mr. Randy Pausch that triggered few things in my mind. Do we really know , what we will be doing tomorrow 5.30 . Atleast, do we plan for that. For majority of us, answer is no. Atleast, for me !!!

After watching the video, i thought of finding a way through which i could find the golden time that am wasting through outt my life. Simple google search on apps lead me to 2 important android apps.

For ios users we have daily routines app which does the same stuff.

Firstly, the app routinely helps us to decide on what are all the things that we really need to do on daily basis . Hence, we can come up with our own list and check it up after completing it on day to day basis.

Second one is quiet interesting. Schedule Planner app helps us to list our stuff by dividing into categories. There are two tabs. Planned and Actual. You can plan your work, and you can move it to actual after performing it. In the pro version, we can edit our categories. Using this app for 1 week, we can easily find out on how we are wasting our time. and how we can manage it on useful stuff.

I could really see some changes in my learning process. You can try and share your comments as well.

## Old Pochmann Blindfold Tutorial (Memorization)

Posted: October 16, 2014 in Rubik
Tags: , , , , ,

It was a dream for me to learn 3 x 3 blindfold. Since , i was not good in memory skills , i thought it would never happen. But , after watching this video, everything changed and i learnt blindfold in a day .

Just in case, if you dont get a good clarity after seeing Zane C’s Video , i would really recomment to watch Badmephisto video given below

Since there are plently of methodologies covered in the video , i would like to stress more on the memorization part. Initially, the memorization part will take more time than to solve the pieces .

There are many ways through which you can memorize the piece orientation. People who are good in memory , use visual memory to memorize the pieces. But, visual memory wont last for a long time. And , it really needs good memory to remember all piece orientations.

Some People use objects to remember each piece. Even for this, we need a good memory because there will be around 15 to 20 object we need to remember with a connection.

Especially for the people like me, the third method is so suitable . We will label each piece with a Letter. Starting from UB as A we will move anti clockwise . In this case , you need not remember all the labels initially,

UB – A
UL – B
UF – C
UR – D

FU – E
FL – F
FD – G
FR – H

RU – I
RF – J
RD – K
RB – L

BU – M
BR – N
BD – O
BL – P

LU – Q
LB – R
LD – S
LF – T

UF – U
UL – V
UB – W
UR – Y (Not X , because we can form more words in Y than X )

For the initial solves, its fine to remember only 6 pieces

UB – A
FU – E
RU – I
BU – M
LU – Q
UF – U

From these pieces, we can appropriately move in anti clockwise direction and increase the alphabet .

Similarly, we can do it for Corners :

UBL – A
UFL – B
….
….
….
….
….
DBL – Y

Hence, we just need to remember a letter , rather than remembering the position.

And also, once you form sequence of letters , we can form words with it. For Ex:

C D L M T S W can be randomly made as

CoDe LiMiT SoftWare (am a CS Engg :P)

Hence, we can simply say :

2 sentences = a blind fold solve.

All we need is to move one piece at a time and create words with the corresponding notation.

## ImportError: No module named oauth2

Posted: July 18, 2014 in Programming
Tags: , , , , , , , ,

Very new to python Programming . I tried installing python 2.7 in my linux machine (ubuntu). Unfortunately , python 3 was already installed in the system.

For parsing the twitter tweets using python, i had to install oauth2 in my machine. i spent almost 2 to 3 hours doing it . Got almost 5 different kind of packages from internet and tried installing it.

Also installed additional libraries. PIP and all stuffs . But still, it didnt work. I got the same error as below

Traceback (most recent call last):
import oauth2 as oauth
ImportError: No module named oauth2

At last , i found that the error was occuring because of the 2 differnt python versions in my system.

Then i started locating python directory and checked where it is pointing to. when i checked /usr/bin/python , it was pointing to python 2.7.

Instead of running the script as

python script_name.py

i changed it to

/usr/bin/python script_name.py

And yes, it worked. Sometimes we complicate few easy stuffs :-)