# Sorting

Sorting algorithms are a fundamental part of computer science. Being able to sort through a large data set quickly and efficiently is a problem you will be likely to encounter on nearly a daily basis.

Here are the main sorting algorithms:

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
QuicksortArrayO(n log(n))O(n log(n))O(n^2)O(n)
Merge SortArrayO(n log(n))O(n log(n))O(n log(n))O(n)
HeapsortArrayO(n log(n))O(n log(n))O(n log(n))O(1)
Bubble SortArrayO(n)O(n^2)O(n^2)O(1)
Insertion SortArrayO(n)O(n^2)O(n^2)O(1)
Select SortArrayO(n^2)O(n^2)O(n^2)O(1)
Bucket SortArrayO(n+k)O(n+k)O(n^2)O(nk)

# Searching

Another crucial skill to master in the field of computer science is how to search for an item in a collection of data quickly. Here are the most common searching algorithms, their corresponding data structures, and time complexities.

Here are the main searching algorithms:

AlgorithmData StructureTime Complexity - AverageTime Complexity - WorstSpace Complexity - Worst
Depth First SearchGraph of |V| vertices and |E| edges-O(|E|+|V|)O(|V|)
Breadth First SearchGraph of |V| vertices and |E| edges-O(|E|+|V|)O(|V|)
Binary SearchSorted array of n elementsO(log(n))O(log(n))O(1)
Brute ForceArrayO(n)O(n)O(1)
Bellman-FordGraph of |V| vertices and |E| edgesO(|V||E|)O(|V||E|)O(|V|)

# Graphs

Graphs are an integral part of computer science. Mastering them is necessary to become an accomplished software developer. Here is the data structure analysis of graphs:

Incidence ListO(|V|+|E|)O(1)O(1)O(|E|)O(|E|)O(|E|)