Heapsort – C++

Heap sort is simple to implement, performs an O(n·lg(n)) in-place sort, but is not stable.

The first loop, the Θ(n) “heapify” phase, puts the array into heap order. The second loop, the O(n·lg(n)) “sortdown” phase, repeatedly extracts the maximum and restores heap order.
Example –

• Not stable
• O(1) extra space (see discussion)
• O(n·lg(n)) time
• Not really adaptive

Algorithm –

(1) for x on list L do
(2) INSERT(x, S);
(3) while not EMPTY(S) do begin
(4) y := MIN(S);
(5) writeln(y);
(6) DELETE(y, S)
end

Click Down For Program –

Floyd-Warshall’s Algorithm – C++

Floyd-Warshall algorithm known as Modified Warshall’s Algorithm used to solve the All-Pairs Shortest Path problem in Graphs. The Algorithm’s time complexity is O(n³) for a graph with n nodes.

Algorithm–

For each vertex v
	dist[v][v] ← 0
For each edge (u,v)
	dist[u][v] ← w(u,v) 
For k from 1 to |V|       
	for i from 1 to |V|
		for j from 1 to |V|
			if dist[i][k] + dist[k][j] < dist[i][j] then   
				dist[i][j] ← dist[i][k] + dist[k][j]  

Click below for Program –