Random Quote
Random Quotes
Categories
- A ll Codes (310)
- ACM (221)
- ACM Technique (18)
- ACM-ICPC (57)
- Adhoc/Brute Force (3)
- Algorithm (83)
- Algo Unsolved (3)
- Asymptotic Notation (3)
- Geometry (2)
- Graph (6)
- All Pair Shortest Path (1)
- BFS (1)
- DFS (1)
- Single Source Shortest Path (2)
- Bellman Ford (1)
- Dijkstra (1)
- Topological Sort (1)
- Number Theory (6)
- Euler GCD (1)
- GCD (1)
- LCM (1)
- Prime factorization (1)
- Sieve of Erastosthenes (1)
- Trial Division (1)
- Recursion (3)
- Fibonacci (1)
- Tower of Hanoi (1)
- Searching (3)
- Binary Search (2)
- Linear Search (1)
- Sorting (13)
- Bubble Sort (1)
- Bucket Sort (1)
- Counting Sort (1)
- Heap Sort (1)
- Insertion Sort (1)
- Merge Sort (3)
- Quicksort (2)
- Radix Sort (1)
- Selection Sort (3)
- Tree (6)
- AVL Tree (1)
- B+ Tree (1)
- Binary Search Tree (4)
- Competitive Programming (1)
- Data Structure (6)
- Linked List (1)
- Queue (2)
- Circular Queue (1)
- Stack (1)
- Future Reference (1)
- Problem Solution (101)
- Codeforces (3)
- DevSkill (1)
- HackerEarth (17)
- HackerRank (4)
- Lightoj (2)
- SPOJ (1)
- Unsolved (1)
- URI Online Judge (34)
- UVa (18)
- Programming Contest (2)
- Programming Problem Solving (18)
- CS Courses (141)
- Art of Effective Living (1)
- Artificial Intelligence (12)
- Assembly Language (3)
- Compiler Design (1)
- Computer Architecture (3)
- Data Communication (1)
- Data Mining (10)
- WEKA (2)
- Database (10)
- SQL (8)
- Digital Image Processing (5)
- Embedded Systems (2)
- Arduino (2)
- Games Development (1)
- Graphics (9)
- OpenGL (7)
- Mathematics (25)
- Numerical Method (18)
- Bisection Method (4)
- Numerical Method (18)
- Microprocessor (1)
- OOP (44)
- Operating System (11)
- Bash/Shell Scripting (7)
- CPU Scheduling (1)
- Simulation and Modelling (1)
- Web Engineering (1)
- Experience (3)
- Events (1)
- Food Review (1)
- Travel (1)
- Fitness (15)
- Body Transformation (2)
- Bodybuilding (7)
- Cycling (2)
- Fat Loss (2)
- Fitness Motivation (5)
- Health (2)
- Mental Health (1)
- My Gym (2)
- My Life Chart (3)
- My Life Style (3)
- Weight loss (1)
- Graphics Design (1)
- Photoshop (1)
- HigherStudy (72)
- EducationUSA (2)
- English Learning (9)
- Pronunciation (3)
- German Learning (18)
- Germany (2)
- Grammar (7)
- GRE (17)
- IELTS (26)
- Handwriting Improvement (1)
- Listening (4)
- Reading (1)
- Speaking (2)
- Writing Task (3)
- TOEFL (2)
- HTML/CSS (1)
- Job (43)
- CSE (2)
- CV/Resume (4)
- Interview (22)
- Fresher/Intern (1)
- Java (5)
- Masters of Science (1)
- Introductory Data Analysis(IDA) (1)
- Excel (1)
- Introductory Data Analysis(IDA) (1)
- MSSQL (3)
- Stored Procedures (1)
- T-SQL (1)
- Open Source (6)
- Linux (4)
- Ubuntu 15.04 (1)
- Ubuntu 18.04 (1)
- Ubuntu14.04 (1)
- Ubuntu (2)
- Linux (4)
- Philosophy of Life (163)
- Learning (1)
- Life (9)
- Life Motivation (122)
- Business/Money (5)
- Career/Earning (10)
- Depression (3)
- Fearless Motivation (1)
- Life Quotes (2)
- Life Story/Journey (1)
- Passion (1)
- People Skill/Networking (14)
- Stress (2)
- Study Motivation (57)
- Success Hacks (73)
- Healthy Habit (15)
- Never Quit (35)
- Patience (22)
- Social Skills/Communicative Skills (5)
- Time Management (4)
- Life Productivity (10)
- Life Rules (3)
- Life Skills (3)
- Lifefact (3)
- Lifelessons (6)
- Lifestyle (1)
- Love (8)
- Motivation (16)
- Motivational Posts (5)
- Music (4)
- Poems (1)
- Love (1)
- Poetry (1)
- Ramadan (1)
- Romance (4)
- Sadness (2)
- Sarcasm (2)
- Thoughts (2)
- Pore Abar Bujhbo (8)
- Presentation (8)
- Programming (316)
- Language (288)
- C (152)
- Array (24)
- C library function (3)
- C Refresh (106)
- Function (17)
- logic (1)
- Logic Logic (4)
- Logics (1)
- Memory Management (1)
- Pointer (19)
- String (21)
- Structured Programming (1)
- C# (40)
- C++ (35)
- Vector (1)
- Java (44)
- Javascript (1)
- PHP (18)
- Python (13)
- C (152)
- Language (288)
- Project (2)
- Project Report (1)
- Research (49)
- BigData (3)
- Data Science (14)
- Machine Learning (23)
- Natural Language Processing(NLP) (5)
- Plagiarism Checker (1)
- Research Papers (3)
- Research Topic (1)
- Statistics (3)
- Sentiment Analysis (3)
- Software Development (80)
- .NET (34)
- Xamarin (1)
- Android (10)
- ASP.NET (10)
- Debate (2)
- Design Pattern (3)
- Laravel (4)
- Object Notation (3)
- Regex (2)
- Software Development Life Cycle(SDLC) (4)
- Training (9)
- LICT (9)
- unity3d (1)
- Version Control/SVN (4)
- XML (1)
- .NET (34)
- Tech Tips (21)
- Desktop (1)
- Fix (1)
- Laptop (1)
- Laptop(ল্যাপটপ) (1)
- HP (1)
- Techie Talk (15)
- Tech Debate (2)
- VPS (2)
- Uncategorized (35)
- University Life (4)
- 11th semester (1)
- 7th semester (1)
- 9th semester (1)
- Web Links (1)
- বাংলা (10)
- অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং (1)
- রিসার্চ (1)
- সি প্রোগ্রামিং (2)
- হার্ডডিস্ক পার্টিশান (1)
-
Recent Comments
- ijazbesant on Become a Software Engineer in PHP platform
- zakilive on OOPs ! অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং কনসেপ্ট এবং তার সূচনা :D
- Hasibul Hasan on OOPs ! অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং কনসেপ্ট এবং তার সূচনা :D
- Rezaul Islam on Some Android Links that May Help
- chris woodward on Project UX design for Java Balloon Shooter Game in 4th semester
Category Archives: Algorithm
Bellman Ford
It works on negative cycle.
Implemented Code:
Time Complexity:
O([E].[V])
Reference:
http://cyberlingo.blogspot.com/2015/07/bellman-ford-algorithm.html
Posted in Algo Unsolved, Bellman Ford, Single Source Shortest Path
Tagged not greedy
Dijkstra
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<bits/stdc++.h> using namespace std; int main(){ int cost[10][10],path[10][10],i,j,n,p,v,min,index=1; int distance[10],row,column; cout<<"Enter no. of nodes: "; cin>>n; cout<<"Enter cost matrix: \n"; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cin>>cost[i][j]; } } printf("Enter the node you want to visit:"); cin>>v; printf("Enter the path for the selected node:"); cin>>p; cout<<"Enter the path matrix: \n"; for(i=1;i<=p;i++) { for(j=1;j<=n;j++) { cin>>path[i][j]; } } for(i=1;i<=p;i++){ distance[i]=0; row=1; for(j=1;j<=n;j++) { if(row!=v) { column=path[i][j+1]; distance[i]=distance[i]+cost[row][column]; } row=column; } } min=distance[1]; for(i=1;i<=p;i++) { if(distance[i]<=min) { min=distance[i]; index=i; } } cout<<"The minimum distance is:"; cout<<min; for(i=1;i<=n;i++){ if(path[index][i]!=0) { printf("-->%d",path[index][i]); } } } |
output:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
Enter no. of nodes: 5 Enter cost matrix: 0 4 0 8 0 4 0 3 0 0 0 3 0 4 0 8 0 4 0 7 0 0 0 7 0 Enter the node you want to visit:5 Enter the path for the selected node:2 Enter the path matrix: 1 2 3 4 5 1 4 5 0 0 The minimum distance is:15-->1-->4-->5 |
Complexity:
O(E+V^2)
We are using here adjacency matrix list
Posted in Dijkstra, Graph, Single Source Shortest Path
Topological Sort
https://www.youtube.com/watch?v=Q9PIxaNGnig/
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
// A Java program to print topological sorting of a DAG import java.io.*; import java.util.*; // This class represents a directed graph using adjacency // list representation class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; // Adjacency List //Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } // Function to add an edge into the graph void addEdge(int v,int w) { adj[v].add(w); } // A recursive function used by topologicalSort void topologicalSortUtil(int v, boolean visited[], Stack stack) { // Mark the current node as visited. visited[v] = true; Integer i; // Recur for all the vertices adjacent to this // vertex Iterator<Integer> it = adj[v].iterator(); while (it.hasNext()) { i = it.next(); if (!visited[i]) topologicalSortUtil(i, visited, stack); } // Push current vertex to stack which stores result stack.push(new Integer(v)); } // The function to do Topological Sort. It uses // recursive topologicalSortUtil() void topologicalSort() { Stack stack = new Stack(); // Mark all the vertices as not visited boolean visited[] = new boolean[V]; for (int i = 0; i < V; i++) visited[i] = false; // Call the recursive helper function to store // Topological Sort starting from all vertices // one by one for (int i = 0; i < V; i++) if (visited[i] == false) topologicalSortUtil(i, visited, stack); // Print contents of stack while (stack.empty()==false) System.out.print(stack.pop() + " "); } // Driver method public static void main(String args[]) { // Create a graph given in the above diagram Graph g = new Graph(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); System.out.println("Following is a Topological " + "sort of the given graph"); g.topologicalSort(); } } |
Output:
1 2 |
Following is a Topological sort of the given graph 5 4 2 3 1 0 |
Time Complexity: O(V+E)
Space Complexity: O(V)
V for vertex E for edge
code courtesy:
I understood the theory but need to understand the code well later
Posted in Graph, Topological Sort
Bucket Sort
Pseudocode:
1 2 3 4 5 6 |
bucketSort(arr[], n) 1) Create n empty buckets (Or lists). 2) Do following for every array element arr[i]. .......a) Insert arr[i] into bucket[n*array[i]] 3) Sort individual buckets using insertion sort. 4) Concatenate all sorted buckets. |
Implemented Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<bits/stdc++.h> using namespace std; void bucketSort(float A[],int n){ //1. create an n empty buckets vector<float> b[n]; //2. Put array elements in different buckets for(int i=0;i<n;i++) { int bi=n*A[i]; //index in bucket b[bi].push_back(A[i]); } //3. Sort individual buckets for(int i=0;i<n;i++) { sort(b[i].begin(),b[i].end()); } //4. concatenate all bucket into an array int index=0; for(int i=0;i<n;i++) for(int j=0;j<b[i].size();j++) { A[index++]=b[i][j]; } { } } int main() { float arr[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68}; int n=sizeof(arr)/sizeof(arr[0]); bucketSort(arr,n); cout<<"Sorted array is\n"; for(int i=0;i<n;i++) { cout<<arr[i]<<" "; } return 0; } |
output:
1 2 |
Sorted array is 0.12 0.17 0.21 0.23 0.26 0.39 0.68 0.72 0.78 0.94 |
Tuts:
Reference:
CLRS: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/bucketSort.htm
Harumanchi Book implementation:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include <stdio.h> #include <stdlib.h> int max(int a[],int n) { int max=0,i; for(i=0; i<n; i++) { if(a[i]>max) { max=a[i]; } } return max; } void bucket_sort(int a[],int n) { int bucket=max(a,n); int b[bucket],i,k,j=-1; for(i=0; i<=bucket; i++) b[i]=0; for(i=0; i<n; i++) { b[a[i]]=b[a[i]]+1; } for(i=0; i<=bucket; i++) { for(k=b[i]; k>0; --k) { a[++j]=i; } } } int main() { int i; // scanf("%d",&n); int arr[]={78,17,39,26,72,94,21,12,23,68}; int n=sizeof(arr)/sizeof(arr[0]); bucket_sort(arr,n); for(i=0; i<n; i++) printf(" %d",arr[i]); return 0; } |
output:
1 |
12 17 21 23 26 39 68 72 78 94 |
Time and Space complexity: O(n)
Posted in Bucket Sort
Counting Sort
Algo:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
COUNTING-SORT(A,B,k) 1. let C[0..k] be a new array 2. for i = 0 to k 3. C[i] = 0 4. for j = 1 to A.length 5. C[A[j]] = C[A[j]] + 1 6. // C[i] now contains the number of elements equal to i . 7. for i = 1 to k 8. C[i] = C[i] + C[i - 1] 9. // C[i] now contains the number of elements less than or equal to i . 10.for j = A.length downto 1 11. B[C[A[j]]] = A[j] 12. C[A[j]] = C[A[j]] - 1 |
Implemented Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include<bits/stdc++.h> using namespace std; void countingSort(int a[],int k,int n) { int i,j; int b[15],c[100]; for(i=0;i<=k;i++) c[i]=0; for(j=1;j<=n;j++) c[a[j]]=c[a[j]]+1; for(i=1;i<=k;i++) c[i]=c[i]+c[i-1]; for(j=n;j>=1;j--) { b[c[a[j]]]=a[j]; c[a[j]]=c[a[j]]-1; } cout<<"Sorted Array is:"<<endl; for(i=1;i<=n;i++) { cout<<" "; cout<<b[i]; } } int main() { int i,k=9; //k means maximum value in an array int A[]={5,2,9,5,2,3,5}; int n=sizeof(A)/sizeof(A[0]); countingSort(A,k,n); return 0; } |
Reference:
http://scanftree.com/Data_Structure/Counting-sort
CLRS:
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/countingSort.htm
Tuts:
Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)
Posted in Counting Sort, Quicksort, Sorting
Binary Search Tree: Successor in Inorder Traversal
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
/* C++ program to find Inorder successor in a BST */ #include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node *left; struct Node *right; }; //Function to find some data in the tree Node* Find(Node*root, int data) { if(root == NULL) return NULL; else if(root->data == data) return root; else if(root->data < data) return Find(root->right,data); else return Find(root->left,data); } //Function to find Node with minimum value in a BST struct Node* FindMin(struct Node* root) { if(root == NULL) return NULL; while(root->left != NULL) root = root->left; return root; } //Function to find Inorder Successor in a BST struct Node* Getsuccessor(struct Node* root,int data) { // Search the Node - O(h) struct Node* current = Find(root,data); if(current == NULL) return NULL; if(current->right != NULL) { //Case 1: Node has right subtree return FindMin(current->right); // O(h) } else { //Case 2: No right subtree - O(h) struct Node* successor = NULL; struct Node* ancestor = root; while(ancestor != current) { if(current->data < ancestor->data) { successor = ancestor; // so far this is the deepest node for which current node is in left ancestor = ancestor->left; } else ancestor = ancestor->right; } return successor; } } //Function to visit nodes in Inorder void Inorder(Node *root) { if(root == NULL) return; Inorder(root->left); //Visit left subtree printf("%d ",root->data); //Print data Inorder(root->right); // Visit right subtree } // Function to Insert Node in a Binary Search Tree Node* Insert(Node *root,char data) { if(root == NULL) { root = new Node(); root->data = data; root->left = root->right = NULL; } else if(data <= root->data) root->left = Insert(root->left,data); else root->right = Insert(root->right,data); return root; } int main() { /*Code To Test the logic Creating an example tree 5 / \ 3 10 / \ \ 1 4 11 */ Node* root = NULL; root = Insert(root,5); root = Insert(root,10); root = Insert(root,3); root = Insert(root,4); root = Insert(root,1); root = Insert(root,11); //Print Nodes in Inorder cout<<"Inorder Traversal: "; Inorder(root); cout<<"\n"; // Find Inorder successor of some node. struct Node* successor = Getsuccessor(root,1); if(successor == NULL) cout<<"No successor Found\n"; else cout<<"Successor is "<<successor->data<<"\n"; } |
https://www.youtube.com/watch?v=5cPbNCrdotA
Posted in Binary Search Tree, Tree
Delete a node in Binary Search Tree
https://www.youtube.com/watch?v=gcULXE7ViZw
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include<bits/stdc++.h> using namespace std; struct Node{ int data; struct Node* left; struct Node* right; }; Node* FindMin(Node* root) { while(root->left!=NULL) root=root->left; return root; } //Function to search a delete value from tree struct Node* Delete(struct Node *root, int data) { if(root==NULL) return root; else if(data<root->data) root->left=Delete(root->left,data); else if(data>root->data) root->right=Delete(root->right,data); else{ //case 1: No child if(root->left==NULL && root->right==NULL) { delete root; root=NULL; } //case 2: one child else if(root->left==NULL) { struct Node* temp=root; root=root->right; delete temp; } else if(root->right==NULL) { struct Node* temp=root; root=root->left; delete temp; } //case 3: 2 children else{ struct Node * temp=FindMin(root->right); root->data=temp->data; root->right=Delete(root->right, temp->data); } } return root; } //function to visit nodes in inorder void Inorder(Node* root) { if(root==NULL) return; Inorder(root->left); //visit left subtree printf("%d ",root->data); //print data Inorder(root->right); //visit right subtree } Node* Insert(Node *root, char data) { if(root==NULL) { root=new Node(); root->data=data; root->left=root->right=NULL; } else if(data<=root->data) root->left=Insert(root->left,data); else root->right=Insert(root->right,data); return root; } int main() { Node *root=NULL; root=Insert(root,5); root=Insert(root,10); root=Insert(root,3); root=Insert(root,4); root=Insert(root,1); root=Insert(root,11); root=Delete(root,5); //Print Nodes in Inorder cout<<"Inorder: "; Inorder(root); cout<<"\n"; } |
Posted in Binary Search Tree, Tree
Traversal in Binary Search Tree
Height of a binary tree:
https://www.youtube.com/watch?v=_pnqMz5nrRs
Level Order BFS in Binary Search Tree:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#include<bits/stdc++.h> #include<queue> using namespace std; struct Node { char data; Node *left; Node *right; }; //Function to print nodes in a binary tree in level order void LevelOrder(Node *root) { if(root==NULL) return; queue<Node*> Q; Q.push(root); //while there is at least one discovered node while(!Q.empty()) { Node* current=Q.front(); Q.pop(); cout<<current->data<<" "; if(current->left!=NULL) Q.push(current->left); if(current->right!=NULL) Q.push(current->right); } } //Function to insert node in a binary search tree Node* Insert(Node *root, char data) { if(root==NULL) { root=new Node(); root->data=data; root->left=root->right=NULL; } else if(data<=root->data) root->left=Insert(root->left,data); else root->right=Insert(root->right,data); return root; } int main() { //creating an example tree Node *root=NULL; root=Insert(root,'M'); root=Insert(root,'B'); root=Insert(root,'Q'); root=Insert(root,'Z'); root=Insert(root,'A'); root=Insert(root,'C'); LevelOrder(root); } |
output:
1 |
M B Q A C Z |
https://www.youtube.com/watch?v=gm8DUJJhmY4&index=34&list=PL2_aWCzGMAwI3W_JlcBbtYTwiQSsOTa6P
DFS in Preorder, Inorder, Postorder:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include<bits/stdc++.h> #include<queue> using namespace std; struct Node { char data; Node *left; Node *right; }; //Function to print nodes in a binary tree in level order void Preorder(struct Node* root){ if(root==NULL) return; printf("%c ",root->data);//print data Preorder(root->left); //visit left subtree Preorder(root->right); //Visit right subtree } //function to visit nodes in Inorder void Inorder(Node* root) { if(root==NULL) return; Inorder(root->left); //Visit left subtree printf("%c ",root->data); //Print data Inorder(root->right); //Visit right subtree } void Postorder(Node* root) { if(root==NULL) return; Postorder(root->left); //visit left subtree Postorder(root->right); //visit right subtree printf("%c ",root->data); //print data } //Function to insert node in a binary search tree Node* Insert(Node *root, char data) { if(root==NULL) { root=new Node(); root->data=data; root->left=root->right=NULL; } else if(data<=root->data) root->left=Insert(root->left,data); else root->right=Insert(root->right,data); return root; } int main() { //creating an example tree Node *root=NULL; root=Insert(root,'M'); root=Insert(root,'B'); root=Insert(root,'Q'); root=Insert(root,'Z'); root=Insert(root,'A'); root=Insert(root,'C'); //Print nodes in preorder cout<<"Preorder: "; Preorder(root); cout<<endl; //Print nodes in in inorder cout<<"Inorder: "; Inorder(root); cout<<endl; //Print Nodes in postorder cout<<"Postorder: "; Postorder(root); cout<<endl; return 0; } |
output:
1 2 3 |
Preorder: M B A C Q Z Inorder: A B C M Q Z Postorder: A C B Z Q M |
Posted in Binary Search Tree, Tree
Binary Search Tree
youtube :
https://www.youtube.com/watch?v=COZK7NATh4k
code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include<iostream> using namespace std; //Definition of Node for Binary search tree struct BstNode { int data; BstNode* left; BstNode* right; }; //Function to create new Node in heap BstNode* GetNewNode(int data) { BstNode* newNode=new BstNode(); newNode->data=data; newNode->left=newNode->right=NULL; return newNode; } //To search an element in BST return true if element is found bool Search(BstNode* root, int data) { if(root==NULL) return false; else if(root->data==data) return true; else if(data<=root->data) return Search(root->left,data); else return Search(root->right,data); } //TO insert data in BST, return address of root node BstNode* Insert(BstNode* root, int data) { if(root==NULL) //empty tree { root=GetNewNode(data); } //if data to be inserted is lesser, insert it in left subtree else if(data<=root->data) { root->left=Insert(root->left,data); } //else, insert in right subtree else { root->right=Insert(root->right,data); } return root; } int main() { BstNode* root=NULL;//creating an empty tree /* Code to test the logic */ root=Insert(root,15); root=Insert(root,10); root=Insert(root,20); root=Insert(root,25); root=Insert(root,8); root=Insert(root,12); //asking user to enter a number int number; cout<<"Enter number to be searched:\n"; cin>>number; //If number is found, print "FOUND" if(Search(root,number)==true) cout<<"Found\n"; else cout<<"Not Found\n"; return 0; } |
Posted in Binary Search Tree, Tree
Heap Sort
Steps:
If we want to sort in ascending then we create a min heap
If we want to create in descending then we create in max heap
Once the heap is created we delete the root node from heap and put the last node in the root position and repeat the steps till we have covered all the elements.
For ascending order:
1. Build Heap
2. Transform the heap into min heap
3. Delete the root node
pseudocode:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
Heapsort(A as array) BuildHeap(A) for i = n to 1 swap(A[1], A[i]) n = n - 1 Heapify(A, 1) BuildHeap(A as array) n = elements_in(A) for i = floor(n/2) to 1 Heapify(A,i,n) Heapify(A as array, i as int, n as int) left = 2i right = 2i+1 if (left <= n) and (A[left] > A[i]) max = left else max = i if (right<=n) and (A[right] > A[max]) max = right if (max != i) swap(A[i], A[max]) Heapify(A, max) |
source:
http://www.algorithmist.com/index.php/Heap_sort
Implemented code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
//this is descending order max-heapify #include<bits/stdc++.h> using namespace std; //swapping numbers using call by reference int swaps(int *p,int *q) { int temp=*q; *q=*p; *p=temp; } //this max heapify ensure that child node is always smaller than the parent node MaxHeapify(int ary[],int n,int i){ int largest=i; int left=2*i+1; int right=2*i+2; if(left<n && ary[left]>ary[largest]) { largest=left; } if(right<n && ary[right]>ary[largest]) { largest=right; } if(largest!=i) { swaps(&ary[i],&ary[largest]); MaxHeapify(ary,n,largest); } } //building heap void BuildHeap(int ary[],int n) { int i; for(i=floor(n/2)-1;i>=0;i--){ MaxHeapify(ary,n,i); } } //heapSort function sorting the array void heapSort(int ary[],int n) { BuildHeap(ary,n); for(int i=n-1;i>0;i--){ swaps(&ary[0],&ary[i]); int heap_size=i; MaxHeapify(ary,heap_size,0); } } //utility function void printAry(int ary[],int n) { for(int i=0;i<n;i++) { cout<<ary[i]<<" "; } } //driver program int main(){ int ary[]={40,60,10,20,50,30}; int n=sizeof(ary)/sizeof(ary[0]); heapSort(ary,n); cout<<"Sorted array:"; printAry(ary,n); } |
output:
1 |
Sorted array:10 20 30 40 50 60 |
Took help from these two links:
http://www.codingeek.com/algorithms/heap-sort-algorithm-explanation-and-implementation/
http://www.geeksforgeeks.org/heap-sort/
Complexity Analysis:
Time Complexity for MaxHeapify: O(logn)
Complexity for BuildHeap: O(n)
Complexity of heapSort:
Worst, Avergae, Base case: O(n*logn)
It is inplace algorithm.
Space Complexity: O(1)