Comparison-Based Sorting Algorithms

Bubble Sort

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.

• Simplest sorting algorithm
• Works well when input is nearly sorted
• Runtime
• When it is Reverse Sorted, Worst-case is O(n^2 )
• If it is sorted, Best-case is O(n)
• Expected case is O(n^2)

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.

• Does not change when everything to left is already sorted
• Works especially well when input is nearly sorted
• Runtime
• Considering reverse sorted input Worst-case O(n2)
• Considering sorted input. Best-caseO(n)

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.

• No element slided to left if Element is always greater or equal to element on left, running time in this case of each insertion sort will be O(n).
• If all the elements are smaller than element on left then the running time of each insertion will be O(n^2). g. (12, 8, 5, 3, 2).So reverse sorted array is worst case for insertion.

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.

• It is always required to scan the entire array even if it is perfectly sorted.
• Runtime
• Considering reverse-sorted input, Worst-case is O(n^2 )
• Considering sorted inpu ,Best-case is O( n^2)

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).

Insertion Sort

 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.

• Sort both parts. Sort both sides and glue the two sides together to produce output.

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

• Input array is divided in two halves and then two sorted halves are merged .Time complexity  will remain same for worst, average and best cases reason being array is divided in list of two halves which takes linear time. 

The diagram given below explains it 

• comparison based sorting technique
• It is based on Binary-Heap data sorting.
• Maximum element is taken and placed at the end(same as selection sort)
• Process is repeated till the sorted list is achieved.
• in-place algorithm
• unstable but can be made stable.
• Time Complexity:

1. heapify is O(Logn).
2. createAndBuildHeap() is O(n)
3. overall time Heap Sort is O(nLogn)

 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=∞

Selection Sort

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)]

Quick Sort

            (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:

1. x ∈ReachedSet
2. y∈UnReachedSet
3. e has smallest cost

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 }