WAP to print 2D array matrix in Spiral Order

Question: Given a 2D array / matrix of integers. Write a program to print the elements in spiral order. Consider a matrix as show in the diagram to the right. The desired output of the program should be as: 1,2,3,4,8,12,16,20,19,18,17,13,9,5,6, 7,11,15,14,10.




Solution: There are several ways to solve this problem, but I am mentioning a method that is intuitive to understand and easy to implement. The idea is to consider the matrix similar to onion which can be peeled layer after layer. We can use the same approach to print the outer layer of the matrix and keep doing it recursively on a smaller matrix (with 1 less row and 1 less column).

Refer to the image below for a visual explanation. We start by printing the top-right layer of the matrix by calling the print_layer_top_right. It will print 1,2,3,4,8,12,16,20. The print_layer_top_right method then calls the print_layer_bottom_left method which will print 19,18,17,13,9,5. If you observe the size of the target matrix is reducing after each call. Each method basically calls the other method and passes the matrix indexes for the reduced matrix. Both methods take 4 index parameters which represent the target matrix. When the target matrix size is such that there is only one layer left the recursion terminates and by this time the code has printed all the numbers in the full matrix.




Code (C language):

<script type="syntaxhighlighter" class="brush: html"><![CDATA[

#include
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2);
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2);

int main(void)
{
int a[5][4] = {
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,16},
{17,18,19,20}
};

print_layer_top_right(a,0,0,3,4);
}

//
// prints the top and right shells of the matrix
//
void print_layer_top_right(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

// print the row
for(i = x1; i<=x2; i++)
{
printf("%d,", a[y1][i]);
}

//print the column
for(j = y1 + 1; j <= y2; j++)
{
printf("%d,", a[j][x2]);
}

// see if we have more cells left
if(x2-x1 > 0)
{
// 'recursively' call the function to print the bottom-left layer
print_layer_bottom_left(a, x1, y1 + 1, x2-1, y2);
}
}

//
// prints the bottom and left shells of the matrix
//
void print_layer_bottom_left(int a[][4], int x1, int y1, int x2, int y2)
{
int i = 0, j = 0;

//print the row of the matrix in reverse
for(i = x2; i>=x1; i--)
{
printf("%d,", a[y2][i]);
}

// print the last column of the matrix in reverse
for(j = y2 - 1; j >= y1; j--)
{
printf("%d,", a[j][x1]);
}

if(x2-x1 > 0)
{
// 'recursively' call the function to print the top-right layer
print_layer_top_right(a, x1+1, y1, x2, y2-1);
}
}

]]></script>

Run Here https://ideone.com/ut0Hx

WAP to Write Find MaximumSize Sub-Matrix From Given Matrxi having Size of R*C

Maximum size square sub-matrix with all 1s
April 4, 2010

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.

For example, consider the below binary matrix.

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

The maximum square sub-matrix with all set bits is

1 1 1
1 1 1
1 1 1

Algorithm:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.

1) Construct a sum matrix S[R][C] for the given M[R][C].
a) Copy first row and first columns as it is from M[][] to S[][]
b) For other entries, use following expressions to construct S[][]
If M[i][j] is 1 then
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
Else /*If M[i][j] is 0*/
S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
sub-matrix of M[][]

For the given M[R][C] in above example, constructed S[R][C] would be:

0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 2 2 0
1 2 2 3 1
0 0 0 0 0

The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.


C program

#include
#define bool int
#define R 6
#define C 5

/* UTILITY FUNCTIONS */
/* Function to get minimum of three values */

int min(int a, int b, int c)
{
int m = a;
if (m > b)
m = b;
if (m > c)
m = c;
return m;
}

void printMaxSubSquare(bool M[R][C])
{
int i,j;
int S[R][C];
int max_of_s, max_i, max_j;

/* Set first column of S[][]*/
for(i = 0; i < R; i++)
S[i][0] = M[i][0];

/* Set first row of S[][]*/
for(j = 0; j < C; j++)
S[0][j] = M[0][j];

/* Construct other entries of S[][]*/
for(i = 1; i < R; i++)
{
for(j = 1; j < C; j++)
{
if(M[i][j] == 1)
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1;
else
S[i][j] = 0;
}
}

/* Find the maximum entry, and indexes of maximum entry
in S[][] */
max_of_s = S[0][0]; max_i = 0; max_j = 0;
for(i = 0; i < R; i++)
{
for(j = 0; j < C; j++)
{
if(max_of_s < S[i][j])
{
max_of_s = S[i][j];
max_i = i;
max_j = j;
}
}
}

printf("\n Maximum size sub-matrix is: \n");
for(i = max_i; i > max_i - max_of_s; i--)
{
for(j = max_j; j > max_j - max_of_s; j--)
{
printf("%d ", M[i][j]);
}
printf("\n");
}
}



/* Driver function to test above functions */
int main()
{
bool M[R][C] = {{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1},
{0, 0, 0, 0, 0}};

printMaxSubSquare(M);
getchar();
}

Run Here https://ideone.com/oFXO6

WAP for Given a binary tree, write a program to find the cousin nodes of the given node.

//find the level and print the cousins
#include
#include

using namespace std;

struct node{
struct node* left;
struct node* right;
int data;
};

void inorder(struct node* root,int present_level,int level,struct node* parent)
{
if(root!=NULL)
{
if(parent!=root)
inorder(root->left,present_level+1,level,parent);
if(level==present_level)
cout<data<<" ";
if(parent!=root)
inorder(root->right,present_level+1,level,parent);
}

}

void make_tree(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=new node;
(*root)->left=NULL;
(*root)->right=NULL;
(*root)->data=data;
return;
}
else
{
if(((*root)->data)make_tree(&((*root)->right),data);
else
make_tree(&((*root)->left),data);
}


}

struct node* find_level_and_parent(struct node* root,int data,int* level)
{
struct node* parent=NULL;
struct node* child=root;

while(1)
{

if(child==NULL)
return NULL;
if(child->data==data)
{
return parent;

}
if(data>child->data)
{
parent=child;
child=child->right;
*level=*level+1;

}
else if(data<=child->data)
{
parent=child;
child=child->left;
*level=*level+1;
}


}

}

int main()
{
struct node* root=NULL;
make_tree(&root,6);
make_tree(&root,8);
make_tree(&root,3);
make_tree(&root,4);
make_tree(&root,44);
make_tree(&root,34);
make_tree(&root,12);
make_tree(&root,8);
make_tree(&root,2);
make_tree(&root,1);
make_tree(&root,33);

int level=0;
struct node* temp=find_level_and_parent(root,12,&level);
if(temp!=NULL)
{
cout<<"Level="<return 0;
}

Solution Provide By Ankit From CareerCup
Run Here https://ideone.com/ybavU

WAP to Populate The next Higher in Singly Linked List

struct node
{
int data;
struct node *next;
struct node *next_larger;
}

initially next_larger of every node is point to NULL.
now write a c code which set all node's next_larger pointer.
where next_largest point to the next larger then its own value and largest value node's next_larger pointer points to NULL

i.e.
if LL is 3->1->5->6->4
then 3's next_larger points to 4
and 1's next_larger points to 3
and 5's next_larger points to 6
and 6's next_larger points to NULL
and 4's next_larger points to 5

#include
#include


struct node
{

int data;
struct node *next;
struct node *next_higher;

};

struct node* setNextHigher(struct node** head)
{
if(head==NULL)
return NULL;

struct node *start=*head;

(*head)=(*head)->next;

while((*head))
{

if((*head)->datadata)
{

(*head)->next_higher=start;
start= (*head);

}
else
{
struct node *p=start;
while(p->next_higher&&(*head)->data>=p->next_higher->data)
p=p->next_higher;

(*head)->next_higher=p->next_higher;
p->next_higher=(*head);

}
(*head)= (*head)->next;
}

return start;
}

void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print linked list */
void printList(struct node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next_higher;
}
}

int main()
{
/* Start with the empty list */
struct node* head = NULL;

push(&head, 4);
push(&head, 6);
push(&head, 5);
push(&head, 1);
push(&head, 3);

head=setNextHigher(&head);

printList(head);

getchar();
}


Run Here https://ideone.com/fARV8

WAP to Solve Robot In The Maze

Pretend there is a robot that has to navigate a maze (N x M). The robot can only move down or right and the maze can contain walls. Write an algorithm to determine the number of paths the robot can take.

1st Approach No of Paths

(For clarity, we will solve this part assuming an X*Y Matrix)
Each path has (X-1)+(Y-1) steps. Imagine the following paths:

X X Y Y X (move right -> right -> down -> down -> right)
X Y X Y X (move right -> down -> right -> down -> right)
...& so on

Each path can be fully represented by the moves at which we move
right. That is, if I were to ask you which path you took, you could
simply say “I moved right on step 3 and 4.”
Since you must always move right X-1 times, and you have X-1 + Y-1
total steps, you have to pick X-1 times to move right out of X-1+Y-1
choices. Thus, there are C(X-1, X-1+Y-1) paths (e.g., X-1+Y-1 choose
X-1):

(X-1 + Y-1)! / ((X-1)! * (Y-1)!)..Hope This Equation Clear to Every1

which is nothing but C(2n-2,n-1) Catalan Number

2nd Approach

DP(Always Best)

A robot can take path (N,M) from either (N-1,M) or (N,M-1)
if N and M is 0, its the beginning so return 0.
if N or M is 0, we can get there in 1 path.

We call paths(N,M) with s[][] initialized to -1.

int paths(int i,int j)
{
if(!(i||j)) //means we either can go down or right path as only 1 is
zero
return 1;

if((i&&j))/// no path exist if both are zero
return 0;

if(s[i][j] != -1)
return s[i][j];

s[i][j] = paths(i-1,j) + paths(i,j-1);

return s[i][j];

}

Running C++ Code


#include
void PrintRobotPaths(std::string path, int row, int column, int totrows, int totcols)
{
if(column == totcols && row == totrows)
{
std::cout << path << std::endl;
return;
}
if(row == totrows)
{
std::string pc = path + " D";
PrintRobotPaths(pc, row, column+1, totrows, totcols);
return;
}
if(column == totcols)
{
std::string pr = path + " R";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
return;
}
std::string pr = path + " R";
std::string pc = path + " D";
PrintRobotPaths(pr, row+1, column, totrows, totcols);
PrintRobotPaths(pc, row, column+1, totrows, totcols);
}



int main(int argc, char** argv)
{
int row=4;
int column=4;
std::string path;
PrintRobotPaths(path,1, 1, row, column);
return 0;
}


Run Here https://ideone.com/qq7dh

Iterative Solution of Binary Tree Traversal Inorder,Preorder,PostOrder

Most problems involving binary trees can be solved by using recursion. Recursion is inherent to trees. But, keep in mind that recursion has a memory overhead because of the additional stack space required for the recursive method calls. Sometime interviewers will ask to solve problems related to trees without using recursion. This can sometimes make the problem challenging. In this problem, even though we will not use recursion explicitly, we will use the Stack data structure that emulates what recursion does.


Inorder


Algo


1) Create an empty stack S.
2) Initialize current node as root
3) Push the current node to S and set current = current->left until current is NULL
4) If current is NULL and stack is not empty then
a) Pop the top item from stack.
b) Print the popped item, set current = current->right
c) Go to step 3.
5) If current is NULL and stack is empty then we are done.



#include
#include
#define bool int

/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for inorder tree traversal */
void inOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current = root;
struct sNode *s = NULL; /* Initialize stack s */
bool done = 0;

while (!done)
{
/* Reach the left most tNode of the current tNode */
if(current != NULL)
{
/* place pointer to a tree node on the stack before traversing
the node's left subtree */
push(&s, current);
current = current->left;
}

/* backtrack from the empty subtree and visit the tNode
at the top of the stack; however, if the stack is empty,
you are done */
else
{
if (!isEmpty(s))
{
current = pop(&s);
printf("%d ", current->data);

/* we have visited the node and its left subtree.
Now, it's right subtree's turn */
current = current->right;
}
else
done = 1;
}
} /* end of while */
}

/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref);

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}

/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;

return(tNode);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);

inOrder(root);

getchar();
return 0;
}

Run Here https://ideone.com/bgss3

Preorder Traversal


Algo

/**
non-recursive version of Pre-order traversal
void PreOrderNonRecur(NODE *root)
Algorithm:
create a stack
PUSH the root node of the tree into the stack
While the stack is not empty
POP a node
If the node is not NULL
Print the value of the node
PUSH the node's right child into the stack
PUSH the node's left child into the stack
*/

#include
#include
#define bool int

/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for preorder tree traversal */
void postOrder(struct tNode *root)
{
/* set current to root of binary tree */
struct tNode *current=root;
struct sNode *s = NULL; /* Initialize stack s */


push(&s,current);

while(!isEmpty(s))
{
current=pop(&s);
printf(" %d ", current->data);
push(&s,current->right);
push(&s,current->left);

}

}

/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref);

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}

/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;

return(tNode);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);


postOrder(root);

getchar();
return 0;
}

run here https://ideone.com/YUPvS

PostOrder Traversal

Algo use Tow Stack child & Parent

* Push the root node to the child stack.
* while child stack is not empty
* Pop a node from the child stack, and push it to the parent stack.
* Push its left child followed by its right child to the child stack.
* end while
* Now the parent stack would have all the nodes ready to be traversed in post-order. Pop off the nodes from the parent stack one by one and you will have the post order traversal of the tree.


#include
#include
#define bool int

/* A binary tree tNode has data, pointer to left child
and a pointer to right child */
struct tNode
{
int data;
struct tNode* left;
struct tNode* right;
};

/* Structure of a stack node. Linked List implementation is used for
stack. A stack node contains a pointer to tree node and a pointer to
next stack node */
struct sNode
{
struct tNode *t;
struct sNode *next;
};

/* Stack related functions */
void push(struct sNode** top_ref, struct tNode *t);
struct tNode *pop(struct sNode** top_ref);
bool isEmpty(struct sNode *top);

/* Iterative function for postorder tree traversal */
void postOrder(struct tNode *root)
{
if(!root)
return;

/* set current to root of binary tree */

struct sNode *child,*parent = NULL; /* Initialize stack s */

push(&child,root);
while(!isEmpty(child))
{
struct tNode *current =pop(&child);
push(&parent,current);

if(current->left)
push(&child,current->left);
if(current->right)
push(&child,current->right);

}
while(!isEmpty(parent))
{
struct tNode *current= pop(&parent);
printf(" %d ",current->data);
}

}

/* UTILITY FUNCTIONS */
/* Function to push an item to sNode*/
void push(struct sNode** top_ref, struct tNode *t)
{
/* allocate tNode */
struct sNode* new_tNode =
(struct sNode*) malloc(sizeof(struct sNode));

if(new_tNode == NULL)
{
printf("Stack Overflow \n");
getchar();
exit(0);
}

/* put in the data */
new_tNode->t = t;

/* link the old list off the new tNode */
new_tNode->next = (*top_ref);

/* move the head to point to the new tNode */
(*top_ref) = new_tNode;
}

/* The function returns true if stack is empty, otherwise false */
bool isEmpty(struct sNode *top)
{
return (top == NULL)? 1 : 0;
}

/* Function to pop an item from stack*/
struct tNode *pop(struct sNode** top_ref)
{
struct tNode *res;
struct sNode *top;

/*If sNode is empty then error */
if(isEmpty(*top_ref))
{
printf("Stack Underflow \n");
getchar();
exit(0);
}
else
{
top = *top_ref;
res = top->t;
*top_ref = top->next;
free(top);
return res;
}
}

/* Helper function that allocates a new tNode with the
given data and NULL left and right pointers. */
struct tNode* newtNode(int data)
{
struct tNode* tNode = (struct tNode*)
malloc(sizeof(struct tNode));
tNode->data = data;
tNode->left = NULL;
tNode->right = NULL;

return(tNode);
}

/* Driver program to test above functions*/
int main()
{

/* Constructed binary tree is
1
/ \
2 3
/ \
4 5
*/
struct tNode *root = newtNode(1);
root->left = newtNode(2);
root->right = newtNode(3);
root->left->left = newtNode(4);
root->left->right = newtNode(5);
root->right->left = newtNode(6);
root->right->right = newtNode(7);
postOrder(root);

getchar();
return 0;
}


Run here https://ideone.com/uFq33

Excellent Explanation of Postorder Using Single Stack

http://www.ihas1337code.com/2010/10/binary-tree-post-order-traversal.html

8 FAQ Sorting Algorithms Bubble,Insertion,Selection,Pancake,Quick,Merge,Heap & Tree Sorting

1st program Contains Bubble,Insertion,Selection,Pancake Sorting

#include

/* Function to reverse arr[] from start to end*/
void rvereseArray(int arr[], int start, int end)
{

int temp;
while(start < end)
{
temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}

/* Utility that prints out an array on a line */
void printArray(int arr[], int size)
{
int i;
for (i=0; i < size; i++)
printf("%d ", arr[i]);

printf("\n");
}

int get(int ar[],int i)
{

return ar[i];

}

int length(int ar[])
{
return (sizeof(ar)/sizeof(int));
}


void pancake_sort(int arr[],int n)
{
int i,j;

for( i = 1; i < n; i++ )
{
int index = i;
for( j = i-1; j >= 0; j-- )
{
if( arr[j] > arr[index] )
{
rvereseArray(arr, j, index);
index = j;
}
}
}

}

void swap(int a[],int i,int j)
{
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;

}
void select_sort(int a[],int n)
{
/* a[0] to a[n-1] is the array to sort */
int iPos;
int iMin,i;

/* advance the position through the entire array */
/* (could do iPos < n-1 because single element is also min element) */
for (iPos = 0; iPos < n; iPos++)
{
/* find the min element in the unsorted a[iPos .. n-1] */

/* assume the min is the first element */
iMin = iPos;
/* test against all other elements */
for (i = iPos+1; i < n; i++)
{
/* if this element is less, then it is the new minimum */
if (a[i] < a[iMin])
{
/* found new minimum; remember its index */
iMin = i;
}
}

/* iMin is the index of the minimum element. Swap it with the current position */
if ( iMin != iPos )
{
swap(a, iPos, iMin);
}
}


}
void insert_sort(int A[],int n)
{
int i,j,key;

for(j=1;j {
key=A[j];
//> A[ j ] is added in the sorted sequence A[0, .. j-1]
i=j-1;
while(i >= 0 && A [i] > key)
{ A[i+1] =A[i];
i=i-1;
}
A [i+1]=key;
}

}

void bubble_sort(int arr[],int n)//optmized see loop
{
int temp,i,j,k;

for(i=0;i{
for(j=n-1;j>i;j--)
{
if(arr[j-1] >arr[j])
{
temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
for(k=0;k{
printf(" %d \t",arr[k]);
}

printf( " \n " );

}

}



int main()
{
int arb[]={5,2,1,4,3};
int n=5;
int i=0;

bubble_sort(arb,n);

printf("\n\n-- Bubble Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",arb[i]);
}

int ari[]={5,2,1,4,3};

insert_sort(ari,n);

printf("\n\n-- Insertion Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",ari[i]);
}

int ars[]={5,2,1,4,3};

select_sort(ars,n);

printf("\n\n-- Selection Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",ars[i]);
}


int arp[]={5,2,1,4,3};

pancake_sort(arp,n);

printf("\n\n-- Pancake Sorted Series --");
for(i=0;i{
printf("\n \n \t %d",arp[i]);
}


}


Time Complexity O(n^2)
Space Complexity O(1)
Run Here https://ideone.com/clone/5Htf9


2nd program heap Sort 

How heap can be build in O(n)  check this out http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf

#include
#include
using namespace std;

void swap(int *x, int *y) {
int temp = *x;
*x = *y;
*y = temp;
}

class Heap
{
int *arr; // pointer to array of elements in heap
int heap_size;
public:
Heap(int a[], int size);
void buildminHeap();
void minHeapify(int );
void heapSort();
int getRoot() {return arr[0];}
int parent(int i){ return (i-1)/2; } ;
int left(int i) { return (2*i + 1); } ;
int right(int i) { return (2*i + 2); } ;
};

Heap::Heap(int a[], int size) {
heap_size = size;
arr = a;
}



void Heap::minHeapify(int i) {
int l = left(i);
int r = right(i);

printf( "l=%d,r=%d \n ",l,r);

int largest;
if (l < heap_size && arr[l] < arr[i])
largest = l;
else
largest = i;
if (r < heap_size && arr[r] < arr[largest])
largest = r;
if (largest != i)
{
swap(&arr[i], &arr[largest]);
printf(" a[i]=%d \t a[large]=%d", arr[i],arr[largest]);
minHeapify(largest);
}
}

void Heap::buildminHeap() {
int i = (heap_size - 1)/2;
printf( " %d ",i);
while (i >= 0)
{
minHeapify(i);
i--;
}
}
void heapsort(int a[],int n)
{
Heap hp(a, n);
hp.buildminHeap();
int i=0,temp=0;
for (i = n-1; i >= 1; i--)
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
hp.minHeapify(0);
}

}
int main()
{
int k = 4;
int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);

heapsort(arr,n);

int i=0;
for(i=0;i printf( " %d ",arr[i]);

getchar();
return 0;
}


Time Complexity O(nlogn)
Space Complexity O(1)
Run here https://ideone.com/tP2z3

3rd program Merge Sort

#include

void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}

while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}

for (i=0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}

void m_sort(int numbers[], int temp[], int left, int right)
{
int mid;

if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);
}
}


void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);
}



int main()
{

int arr[] = {12, 34, 10, 8, 9, 4, 56};
int n = sizeof(arr)/sizeof(arr[0]);
int temp[7];

mergeSort(arr,temp,n);

int i=0;
for(i=0;i printf( " %d ",arr[i]);

getchar();
return 0;
}


Time Complexity O(nlogn)
Space Complexity O(n)
Run here https://ideone.com/ZQImg

4th program Quick Sort

#include "stdio.h"

int split ( int*, int, int ) ;

int main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;

void quicksort ( int *, int, int ) ;

quicksort ( arr, 0, 9 ) ;

printf ( "\nArray after sorting:\n") ;

for ( i = 0 ; i <= 9 ; i++ )
printf ( "%d\t", arr[i] ) ;

}

void quicksort ( int a[ ], int lower, int upper )
{
int i ;
if ( upper > lower )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1 ) ;
quicksort ( a, i + 1, upper ) ;
}
}

int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;

p = lower + 1 ;
q = upper ;
i = a[lower] ;

while ( q >= p )
{
while ( a[p] < i )
p++ ;

while ( a[q] > i )
q-- ;

if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}

t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;

return q ;
}


Time Complexity O(nlogn)
Space Complexity O(logn) if stack space considered else O(1)
Run Here https://ideone.com/clone/YFFWE

5th program BST Sort


#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node
with the given data and NULL left and right
pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

/* Give a binary search tree and a number,
inserts a new node with the given number in
the correct place in the tree. Returns the new
root pointer which the caller should then use
(the standard trick to avoid using reference
parameters). */
struct node* insert(struct node* node, int data)
{
/* 1. If the tree is empty, return a new,
single node */
if (node == NULL)
return(newNode(data));
else
{
/* 2. Otherwise, recur down the tree */
if (data <= node->data)
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);

/* return the (unchanged) node pointer */
return node;
}
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(struct node* node)
{
if (node == NULL)
return;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf("%d ", node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Driver program to test sameTree function*/
int main()
{
struct node* root = NULL;
root = insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 3);
insert(root, 6);
insert(root, 5);

printInorder(root);

getchar();
return 0;
}

Time Complexity O(nlogn)
Space Complexity O(1)
Run here https://ideone.com/tP2z3

8 FAQ Sorting Algorithms Bubble,Insertion,Selction,Pancake,Quick,Merge,Heap,Tree Sorting

WAP to Implement The Counting Sort Pure O(n)

#include
#include

void counting_sort(int array[], int size)
{
int i, min, max;

min = max = array[0];
for(i = 1; i < size; i++)
{
if (array[i] < min)
min = array[i];
else if (array[i] > max)
max = array[i];
}

int range = max - min + 1;
int *count =(int*)malloc(range * sizeof(int));

for(i = 0; i < range; i++)
count[i] = 0;

for(i = 0; i < size; i++)
count[ array[i] - min ]++;
int j, z = 0;
for(i = min; i <= max; i++)
for(j = 0; j < count[ i - min ]; j++)
array[z++] = i;

free(count);
}

/* Explaination
// CountingSort.
//
// The data to be sorted is in array A with
// subscripts 0..n-1. For example,
//
// subscript: 0 1 2 3 4 5 6 7 8
// A = [ 2, 0, 4, 1, 4, 2, 2, 1, 0 ]
//
// The data values range from 0 to MAX (=4).
// A second array B will hold the sorted data.
//
// Initialize a "counting array" C:
// ---------------------------------------------

for (i = 0; i <= MAX; i++)
C[i] = 0;

// ---------------------------------------------
// Count how often each value occurs in A:
// ---------------------------------------------

for (i = 0; i < n; i++)
C[A[i]]++;

// ---------------------------------------------
// At this point C[i] contains the number
// of occurrences of the value i in A. In
// the example:
//
// 0 1 2 3 4
// C = [ 2, 2, 3, 0, 2 ]
//
// Make C[i] contain the number of
// occurrences of values 0..i in A:
// ---------------------------------------------

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

// ---------------------------------------------
// In the example:
//
// 0 1 2 3 4
// C = [ 2, 4, 7, 7, 9 ]
//
// Note that now C[i] is such that in the sorted
// array, the last occurrence of value i will be
// just before position C[i] (e.g., the last 2 in
// the sorted array B will be just before position
// C[2]=7).
//
// Move values from A to B, using C to know
// where to put them:
// ---------------------------------------------

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

// ---------------------------------------------
// Now B looks like
//
// 0 1 2 3 4 5 6 7 8
// B = [ 0, 0, 1, 1, 2, 2, 2, 4, 4 ]
//
// Not that it matters, but now C[i] contains the
// subscript of the first occurrence of value i
// in the sorted array B:
//
// 0 1 2 3 4
// C = [ 0, 2, 4, 7, 7 ]
//
*/
void counting_sort_n(int A[],int n)
{

int i, min, MAX;

min = MAX= A[0];
for(i = 1; i < n; i++)
{
if (A[i] < min)
min = A[i];
else if (A[i] > MAX)
MAX= A[i];
}

int range = MAX- min + 1;
int *C =(int*)malloc(range * sizeof(int));
int *B=(int*)malloc(range * sizeof(int));
for (i = 0; i <= MAX; i++)
C[i] = 0;

for (i = 0; i < n; i++)
C[A[i]]++;

for (i = 1; i <= MAX; i++)
C[i] += C[i-1];

for (i = n-1; i >= 0; i--)
B[--C[A[i]]] = A[i];

for(i=0;i<9;i++)
printf( "%d ", B[i]);

}
int main()
{
int a[]={5,1,2,4,3};

//1st Method
counting_sort(a,5);

int i=0;
printf( "\n");
for(i=0;i<5;i++)
printf( "%d ", a[i]);

//2nd Method

int b[]={ 2, 0, 4, 1, 4, 2, 2, 1, 0};
counting_sort_n(b,9);



return 0;

}

Run here https://ideone.com/kLlEa

WAP Create a singly linked list of Leaf nodes from a binary tree

include

struct node
{
struct node *left, *right;
int data;

};


void LeafLinked(struct node *t, struct node **prevLeaf, struct node **head)
{
if(t)
{

if(t->left == NULL && t->right == NULL)
{ //leaf

if(*head == NULL)
*head = t;

else if(*prevLeaf)
(*prevLeaf)->next = t;

*prevLeaf = t;
}
else { //at least one child
LeafLinked(t->left, prevLeaf, head);
LeafLinked(t->right, prevLeaf, head);
}
}
}


/*Utilities*/

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

inline void printList(struct node *t)
{
while(t)
{
printf("%d ", t->data);
t = t->next;
}
printf("\n");
}

int main()
{
/*level 0*/
struct node *t = newNode(10);

/*level 1*/
t->left = newNode(20);
t->right = newNode(30);


/*level 2*/
t->left->left = newNode(40);
t->left->right = newNode(70);
t->right->left = newNode(50);
t->right->right = newNode(60);

/*level 3*/
t->left->left->left = newNode(70);
t->right->right->left = newNode(60);
t->right->right->right = newNode(160);

/*Empty List head*/
struct node *head = NULL, *prevLeaf = NULL;

/*Convert tree to list*/
LeafLinked(t, &prevLeaf, &head);

/*print list*/
printList(head);


return 0;
}

Rune Here https://ideone.com/UOakN