# Category Archives: Algorithm

## Bellman Ford

It works on negative cycle.

Implemented Code:

Time Complexity:

O([E].[V])

## Dijkstra

output:

Complexity:
O(E+V^2)

We are using here adjacency matrix list

## Topological Sort

code:

Output:

Time Complexity: O(V+E)
Space Complexity: O(V)
V for vertex E for edge

code courtesy:

Topological Sorting

I understood the theory but need to understand the code well later

## Bucket Sort

Pseudocode:

Implemented Code:

output:

Tuts:

Bucket Sort

Harumanchi Book implementation:

output:

Time and Space complexity: O(n)

best video:

pseudocode:

implementation: (I need to clear the radix sort part later..took help to implement)

Reference:

Radix Sort – Explanation, Pseudocode and Implementation

Time complexity: O(d*n)==O(n)
Where d is the digit of the number

## Counting Sort

Algo:

Implemented Code:

Counting Sort in C

Tuts:

Complexity:
Time: O(k)+O(n)+O(k)+O(n)=O(n) if K=O(n)
Space: O(n)

code:

code:

## Traversal in Binary Search Tree

Height of a binary tree:

Level Order BFS in Binary Search Tree:

output:

DFS in Preorder, Inorder, Postorder:

output:

code:

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

Implemented code:

output:

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)