Bubble Sort works by comparing all the elements one by one and then sorting them according to there value. With every iteration the smaller element goes up towards the first place in the list and the larger element moves towards the end. All the items are compared one-by-one in pairs and swap each pair if elements are out of order.
It takes less time to move the bigger element to end whereas it is always slower to move the smaller element to start.
Consider the following:
Input Array {6 2 8 4 10}
Pass1
(62 8 4 10 ) à(2 6 8 4 10) . 2 and 6 will be swapped since 6>2
(2 684 10)à(2 64 8 10) .Swap since 8>4
(2 6 4 8 10 )à(2 6 4 8 10).
Array is sorted now but to know it is sorted it will go for another whole pass (without swap)
Insertion Sort
This is a comparison-basedin-place sorting algorithm, it maintains sub-list (lower part of an array) which is always sorted.
Insertion sort takes one input element repeatedly (in iteration) and output (sorted list) starts growing. With every iteration, it removes an element from the input, and searches the location/place in the sorted list, and starts the insertion till no input element is left.
It is called in place Sorting, as with every iteration the sorted list starts growing. The value of every array element is checked against the largest value in the sorted list. The element will remain in place if the element is greater than the largest value of the sorted list, and it moves to the next. If value is smaller, it locates the correct position of the element in the sorted list and larger values elements are shifted up to make a space, and placed at that correct position.
First n + 1 entries are sorted after n iterations in the resulted array, in each every the first entry of the input is removed, and inserted in the correct position in the sorted list.
It is a comparison-basedin-place algorithm. Right side of the list is divided into two parts: The left part contains sorted elements and the right part contains unsorted element list. In the binging the sorted part is empty and the unsorted part contains the entire list.
In selection sort the input lists is divided into two parts sub-list which is sorted and the sub-list which is yet to be sorted (unsorted). Sorted sub-list consists of elements from left to right .Initially sub-list which is sorted contains no element and the unsorted sub-list contain all the inputs. It locates the smallest element in the unsorted sub-list and swaps with the leftmost unsorted element (placed in sorted order).
78 28 10 20 9 //// Start State
9 28 10 20 78 //// sorted sub-list = {9}
9 10 28 2078 //// sorted sub-list = {9, 10}
9 10 20 2878 //// sorted sub-list = {9, 10, 20}
9 10 20 2878 //// sorted sub-list = {9, 10, 20, 28}
9 10 20 2878 //// sorted sub-list = {9, 10, 20, 28, 78}
Uses divide and conquer technique
We start by choosing Pivot value first and then consider middle element as pivot value, any random value can be taken into consideration, within the range of sorted values.
Then we proceeds by rearranging elements in such a way, that all elements which are lesser than the pivot go to the left part of the array and all elements greater than the pivot, go to the right part of the array. Values equal to the pivot can stay in any part of the array. Moreover, that array may be divided in non-equal parts.
Time complexity: O(n log n) is the average in all cases as it needs to handle large data volumes.
Uses divide and conquer technique
The diagram given below explains it
The values in parent node are compared with values in 2 children nodes. If the parent node value is greater than children nodes then it is max heap and if it is smaller, then it is represented as min heap. Considering the parent node is stored at index K, the left child can be calculated by 2 * K + 1 and right child by 2 * K + 2 (K starts at 0).
The below diagram illustrates it
Input data: 5, 11, 4, 6, 2
5(0)
/
11(1) 4(2)
/
6 (3) 2(4)
Indexes are numbers given in the bracket.
Apply heapify procedure to index 1:
5(0)
/
11(1) 4(2)
/
6(3) 2(4)
Apply heapify procedure to index 0:
11(0)
/
6(1) 4(2)
/
5(3) 2(4)
This procedure is called recursively until heap is built in top down manner.
a) We will be using graph theory to obtain all possible orderings Obtain all possible combinations of the set of points, and then select the combinations that will minimize the total length using the following:
OptimalTSP(P)
d=∞
For each of the n! permutations Pi of point set P
If (cost(Pi)≤d) then d=cost(Pi) and Pmin=Pi
Return Pmin
Since all possible combinations are considered, personPj could be reached by a sequence of direct contacts stating from Pi.
b) (P1 , P2, 3), (P2 , P4, 6), (P3 , P4, 8), (P1 , P4, 10).If P1 was infected at time 2, Then P3 would be infected at time 8 by a sequence of three steps: first P2 becomes infected at time 3, then P4 gets the infection from P2 at time 6, and then P3 gets the infection from P4 at time 8.So we should return 8 if the query is p3. On the other hand, if the trace data were (P2 , P3, 5), (P2 , P4, 6), (P3 , P4, 10), (P1 , P4, 12)and again P1 was infected at time 2, then P3 would not become infected during the period of observation. There is no sequence of direct contacts moving forward in time by which the infection could get from P1 to P3 in this second example. So we should return ∞ if the query is P3.
We use graph theory here. Considering G as a graph ,V (G) is set of vertces and E(G) is the set of edges . The number of vertices is written as v|G|, and the number of edges is written e(G). A graph may have multiple edges, i.e. more than one edge between some pair of vertices, or loops, i.e. edges from a vertex to itself. Two vertices joined by an edge are called adjacent. Let G be a directed graph represented by an adjacency list. Suppose each node u has a weight w(u), which might be different for each node reachable from u. So, for example, if G is strongly connected then every node can reach every other node, so for every node the maximum reachable weight is the same (the largest weight of any node in the graph). More formally, for each vertex u let R(u) denote the vertices reachable from u. Then when your algorithm is run on G, it should return an array of values where the value for node u is maxv∈R(u) w(v) or O(max(m,n)) also written as O(m+n) .
Or v1 + (incidentEdges) + v2 + (incidentEdges) + …. + vn + (incident edges)
Can be rewritten as
(v1 + v2 + … + vn) + [(incidentEdges v1) + (incidentEdges v2) + … + (incidentEdgesvn)]
(v1 + v2 + … + vn) is O(N) while incidentEdges v1) + (incidentEdges v2) + … + (incidentEdgesvn isO(E).
DepthFirstSearch Algo For Setting/getting a vertex/edge label time taken O(1) .Each vertex is labeled twice once as UNEXPLOREDonce as VISITEDEach edge is labeled twice once as UNEXPLOREDonce as DISCOVERY or BACKMethod incident Edges is called once for every vertexDFS runs in O(n + m) time provided the graph is represented by the adjacency list structureRecall that Σvdeg(v) = 2mBreadth FS (analysis):For Setting/getting a vertex time taken is O(1).Each vertex is labeled twice once as UNEXPLOREDonce as VISITEDEach edge is labeled twice once as UNEXPLOREDonce as DISCOVERY or CROSSEach vertex is added once into a seq LiMethod incident Edges is called once for each vertexBFS runs in O(n + m) time provided the graph is represented by the adjacency list structureRecall that Σvdeg(v) = 2m
a) Bridges to build with minimum construction cost, using
1. Kruskal’s algorithm
In a separate cluster, it starts with every vertex, and in each step it merges two clusters. In this case, the clusters are merged in the below order:
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
248 |
210 |
340 |
280 |
200 |
345 |
120 |
2 |
265 |
175 |
215 |
180 |
185 |
155 |
|
3 |
260 |
115 |
350 |
435 |
195 |
||
4 |
160 |
330 |
295 |
230 |
|||
5 |
360 |
400 |
170 |
||||
6 |
175 |
205 |
|||||
7 |
305 |
3 to 5 (115)
1 to 8 (120)
2 to 8 (155)
4 to 5 (160)
5 to 8 (170)
6 to 7 (175) [Note that 2 and 4 are already in the same cluster]
2 to 6 (180)
2. The Prim-Jarník algorithm
At each step of the tree a new vertex is added. The order of adding new vertex is depends upon the starting vertex, so that the resulting tree should be the same. For example: The edges will be added in the below order if the vertex 8 will be the starting index.
8 to 1 (120)
8 to 2 (155)
8 to 5 (170)
5 to 3 (115)
5 to 4 (160)
2 to 6 (180)
6 to 7 (175)
This graph is obtained for both points (1) and (2)
1 — 8 — 2 — 6 — 7
|
|
3 — 5 – 4
b) Implementation using JAVA
Pick the starting node ‘8’ (mark it has reached) and other nodes will be marked as unreached.
ReachedSet = {8}; // It can use any node.
UnReachedSet = {2, 4, 6 … N-1};
SpanningTree = {};
while (UnReachedSet != empty)
{
Find edge e = (x, y) such that:
SpanningTree = SpanningTree∪ {e};
ReachedSet = ReachedSet∪ {y};
UnReachedSet = UnReachedSet – {y};
}
public void PrimMdh( ) { Int i, j, k; Int x,y; boolean[] ReachedAry = new boolean[N_Nodes]; //// Reach/un-reach nodes int[] prenodeAry = new int[N_Nodes]; //// Remember min cost edge ReachedAry[1] = true; for ( i = 1; i < N_Nodes; i++ ) { ReachedAry[i] = false; } prenodeAry[8] = 8; //// make sure not to have a bogus edge for ( k = 1; k <N_Nodes; k++) // Loop N_Nodes-1 times (UnReachedSet = empty) { x = y = 8; for ( i = 1; i<N_Nodes; i++ ) for ( j = 1; j <N_Nodes; j++ ) { if ( ReachedAry[i] && ! ReachedAry[j] && LinkCost[i][j] <LinkCostes[x][y] ) { x = i; // Link (i,j) has lower cost y = j; } } prenodeAry[y] = x; ReachedAry[y] = true; } printMinCostEdges(prenodeAry); //// Print min cost spanning tree } |
We provide professional writing services to help you score straight A’s by submitting custom written assignments that mirror your guidelines.
Get result-oriented writing and never worry about grades anymore. We follow the highest quality standards to make sure that you get perfect assignments.
Our writers have experience in dealing with papers of every educational level. You can surely rely on the expertise of our qualified professionals.
Your deadline is our threshold for success and we take it very seriously. We make sure you receive your papers before your predefined time.
Someone from our customer support team is always here to respond to your questions. So, hit us up if you have got any ambiguity or concern.
Sit back and relax while we help you out with writing your papers. We have an ultimate policy for keeping your personal and order-related details a secret.
We assure you that your document will be thoroughly checked for plagiarism and grammatical errors as we use highly authentic and licit sources.
Still reluctant about placing an order? Our 100% Moneyback Guarantee backs you up on rare occasions where you aren’t satisfied with the writing.
You don’t have to wait for an update for hours; you can track the progress of your order any time you want. We share the status after each step.
Although you can leverage our expertise for any writing task, we have a knack for creating flawless papers for the following document types.
Although you can leverage our expertise for any writing task, we have a knack for creating flawless papers for the following document types.
From brainstorming your paper's outline to perfecting its grammar, we perform every step carefully to make your paper worthy of A grade.
Hire your preferred writer anytime. Simply specify if you want your preferred expert to write your paper and we’ll make that happen.
Get an elaborate and authentic grammar check report with your work to have the grammar goodness sealed in your document.
You can purchase this feature if you want our writers to sum up your paper in the form of a concise and well-articulated summary.
You don’t have to worry about plagiarism anymore. Get a plagiarism report to certify the uniqueness of your work.
Join us for the best experience while seeking writing assistance in your college life. A good grade is all you need to boost up your academic excellence and we are all about it.
We create perfect papers according to the guidelines.
We seamlessly edit out errors from your papers.
We thoroughly read your final draft to identify errors.
Work with ultimate peace of mind because we ensure that your academic work is our responsibility and your grades are a top concern for us!
Dedication. Quality. Commitment. Punctuality
Here is what we have achieved so far. These numbers are evidence that we go the extra mile to make your college journey successful.
We have the most intuitive and minimalistic process so that you can easily place an order. Just follow a few steps to unlock success.
We understand your guidelines first before delivering any writing service. You can discuss your writing needs and we will have them evaluated by our dedicated team.
We write your papers in a standardized way. We complete your work in such a way that it turns out to be a perfect description of your guidelines.
We promise you excellent grades and academic excellence that you always longed for. Our writers stay in touch with you via email.