Minimum Spanning Trees - Kruskals

Tries

Single source shortest path algorithms

Dijkstra's
The heap functions are same as in Prims

Data-structures for disjoint sets

Minimum Spanning Trees - Prims

Graph Traversal

Recursive DFS
Iterative DFS
BFS

AVL Trees

Radix Sort

Counting Sort

Binary Search Trees

Threaded Binary Trees

Iterative Tree Traversals

Circular Queue

Max heap / Max Priority Queues

Quick Sort

partitionArray() partitions the array such that all the elements placed to the left of a selected pivot element are less than the pivot element and all elements to the right are more than the pivot. After every call to partitionArray, the pivot element is placed in its correct postion. The algorithm exhibits O(n^2) behavior for worst case as the partitioning function returns one subarray with n-1 elements. To fix this problem the pivot element is usually a randomly chosen element and then placed at the end of the array.

Time Complexity: O(nlogn) Best and Average Case
                 O(n^2) Worst case

Heap Sort

Merge Sort

This is an algorithm based on the divide and conquer principle. The algorithm divides the problem of sorting an array into smaller problems of sorting smaller arrays. These smaller sorted arrays are then merged into bigger sorted arrays in the conquer phase until we have a completely sorted array.

Time Complexity: O(nlogn) - From the recurrence tree of this algorithm, there are atmost logn levels of this binary tree. The cost of merging the small sorted arrays is n at each level, thus nlogn.

Space Complexity: O(nlogn)

Selection Sort

One of the simplest sorting algorithms to implement. The idea is to select the smallest element from the unsorted array and place it in its right position. With every iteration, the unsorted array gets shorter until there is no element to place in its correct position.

Time Complexity: O(n^2)
Space Complexity: O(1)

Insertion Sort

This is an insanely inefficient but simple to implement sorting algorithm. The analogy for this algorithm can be drawn from the card game. Imagine the cards lying face down on the table. You pick cards one by one from the table and arrange them in a sorted order in your hand. For every card after the second card picked, put that card in its right place by comparing that card with the cards in your hand from right to left.

Time Complexity: Average and Worst Case is O(n^2)

                 Best Case is O(n)

Space Complexity: O(1)