Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Articles by "Data structure"
Showing posts with label Data structure. Show all posts
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Divide and Conquer | Set 2 (Closest Pair of Points)
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q.
The Brute force solution is O(n^2), compute the distance between each pair and return the smallest. We can calculate the smallest distance in O(nLogn) time using Divide and Conquer strategy. In this post, an O(n x (Logn)^2) approach is discussed. We will be discussing an O(nLogn) approach in a separate post.
Algorithm
Following are the detailed steps of an O(n (Logn)^2) algorithm.
Input: An array of n points P[]
Output: The smallest distance between two points in the given array.
As a pre-processing step, input array is sorted according to x coordinates.
1) Find the middle point in the sorted array, we can take P[n/2] as middle point.
2) Divide the given array into two halves. The first subarray contains points from P[0] to P[n/2]. The second subarray contains points from P[n/2+1] to P[n-1].
3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.
4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in the pair is from left half and other is from right half. Consider the vertical line passing through passing through P[n/2] and find all points whose x coordinately is closer than d to the middle vertical line. Build an array strip[] of all such points.
5)Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by recursively sorting and merging.
6) Find the smallest distance in strip[]. This is tricky. From the first look, it seems to be an O(n^2) step, but it is actual O(n). It can be proved geometrically that for every point in the strip, we only need to check at most 7 points after it (note that strip is sorted according to Y coordinate). See this for more analysis.
7) Finally, return the minimum of d and distance calculated in above step (step 6)
Implementation
Time Complexity Let Time complexity of above algorithm be T(n). Let us assume that we use an O(nLogn) sorting algorithm. The above algorithm divides all points into two sets and recursively calls for two sets. After dividing, it finds the strip in O(n) time, sorts the strip in O(nLogn) time and finally finds the closest points in a strip in O(n) time. So T(n) can express as follows
2) The code finds the smallest distance. It can be easily modified to find the points with the smallest distance.
3) The code uses quick sort which can be O(n^2) in the worst case. To have the upper bound as O(n (Logn)^2), an O(nLogn) sorting algorithms like merge sort or heap sort can be used
We are given an array of n points in the plane, and the problem is to find out the closest pair of points in the array. This problem arises in a number of applications. For example, in air-traffic control, you may want to monitor planes that come too close together, since this may indicate a possible collision. Recall the following formula for distance between two points p and q.
The Brute force solution is O(n^2), compute the distance between each pair and return the smallest. We can calculate the smallest distance in O(nLogn) time using Divide and Conquer strategy. In this post, an O(n x (Logn)^2) approach is discussed. We will be discussing an O(nLogn) approach in a separate post.
Algorithm
Following are the detailed steps of an O(n (Logn)^2) algorithm.
Input: An array of n points P[]
Output: The smallest distance between two points in the given array.
As a pre-processing step, input array is sorted according to x coordinates.
1) Find the middle point in the sorted array, we can take P[n/2] as middle point.
2) Divide the given array into two halves. The first subarray contains points from P[0] to P[n/2]. The second subarray contains points from P[n/2+1] to P[n-1].
3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d.
4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in the pair is from left half and other is from right half. Consider the vertical line passing through passing through P[n/2] and find all points whose x coordinately is closer than d to the middle vertical line. Build an array strip[] of all such points.
5)Sort the array strip[] according to y coordinates. This step is O(nLogn). It can be optimized to O(n) by recursively sorting and merging.
6) Find the smallest distance in strip[]. This is tricky. From the first look, it seems to be an O(n^2) step, but it is actual O(n). It can be proved geometrically that for every point in the strip, we only need to check at most 7 points after it (note that strip is sorted according to Y coordinate). See this for more analysis.
7) Finally, return the minimum of d and distance calculated in above step (step 6)
Implementation
Following is C/C++ implementation of the above algorithm
// A divide and conquer program in C/C++ to find the smallest distance from a #include <stdio.h> #include <float.h> #include <stdlib.h> #include <math.h> // A structure to represent a Point in 2D plane struct Point { int x, y; }; /* Following two functions are needed for library function qsort().// Needed to sort array of points according to X coordinate int compareX(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->x - p2->x); } // Needed to sort array of points according to Y coordinate int compareY(const void* a, const void* b) { Point *p1 = (Point *)a, *p2 = (Point *)b; return (p1->y - p2->y); } // A utility function to find the distance between two points float dist(Point p1, Point p2) { return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +(p1.y - p2.y)*(p1.y - p2.y)); } // A Brute Force method to return the smallest distance between two points // in P[] of size n float bruteForce(Point P[], int n) { float min = FLT_MAX; for (int i = 0; i < n; ++i) for (int j = i+1; j < n; ++j) if (dist(P[i], P[j]) < min) min = dist(P[i], P[j]); return min; } // A utility function to find minimum of two float values float min(float x, float y) { return (x < y)? x : y; } // A utility function to find the distance beween the closest points of // strip of given size. All points in strip[] are sorted accordint to // y coordinate. They all have an upper bound on minimum distance as d. // Note that this method seems to be a O(n^2) method, but it's a O(n) // method as the inner loop runs at most 6 times float stripClosest(Point strip[], int size, float d) { float min = d; // Initialize the minimum distance as d qsort(strip, size, sizeof(Point), compareY); // Pick all points one by one and try the next points till the difference // between y coordinates is smaller than d.// This is a proven fact that this loop runs at most 6 times for (int i = 0; i < size; ++i) for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) if (dist(strip[i],strip[j]) < min) min = dist(strip[i], strip[j]); return min; } // A recursive function to find the smallest distance. The array P contains // all points sorted according to x coordinate float closestUtil(Point P[], int n) { // If there are 2 or 3 points, then use brute force if (n <= 3) return bruteForce(P, n); // Find the middle point int mid = n/2; Point midPoint = P[mid]; // Consider the vertical line passing through the middle point // calculate the smallest distance dl on left of middle point and // dr on right side float dl = closestUtil(P, mid); float dr = closestUtil(P + mid, n-mid); // Find the smaller of two distances float d = min(dl, dr); // Build an array strip[] that contains points close (closer than d) // to the line passing through the middle point Point strip[n]; int j = 0; for (int i = 0; i < n; i++) if (abs(P[i].x - midPoint.x) < d) strip[j] = P[i], j++; // Find the closest points in strip. Return the minimum of d and closest // distance is strip[] return min(d, stripClosest(strip, j, d) ) } // The main functin that finds the smallest distance // This method mainly uses closestUtil() float closest(Point P[], int n) { qsort(P, n, sizeof(Point), compareX); // Use recursive function closestUtil() to find the smallest distance return closestUtil(P, n); } // Driver program to test above functions int main() { Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; int n = sizeof(P) / sizeof(P[0]); printf("The smallest distance is %f ", closest(P, n)); return 0; }
Output:
The smallest distance is 1.414214Time Complexity Let Time complexity of above algorithm be T(n). Let us assume that we use an O(nLogn) sorting algorithm. The above algorithm divides all points into two sets and recursively calls for two sets. After dividing, it finds the strip in O(n) time, sorts the strip in O(nLogn) time and finally finds the closest points in a strip in O(n) time. So T(n) can express as follows
T(n) = 2T(n/2) + O(n) + O(nLogn) + O(n) T(n) = 2T(n/2) + O(nLogn) T(n) = T(n x Logn x Logn)
Notes
1) Time complexity can be improved to O(nLogn) by optimizing step 5 of the above algorithm. We will soon be discussing the optimized solution in a separate post.2) The code finds the smallest distance. It can be easily modified to find the points with the smallest distance.
3) The code uses quick sort which can be O(n^2) in the worst case. To have the upper bound as O(n (Logn)^2), an O(nLogn) sorting algorithms like merge sort or heap sort can be used
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Algorithms for Skew Heap Operations
Skew Heaps are a self-adjusting form of Leftist Heap. By unconditionally swapping all nodes in the right merge path Skew Heaps maintain a short right path from the root.The following operations can be executed on Skew Heaps:
- MakeHeap(Element e)
- FindMin(Heap h)
- DeleteMin(Heap h)
- Insert (Heap h, Element e)
- Union (Heap h1, Heap h2)
MakeHeap (Element e) return new Heap(e); FindMin(Heap h) if (h == null) return null; else return h.key DeleteMin(Heap h) Element e = h.key; h = Union (h.left, h.right); return e; Insert (Heap h, Element e) z = MakeHeap(e); h = Union (h, z); Union (Heap h1, heap h2) Heap dummy; if (h1 == null) return h2; else if (h2 == null) return h1; else { // Assure that the key of h1 is smallest if (h1.key > h2.key) { Node dummy = h1; h1 = h2; h2 = dummy; } } if (h1.right == null) // Hook h2 directly to h1 h1.right = h2; else // Union recursively h1.right = Union (h1.right, h2); // Swap children of h1 dummy = h1.right; h1.right = h1.left; h1.left = dummy; return h1;
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Basic Theory
Breadth – first searches are performed by exploring all nodes at a given depth before proceeding to the next level. This means that all immediate children of nodes are explored before any of the children’s children are considered. It has an obvious advantage of always finding a minimal path length solution when one exists. However, a great many nodes may need to be explored before a solution is found, especially if the tree is very full.
Algorithm
BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search.
Example
Consider a graph
Applying above algorithm, the BFS of the graph starting from node 1 is : 1, 2, 3, 4, 6, 7, 5
Source Code
The time complexity of the breadth-first search is O(bd). This can be seen by noting that all nodes up to the goal depth d are generated. Therefore, the number generated is b + b2 + . . . + bd which is O(bd). The space complexity is also O(bd) since all nodes at a given depth must be stored in order to generate the nodes at the next depth, that is, bd-1 nodes must be stored at depth d – 1 to generate nodes at depth d, which gives space complexity of O(bd).
Algorithm
BFS uses a queue structure to hold all generate but still unexplored nodes. The order in which nodes are placed on the queue for removal and exploration determines the type of search.
- The BFS algorithm proceeds as follows
- .Place the starting node is in the queue.
- If the queue is empty, return failure and stop.
- If the first element on the queue is a goal node g, return success and stop Otherwise,
- Remove and expand the first element from the queue and place all the children at the end of the queue in any order.
- Return to step 2.
Example
Consider a graph
 |
| Breadth First Search in C++ Algorithm |
Applying above algorithm, the BFS of the graph starting from node 1 is : 1, 2, 3, 4, 6, 7, 5
Source Code
#include <iostream> #include <ctime> using namespace std; struct node { int info; node *next; }; class Queue { private: node *front; node *rear; public: Queue(); ~Queue(); bool isEmpty(); void enqueue(int); int dequeue(); void display(); }; void Queue::display(){ node *p = new node; p = front; if(front == NULL){ cout<<"\nNothing to Display\n"; }else{ while(p!=NULL){ cout<<endl<<p->info; p = p->next; } } } Queue::Queue() { front = NULL; rear = NULL; } Queue::~Queue() { delete front; } void Queue::enqueue(int data) { node *temp = new node(); temp->info = data; temp->next = NULL; if(front == NULL){ front = temp; }else{ rear->next = temp; } rear = temp; } int Queue::dequeue() { node *temp = new node(); int value; if(front == NULL){ cout<<"\nQueue is Emtpty\n"; }else{ temp = front; value = temp->info; front = front->next; delete temp; } return value; } bool Queue::isEmpty() { return (front == NULL); } /************************************************************ Class Graph represents a Graph [V,E] having vertices V and edges E. ************************************************************/ class Graph { private: int n; /// n is the number of vertices in the graph int **A; /// A stores the edges between two vertices public: Graph(int size = 2); ~Graph(); bool isConnected(int, int); void addEdge(int u, int v); void BFS(int ); }; Graph::Graph(int size) { int i, j; if (size < 2) n = 2; else n = size; A = new int*[n]; for (i = 0; i < n; ++i) A[i] = new int[n]; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) A[i][j] = 0; } Graph::~Graph() { for (int i = 0; i < n; ++i) delete [] A[i]; delete [] A; } /****************************************************** Checks if two given vertices are connected by an edge @param u vertex @param v vertex @return true if connected false if not connected ******************************************************/ bool Graph::isConnected(int u, int v) { return (A[u-1][v-1] == 1); } /***************************************************** adds an edge E to the graph G. @param u vertex @param v vertex *****************************************************/ void Graph::addEdge(int u, int v) { A[u-1][v-1] = A[v-1][u-1] = 1; } /***************************************************** performs Breadth First Search param s initial vertex *****************************************************/ void Graph::BFS(int s) { Queue Q; /** Keeps track of explored vertices */ bool *explored = new bool[n+1]; /** Initailized all vertices as unexplored */ for (int i = 1; i <= n; ++i) explored[i] = false; /** Push initial vertex to the queue */ Q.enqueue(s); explored[s] = true; /** mark it as explored */ cout << "Breadth first Search starting from vertex "; cout << s << " : " << endl; /** Unless the queue is empty */ while (!Q.isEmpty()) { /** Pop the vertex from the queue */ int v = Q.dequeue(); /** display the explored vertices */ cout << v << " "; /** From the explored vertex v try to explore all the connected vertices */ for (int w = 1; w <= n; ++w) /** Explores the vertex w if it is connected to v and and if it is unexplored */ if (isConnected(v, w) && !explored[w]) { /** adds the vertex w to the queue */ Q.enqueue(w); /** marks the vertex w as visited */ explored[w] = true; } } cout << endl; delete [] explored; } int main() { /** Creates a graph with 12 vertices */ Graph g(12); /** Adds edges to the graph */ g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(3, 4); g.addEdge(3, 6); g.addEdge(4 ,7); g.addEdge(5, 6); g.addEdge(5, 7); clock_t t1; t1 = clock(); /** Explores all vertices findable from vertex 1 */ g.BFS(1); float diff = (double)(clock() - t1)/CLOCKS_PER_SEC ; cout <<endl<< "The time taken for Breadth first search: "<< diff << endl; }
Complexity
The time complexity of the breadth-first search is O(bd). This can be seen by noting that all nodes up to the goal depth d are generated. Therefore, the number generated is b + b2 + . . . + bd which is O(bd). The space complexity is also O(bd) since all nodes at a given depth must be stored in order to generate the nodes at the next depth, that is, bd-1 nodes must be stored at depth d – 1 to generate nodes at depth d, which gives space complexity of O(bd).
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Basic Theory
Depth – first searches are performed by diving downward into a tree as quickly as possible. It does this by always generating a child node from the most recently expanded node, then generating that child’s children, and so on until a goal is found or some cutoff depth point d is reached. If a goal is not found when a leaf node is reached or at the cutoff point, the program backtracks to the most recently expanded node and generates another of its children. This process continues until a goal is found or failure occurs.Algorithm
- An algorithm for the depth – the first search is the same as that of breadth first search except in the ordering of the nodes.
- Place the starting nodes on the top of the stack.
- If the stack is empty, return failure and stop.
- If the element on the stack is goal node g, return success and stop. Otherwise,
- Remove and expand the first element , and place the children at the top of the stack.
- Return to step2.
Example
Source Code
#include <iostream> #include <ctime> #include <malloc.h> using namespace std; struct node{ int info; struct node *next; }; class stack{ struct node *top; public: stack(); void push(int); int pop(); bool isEmpty(); void display(); }; stack::stack(){ top = NULL; } void stack::push(int data){ node *p; if((p=(node*)malloc(sizeof(node)))==NULL){ cout<<"Memory Exhausted"; exit(0); } p = new node; p->info = data; p->next = NULL; if(top!=NULL){ p->next = top; } top = p; } int stack::pop(){ struct node *temp; int value; if(top==NULL){ cout<<"\nThe stack is Empty"<<endl; }else{ temp = top; top = top->next; value = temp->info; delete temp; } return value; } bool stack::isEmpty(){ return (top == NULL); } void stack::display(){ struct node *p = top; if(top==NULL){ cout<<"\nNothing to Display\n"; }else{ cout<<"\nThe contents of Stack\n"; while(p!=NULL){ cout<<p->info<<endl; p = p->next; } } } class Graph { private: int n; int **A; public: Graph(int size = 2); ~Graph(); bool isConnected(int, int); void addEdge(int x, int y); void DFS(int , int); }; Graph::Graph(int size) { int i, j; if (size < 2) n = 2; else n = size; A = new int*[n]; for (i = 0; i < n; ++i) A[i] = new int[n]; for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) A[i][j] = 0; } Graph::~Graph() { for (int i = 0; i < n; ++i) delete [] A[i]; delete [] A; } bool Graph::isConnected(int x, int y) { return (A[x-1][y-1] == 1); } void Graph::addEdge(int x, int y) { A[x-1][y-1] = A[y-1][x-1] = 1; } void Graph::DFS(int x, int required){ stack s; bool *visited = new bool[n+1]; int i; for(i = 0; i <= n; i++) visited[i] = false; s.push(x); visited[x] = true; if(x == required) return; cout << "Depth first Search starting from vertex "; cout << x << " : " << endl; while(!s.isEmpty()){ int k = s.pop(); if(k == required) break; cout<<k<<" "; for (i = n; i >= 0 ; --i) if (isConnected(k, i) && !visited[i]) { s.push(i); visited[i] = true; } } cout<<endl; delete [] visited; } int main(){ Graph g(8); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 5); g.addEdge(2, 6); g.addEdge(4, 7); g.addEdge(4, 8); g.DFS(1, 4); return 0; }
Complexity
The depth – the first search is preferred over the breadth – first when the search tree is known to have a plentiful number of goals. The time complexity of the depth-first tree search is the same as that for breadth-first, O(bd). It is less demanding in space requirements, however, since only the path from the starting node to the current node needs to be stored. Therefore, if the depth cutoff is d, the space complexity is just O(d).
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Dijkstra’s Shortest Path Algorithm is popular algorithm for finding shortest path between different nodes. The algorithm (Pseudo Code) is as follows
procedure Dijkstra (G): weighted connected simple graph, with all weights positive)[G has vertices a = v0, v1, ..... , vn = z and weights w(v1, v2) where w(vi, vj) = INFINITY if [vi, vj] is not an edge in G] for i := 1 to n L(vi) := INFINITY L(a) := 0 S := NULL [ the labels are now initialized so that the label of a is 0 and all other labels are INIFINITY, S is empty set] while z is not belongs to S begin u := a vertex not in S with L(u) minimal S := S U [u] for all vertices u not in S If L(u) + w(u,v) < L(v) then L(v) := L(u) + w(u,v) [this adds a vertex to S with minimal label and updates the labels vertices no in S] end [L(z) = length of a shortest path from a to z]
Example:
Now lets come to an example which further illustrates above algorithm. Consider a weighted graph
Here a, b, c .. are nodes of the graph and the number between nodes are weights (distances) of the graph. Now we are going to find the shortest path between source (a) and remaining vertices. The adjacency matrix of the graph is
Now the following source code implements the above example
#include<iostream> #define INFINITY 999 using namespace std; class Dijkstra{ private: int adjMatrix[15][15]; int predecessor[15],distance[15]; bool mark[15]; //keep track of visited node int source; int numOfVertices; public: /** Function read() reads No of vertices, Adjacency Matrix and source * Matrix from the user. The number of vertices must be greather than * zero, all members of Adjacency Matrix must be postive as distances * are always positive. The source vertex must also be positive from 0 * to noOfVertices - 1*/ void read(); /** Function initialize initializes all the data members at the begining of * the execution. The distance between source to source is zero and all other * distances between source and vertices are infinity. The mark is initialized * to false and predecessor is initialized to -1*/ void initialize(); /** Function getClosestUnmarkedNode returns the node which is nearest from the * Predecessor marked node. If the node is already marked as visited, then it search * for another node.*/ int getClosestUnmarkedNode(); /** Function calculateDistance calculates the minimum distances from the source node to * Other node. void calculateDistance(); /** Function output prints the results void output(); void printPath(int); }; void Dijkstra::read(){ cout<<"Enter the number of vertices of the graph(should be > 0)\n"; cin>>numOfVertices; while(numOfVertices <= 0) { cout<<"Enter the number of vertices of the graph(should be > 0)\n"; cin>>numOfVertices; } cout<<"Enter the adjacency matrix for the graph\n"; cout<<"To enter infinity enter "<<INFINITY<<endl; for(int i=0;i<numOfVertices;i++) { cout<<"Enter the (+ve)weights for the row "<<i<<endl; for(int j=0;j<numOfVertices;j++) { cin>>adjMatrix[i][j]; while(adjMatrix[i][j]<0) { cout<<"Weights should be +ve. Enter the weight again\n"; cin>>adjMatrix[i][j]; } } } cout<<"Enter the source vertex\n"; cin>>source; while((source<0) && (source>numOfVertices-1)) { cout<<"Source vertex should be between 0 and"<<numOfVertices-1<<endl; cout<<"Enter the source vertex again\n"; cin>>source; } } void Dijkstra::initialize(){ for(int i=0;i<numOfVertices;i++) { mark[i] = false; predecessor[i] = -1; distance[i] = INFINITY; } distance[source]= 0; } int Dijkstra::getClosestUnmarkedNode(){ int minDistance = INFINITY; int closestUnmarkedNode; for(int i=0;i<numOfVertices;i++) { if((!mark[i]) && ( minDistance >= distance[i])) { minDistance = distance[i]; closestUnmarkedNode = i; } } return closestUnmarkedNode; } void Dijkstra::calculateDistance() { initialize(); int minDistance = INFINITY; int closestUnmarkedNode; int count = 0; while(count < numOfVertices) { closestUnmarkedNode = getClosestUnmarkedNode(); mark[closestUnmarkedNode] = true; for(int i=0;i<numOfVertices;i++) { if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) { if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) { distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]; predecessor[i] = closestUnmarkedNode; } } } count++; } } void Dijkstra::printPath(int node){ if(node == source) cout<<(char)(node + 97)<<".."; else if(predecessor[node] == -1) cout<<"No path from “<<source<<”to "<<(char)(node + 97)<<endl; else { printPath(predecessor[node]); cout<<(char) (node + 97)<<".."; } } void Dijkstra::output() { for(int i=0;i<numOfVertices;i++) { if(i == source) cout<<(char)(source + 97)<<".."<<source; else printPath(i); cout<<"->"<<distance[i]<<endl; } } int main() { Dijkstra G; G.read(); G.calculateDistance(); G.output(); return 0; }
The output of above program is
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Hashing is the transformation of a string of characters into a usually shorter fixed-length value or key that represents the original string.
Hash Function
A function that transforms a key into a table index is called a hash function. If h is a hash function and key is a key, h(key) is called the hash of key and is the index at which a record with the key key should be placed. If r is a record whose key hashes into hr, hr is called hash key of r. The has function in the preceding example is h(k) = key % 1000. The values that h produce should cover the entire set of indices in the table. For example, the function x % 1000 can produce any integer between 0 and 999, depending on the value of x. As we shall see shortly, it is good idea for the table size to be somewhat larger than the number of records that are to be inserted.
Hash Collision
Suppose that two keys k1 and k2 are such that h(k1) equals h(k2). Then when a k2 is hashed, because its has key is the same as that of k2, an attempt may be made to insert the record into the same position where the record with key k1 is stored. Clearly, two records cannot occupy the same position, Such a situation is called a hash collision or a hash clash.Source code for Hashing and Hash table generation in C/C++
#include<iostream> #include<cstdlib> using namespace std; class hash { private: int hash_pos; int array[40]; public: hash(); void insert(); void search(); int Hash(int ); int reHash(int ); void Delete(); }; hash::hash(){ for(int i = 0; i < 40; i++){ array[i] = '*'; } } void hash::insert() { int data; int count = 0; cout<<"Enter the data to insert: "; cin>>data; hash_pos = Hash(data); if(hash_pos >= 40){ hash_pos = 0; } while(array[hash_pos] != '*'){ hash_pos = reHash(hash_pos); count++; if(count>=40){ cout<<"Memory Full!!No space is avaible for storage"; break; } } if(array[hash_pos] == '*'){ array[hash_pos] = data; } cout<<"Data is stored at index "<<hash_pos<<endl; } int hash::Hash(int key) { return key%100; } int hash::reHash(int key) { return (key+1)%100; } void hash::search() { int key,i; bool isFound = false; cout<<"Enter the key to search: "; cin>>key; for(i = 0; i < 40; i++) { if(array[i] == key) { isFound = true; break; } } if(isFound) { cout<<"The key is found at index "<< i <<endl; } else { cout<<"No record found!!"<<endl; } } void hash::Delete(){ int key,i; bool isFound = false; cout<<"Enter the key to delete: "; cin>>key; for(i = 0; i < 40; i++){ if(array[i] == key){ isFound = true; break; } } if(isFound) { array[i] = '*'; cout<<"The key is deleted"<<endl; } else { cout<<"No key is Found!!"; } } int main() { hash h; int choice; while(1){ cout<<"\n1. Insert\n2. Search\n3. Delete\n4. Exit\n"; cout<<"Enter your choice: "; cin>>choice; switch(choice){ case 1: h.insert(); break; case 2: h.search(); break; case 3: h.Delete(); break; case 4: exit(0); default: cout<<"\nEnter correct option\n"; break; } } return 0; }
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
Conversion of infix string to postfix and evaluation of postfix string to make a simple calculator application in C++.
(A) Algorithm for converting an infix expression into postfix operation
1.Add “(“ at the beginning and “)” at the end of an infix expression Q. 2. Scan Q from left to right and repeat step 3 to step 6.
3 If an operand is encountered, add it into postfix P.
4. If a left parenthesis is encountered, push it onto the stack S
5. If and operator op is encountered then,
4. If a left parenthesis is encountered, push it onto the stack S
5. If and operator op is encountered then,
(a) Repeatedly pop from stack S and add
it to postfix each operator which has same precedence as or higher precedence than op.
(b) Add op to Stack S. 6. If a right parenthesis is encountered, then (a) Repeatedly pop from stack S and add
it to postfix each operator until left parenthesis is encountered on stacks.
(c) Remove the left parenthesis.
(B) Algorithm for evaluation of postfix string
- Scan postfix P from left to right and repeat step 2 and 3 for each elements of P until the NULL character or other symbol is encountered.
- . If an operand is encountered then push it on to the stack.
- If an operator op is encountered, then (a) Remove the top elements of stack S where A is the top element and B is next top element (b) Evaluate B op A (c) Place the result back onto the stack S (d) Return top of the stack which is required
Source code for both infix to postfix and postfix evaluation
/****************************************************************
Program: Conversion of Infix to Postfix String and Evaluation
Language: C/C++
/****************************************************************
Program: Conversion of Infix to Postfix String and Evaluation
Language: C/C++
Operators Used
1. '+' For addition 2. '-' For Subtraction 3. '*' For Multiplication 4. '/' For Division 5. '^' For Exponentiation
Program Limitations
* This program Only process single digit operations
* Can't handle unary operation
* Only process left to right associativity
***************************************************/
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#define MAX_SIZE 20
using namespace std;
template<class T>
class Stack{
private:
T item[MAX_SIZE];
int top;
public:
Stack(){
top = -1;
}
void push(T data){
if(!this->is_full())
item[++top] = data;
else{
cout<<"Stack Error"<<endl;
exit(10);
}
}
T pop(){
if(!this->is_empty())
return item[top--];
else{
cout<<"Stack is Empty"<<endl;
exit(11);
}
}
int size(){
return top+1;
}
bool is_empty(){
if(top==-1)
return true;
else
return false;
}
bool is_full(){
if(top==MAX_SIZE-1)
return true;
else
return false;
}
void display(){
for(int i=0; i<this->size(); i++){
cout<<item[i]<<" ";
}
cout<<endl;
}
T return_top(){
return item[top];
}
};
class Convert{
private:
bool num_flag;
bool two_digit_flag;
public:
Convert();
string return_with_bracket(string infix);
void to_Postfix(string infix,char postfix[]);
bool prcd(char op1, char op2);
int isOperand(char op);
int isOperator(char op);
bool return_flag(){
return num_flag;
}
};
Convert::Convert(){
this->num_flag = false;
this->two_digit_flag = false;
}
string Convert::return_with_bracket(string infix){
return("(" + infix + ")");
}
bool Convert::prcd(char op1, char op2){
if((op1=='+' || op1=='-' || op1=='*' || op1=='/') && op2=='(' )
return true;
if(op1=='+' && op2=='+')
return true;
if(op1=='-' && op2=='-')
return false;
if(op1=='-' && op2=='+')
return false;
if(op1=='+' && op2=='-')
return false;
if(op1=='/' && op2=='/')
return false;
if(op1=='/' && (op2=='-' || op2=='+'))
return true;
if(op1=='*' && (op2=='+' || op2=='-'))
return true;
if((op1 == '-' || op1 == '+') && (op2 =='*' || op2 == '/'))
return false;
if((op1 == '#39; || op1 == '+') && (op2 =='*' || op2 == '/' || op2=='-'))
return true;
if((op1 == '-' || op1 == '+' || op1 =='*' || op1 == '/')&& op2=='^')
return false;
if(op1 == '^' && ( op2 == '+' || op2 =='*' || op2 == '/' || op2=='-'))
return false;
}
int Convert::isOperand(char op){
return(op>= '0' && op <= '9');
}
int Convert::isOperator(char op){
return(op=='+' || op=='-' || op == '/' || op=='*' || op=='^');
}
void Convert::to_Postfix(string infix, char postfix[]){
int position, outpos=0;
char c;
int count = 0;
char temp;
char stacktop ;
Stack<char> stack;
for(position = 0; (c = infix[position])!='\0'; position++){
if(this->isOperand(c)){
postfix[outpos++] = c;
this->num_flag = true;
count++;
if(count>=2){
this->two_digit_flag = true;
}
}else if(this->isOperator(c)){
count = 0;
if(isOperator(infix[position]) && isOperator(infix[position+1])){
cout<<"\aMissing argument in between "<<infix[position]<<" and "<<infix[position+1]
<<" in column "<< position+1<<endl;
exit(9);
}
if(this->prcd(c, stacktop)){
stacktop=stack.return_top();
stack.push(c);
stacktop = c;
}else{
while(true){
temp = stack.pop();
postfix[outpos++] =temp;
stacktop = stack.return_top();
if(prcd(c, stacktop) || stacktop=='(')
break;
}
stack.push(c);
stacktop = stack.return_top();
}
}
else if(c=='('){
count = 0;
stack.push(c);
stacktop = stack.return_top();
}else if(c==')'){
count = 0;
while(1){
if(stack.size()==0){
cout<<"Warning!! Number of ')' is greater than '('" <<endl;
exit(2);
}
temp = stack.pop();
if(temp!='('){
postfix[outpos++] = temp;
}else{
break;
}
}
stacktop =stack.return_top();
}
else{
cout<<"Invalid input";
exit(3);
}
if(infix[position]==')' && infix[position+1]=='('){
stack.push('*');
stacktop = stack.return_top();
}
}
if(stack.size()!=0){
cout<<"Warning!!Number of '(' is greater than ')'"<<endl;
// exit(6);
}
if(!this->return_flag()){
cout<<"You must Enter Numeric value for calculation"<<endl;
cout<<"This program cannot perform operations on variables";
exit(5);
}
if(this->two_digit_flag){
cout<<"Sory! Althoug u may have entered right string"<<endl;
cout<<"this program is only for single digit operation"<<endl;
exit(8);
}
postfix[outpos] = '\0';
}
class Evaluate{
public:
double eval(char expr[], Convert &);
double oper(int symb, double op1, double op2);
};
double Evaluate::oper(int symb, double op1, double op2){
switch(symb){
case '+': return (op1 + op2);
case '-': return (op1 - op2);
case '*': return (op1 * op2);
case '/': return (op1 / op2);
case '^': return (pow(op1, op2));
}
}
double Evaluate::eval(char expr[],Convert &convert){
int c, position;
char temp1;
int count = 0;
double opnd1, opnd2, value;
Stack<double> stack;
for(position = 0; (c = expr[position])!='\0'; position++){
if(convert.isOperand(c)){
temp1 = double(c-'0');
stack.push(temp1);
}else{
opnd2 = stack.pop();
if(stack.size()==0){
cout<<"This program cannot process unary operation";
exit(1);
}
opnd1 = stack.pop();
value = oper(c, opnd1, opnd2);
stack.push(value);
}
}
if(stack.size()>=2){
cout<<"Sory! this program cannot calculate this"<<endl;
cout<<"Enter +, *, /, - or ^ between bracket"<<endl;
exit(4);
}
return (stack.pop());
}
int main(){
Convert convert;
Evaluate evaluate;
string bracketted_infix;
char infix[50], postfix[50];
char choice;
while(1){
cout<<"Enter string: ";
cin>>infix;
cout<<endl;
cout<<"Entered String: "<<infix<<endl;
bracketted_infix = convert.return_with_bracket(infix);
convert.to_Postfix(bracketted_infix, postfix);
cout<<"Equivalent Postfix string: "<<postfix<<endl;
cout<<"RESULT: ";
cout<<evaluate.eval(postfix, convert);
cout<<"\nCalculate another string?(y/n) ";
cin>>choice;
cout<<endl;
if(choice=='n')
break;
}
return 0;
}
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
In linear queue, when we delete any element, only front increment by one but position is not used later. So, when we perform more add and delete operations, memory wastage increases. But in circular queue, memory is utilized if we delete any element that position is used later due to its circular representation.
2. For enqueue operation, If head = (tail+1)%MAXSIZE print "Queue is Full" Else queue[tail] = item tail = (tail+1)%MAXSIZE
3. For enqueue of next data item, goto step 2
4. For dequeue operation, If head = tail print "Queue is Empty" Else Remove item i.e. item =
queue[head] Set head = (head + 1)%MAXSIZE
5. For next dequeue operation , goto step 4
6. Stop
Source Code for Circular Queue
Algorithm for Circular Queue
1. Declare and initialize necessary variables such as head = 0, tail = 0 etc.2. For enqueue operation, If head = (tail+1)%MAXSIZE print "Queue is Full" Else queue[tail] = item tail = (tail+1)%MAXSIZE
3. For enqueue of next data item, goto step 2
4. For dequeue operation, If head = tail print "Queue is Empty" Else Remove item i.e. item =
queue[head] Set head = (head + 1)%MAXSIZE
5. For next dequeue operation , goto step 4
6. Stop
Source Code for Circular Queue
#include<iostream> #include<cstdlib> #define MAX_SIZE 4 using namespace std; class Queue { private: int item[MAX_SIZE]; int head; int tail; public: Queue(); void enqueue(int); int dequeue(); int size(); void display(); bool isEmpty(); bool isFull(); }; Queue::Queue() { head = 0; tail = 0; } void Queue::enqueue(int data) { item[tail] = data; tail = (tail+1)%MAX_SIZE; } int Queue::dequeue() { int temp; temp = item[head]; head = (head+1)%MAX_SIZE; return temp; } int Queue::size(){ return (tail - head); } void Queue::display(){ int i; if(!this->isEmpty()){ for(i=head; i!=tail; i=(i+1)%MAX_SIZE){ cout<<item[i]<<endl; } } else { cout<<"Queue Underflow"<<endl; } } bool Queue::isEmpty(){ if(abs(head == tail)){ return true; }else{ return false; } } bool Queue::isFull(){ if(head==(tail+1)%MAX_SIZE){ return true; } else { return false; } } int main() { Queue queue; int choice, data; while(1){ cout<<"\n1. Enqueue\n2. Dequeue\n3. Size\n4. Display all element\n5. Quit"; cout<<"\nEnter your choice: "; cin>>choice; switch(choice){ case 1: if(!queue.isFull()){ cout<<"\nEnter data: "; cin>>data; queue.enqueue(data); }else{ cout<<"Queue is Full"<<endl; } break; case 2: if(!queue.isEmpty()){ cout<<"The data dequeued is :"<<queue.dequeue(); }else{ cout<<"Queue is Emtpy"<<endl; } break; case 3: cout<<"Size of Queue is "<<queue.size(); break; case 4: queue.display(); break; case 5: exit(0); break; } } return 0; }
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
The simplest form of a search is the Sequential Search. This search is applicable to a table organized either as an array or as a linked list. Let us assume that k is an array of n keys, k(0) through k(n-1), and r an array of records, r(0) through r(n-1), such that k(i) is the key of r(i). Let us also assume that key is a search argument. We wish to return the smallest integer i such that k(i) equals key if such an i exists and –1 otherwise.
We can improve this algorithm by inserting an extra key at the end of array called ‘sentinel’. Which prevents beyond the upper bound of array error and generating that key will be found preventing from infinite looping.
Algorithm
for(i = 0; i < n; i++) if(key==k(i)) return (i); else return (-1);
We can improve this algorithm by inserting an extra key at the end of array called ‘sentinel’. Which prevents beyond the upper bound of array error and generating that key will be found preventing from infinite looping.
Source Code:
#include<iostream> using namespace std; int main(){ int arr[10]; int no_of_elements, key; bool found = false; cout<<"Enter the number of element: "; cin>>no_of_elements; for(int i = 0; i < no_of_elements; i++){ cout<<"arr["<<i<<"]: "; cin>>arr[i]; } cout<<"Enter the value to search: "; cin>>key; for(int i=0;i<no_of_elements;i++) { if(key == arr[i]) { found = true; cout<<"The value is found at index arr["<<i<<"]"; } } if(!found) { cout<<"Key not found!"; } return 0; } Output Enter the number of element: 7 arr[0]: 8 arr[1]: 9 arr[2]: 45 arr[3]: 12 arr[4]: 36 arr[5]: 75 arr[6]: 16
Enter the value to search: 36
The value is found at index arr[4]
Efficiency of Sequential Search
Best Case: requires only one comparison, so O(1). Worst Case: requires n comparisons, so O(n).Average Case: requires (n+1)/2 comparisons again O(n).
The value is found at index arr[4]
Efficiency of Sequential Search
Best Case: requires only one comparison, so O(1). Worst Case: requires n comparisons, so O(n).Average Case: requires (n+1)/2 comparisons again O(n).
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
An insertion sort is that which sort a record of data by inserting records into an existing sorted file. The list is divided into two parts: sorted and unsorted. In each pass, the first element of the unsorted sub-list is inserted into the sorted sub-list in proper position.
In this algorithm, we take x[0] as sorted file initially
Efficiency of Straight Insertion sort
Algorithm
1. Declare and initialize necessary variable such as array[], n, i, j etc 2. Insert each x[k] into sorted file i.e. for k = 1 to k < n, repeat temp = x[k] 2.1 Move down one position all elements greater than temp i.e. for ( i = k-1; i >= i && temp < x[i]; i--) x[i+1]=x[i] 2.2 x[i+1] = temp 3. Display the sorted array.
In this algorithm, we take x[0] as sorted file initially
Source Code:
#include<iostream> using namespace std; class InsertionSort { private: int no_of_elements; int elements[10]; public: void getarray(); void sortit(); void display(); }; void InsertionSort::getarray() { cout<<"How many elements? "; cin>>no_of_elements; cout<<"Insert array of element to sort: "; for(int i = 0; i < no_of_elements; i++) { cin>>elements[i]; } } void InsertionSort::sortit(){ int temp, i , j; for(i = 0; i < no_of_elements; i++) { temp = elements[i]; for(j = i-1; j >= 0 && temp < elements[j]; j--) { elements[j+1] = elements[j]; } elements[j+1] = temp; cout<<"Iteration "<<i+1<<" : "; display(); } } void InsertionSort::display() { for(int i = 0 ; i < no_of_elements; i++) { cout<<elements[i]<<" "; } cout<<endl; } int main() { InsertionSort IS; IS.getarray(); IS.sortit(); return 0; }
Output
How many elements? 6 Insert array of element to sort: 52 36 96 12 58 3 Iteration 1 : 52 36 96 12 58 3 Iteration 2 : 36 52 96 12 58 3 Iteration 3 : 36 52 96 12 58 3 Iteration 4 : 12 36 52 96 58 3 Iteration 5 : 12 36 52 58 96 3 Iteration 6 : 3 12 36 52 58 96
Efficiency of Straight Insertion sort
Efficiency of Straight Insertion sort is O(n^2)
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
In selection sort
In each pass smallest/largest element is selected and placed in a sorted list.
Th entire array is divided into two parts: sorted and unsorted
In each pass, in the unsorted subarray, the smallest element is selected and exchanged with the first element.
Algorithm
1. Declare and initialize necessary variables such as array[], i, j, large, n etc.
2. for ( i = n - 1; i > 0; i--), repeat following steps
large = x[0];
index = 0;
2.1 for(j = i ; j <= i; j++)
if x[j] > large
large = x[i]
index = j
2.2 x[index] =x[i]
x[i] = large
3. Display the sorted array
Source Code:
#include<iostream>
using namespace std;
class SelectionSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit(int [], int);
void display();
};
void SelectionSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i<no_of_elements;i++){
cin>>elements[i];
}
}
void SelectionSort::sortit(int x[], int n){
int i, indx, j, large;
for(i = n - 1; i > 0; i--){
large = x[0];
indx = 0;
for(j = 1; j <= i; j++){
if(x[j] > large){
large = x[j];
indx = j;
}
}
x[indx] = x[i];
x[i] = large;
}
}
void SelectionSort::display()
In each pass smallest/largest element is selected and placed in a sorted list.
Th entire array is divided into two parts: sorted and unsorted
In each pass, in the unsorted subarray, the smallest element is selected and exchanged with the first element.
Algorithm
1. Declare and initialize necessary variables such as array[], i, j, large, n etc.
2. for ( i = n - 1; i > 0; i--), repeat following steps
large = x[0];
index = 0;
2.1 for(j = i ; j <= i; j++)
if x[j] > large
large = x[i]
index = j
2.2 x[index] =x[i]
x[i] = large
3. Display the sorted array
Source Code:
#include<iostream>
using namespace std;
class SelectionSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit(int [], int);
void display();
};
void SelectionSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i<no_of_elements;i++){
cin>>elements[i];
}
}
void SelectionSort::sortit(int x[], int n){
int i, indx, j, large;
for(i = n - 1; i > 0; i--){
large = x[0];
indx = 0;
for(j = 1; j <= i; j++){
if(x[j] > large){
large = x[j];
indx = j;
}
}
x[indx] = x[i];
x[i] = large;
}
}
void SelectionSort::display()
{
cout<<"The sorted array is :\n";
for(int i = 0 ; i < no_of_elements; i++)
cout<<"The sorted array is :\n";
for(int i = 0 ; i < no_of_elements; i++)
{
cout<<elements[i]<<" ";
}
cout<<endl;
}
int main()
cout<<elements[i]<<" ";
}
cout<<endl;
}
int main()
{
SelectionSort SS;
SS.getarray();
SS.sortit(SS.elements,SS.no_of_elements);
SS.display();
return 0;
}
Output:
How many elements? 6
Insert array of element to sort: 78 56 110 12 56 26
The sorted list is 12 26 56 56 78 110
Efficiency of Straight selection sort
In this first pass, it makes (n – 1) comparisons, in second pass it makes (n – 2) comparisons and so on, So total number of comparisons is n(n-1)/2 which is O(n^2)
SelectionSort SS;
SS.getarray();
SS.sortit(SS.elements,SS.no_of_elements);
SS.display();
return 0;
}
Output:
How many elements? 6
Insert array of element to sort: 78 56 110 12 56 26
The sorted list is 12 26 56 56 78 110
Efficiency of Straight selection sort
In this first pass, it makes (n – 1) comparisons, in second pass it makes (n – 2) comparisons and so on, So total number of comparisons is n(n-1)/2 which is O(n^2)
Place where all sort of programming stuff and reviews,technology news are shared and Useful Project of C++,C,java C# etc
In tree sort, the given data is first converted into a binary tree. The inorder traversal of the binary tree results in the sorted form which is known as tree sort.
Algorithm
Algorithm
1. Declare and initialize necessary variables.
2. Input the array of element to be sorted from the user.
3. Make a binary tree of the elements.
4. Traverse the binary tree using inorder traversal.
5. Display the result which are in sorted form
2. Input the array of element to be sorted from the user.
3. Make a binary tree of the elements.
4. Traverse the binary tree using inorder traversal.
5. Display the result which are in sorted form
Source Codes
#include<iostream>
using namespace std;
struct tree{
int info;
tree *Left, *Right;
};
tree *root;
class TreeSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit();
void insert1(int);
tree *insert2(tree *, tree *);
void display(tree *);
};
void TreeSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i<no_of_elements;i++){
cin>>elements[i];
}
}
void TreeSort::sortit(){
for(int i = 0; i < no_of_elements; i++){
insert1(elements[i]);
}
}
tree* TreeSort::insert2(tree *temp,tree *newnode){
if(temp==NULL){
temp=newnode;
}
else if(temp->info < newnode->info){
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else{
insert2(temp->Left,newnode);
if(temp->Left==NULL)
temp->Left=newnode;
}
return temp;
}
void TreeSort::insert1(int n){
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}
/* Inorder traversal */
void TreeSort::display(tree *t = root){
if(root==NULL){
cout<<"Nothing to display";
}else
if(t!=NULL){
display(t->Left);
cout<<t->info<<" ";
display(t->Right);
}
}
int main(){
TreeSort TS;
TS.getarray();
TS.sortit();
TS.display();
return 0;
}
using namespace std;
struct tree{
int info;
tree *Left, *Right;
};
tree *root;
class TreeSort{
public:
int no_of_elements;
int elements[10];
public:
void getarray();
void sortit();
void insert1(int);
tree *insert2(tree *, tree *);
void display(tree *);
};
void TreeSort::getarray(){
cout<<"How many elements? ";
cin>>no_of_elements;
cout<<"Insert array of element to sort: ";
for(int i=0;i<no_of_elements;i++){
cin>>elements[i];
}
}
void TreeSort::sortit(){
for(int i = 0; i < no_of_elements; i++){
insert1(elements[i]);
}
}
tree* TreeSort::insert2(tree *temp,tree *newnode){
if(temp==NULL){
temp=newnode;
}
else if(temp->info < newnode->info){
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else{
insert2(temp->Left,newnode);
if(temp->Left==NULL)
temp->Left=newnode;
}
return temp;
}
void TreeSort::insert1(int n){
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}
/* Inorder traversal */
void TreeSort::display(tree *t = root){
if(root==NULL){
cout<<"Nothing to display";
}else
if(t!=NULL){
display(t->Left);
cout<<t->info<<" ";
display(t->Right);
}
}
int main(){
TreeSort TS;
TS.getarray();
TS.sortit();
TS.display();
return 0;
}
Output
How many elements? 5
Insert array of element to sort: 85 53 26 98 77
26 53 77 85 98
26 53 77 85 98
Subscribe to:
Posts (Atom)