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

Algorithm | Data Structure | Time Complexity - Best | Time Complexity - Average | Time Complexity - Worst | Worst Case Auxiliary Space Complexity |
---|---|---|---|---|---|

Quicksort | Array | O(n log(n)) | O(n log(n)) | O(n^2) | O(n) |

Merge Sort | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |

Heapsort | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |

Bubble Sort | Array | O(n) | O(n^2) | O(n^2) | O(1) |

Insertion Sort | Array | O(n) | O(n^2) | O(n^2) | O(1) |

Select Sort | Array | O(n^2) | O(n^2) | O(n^2) | O(1) |

Bucket Sort | Array | O(n+k) | O(n+k) | O(n^2) | O(nk) |

Radix Sort | Array | O(nk) | O(nk) | O(nk) | O(n+k) |

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

Algorithm | Data Structure | Time Complexity - Average | Time Complexity - Worst | Space Complexity - Worst |
---|---|---|---|---|

Depth First Search | Graph of |V| vertices and |E| edges | - | O(|E|+|V|) | O(|V|) |

Breadth First Search | Graph of |V| vertices and |E| edges | - | O(|E|+|V|) | O(|V|) |

Binary Search | Sorted array of n elements | O(log(n)) | O(log(n)) | O(1) |

Brute Force | Array | O(n) | O(n) | O(1) |

Bellman-Ford | Graph of |V| vertices and |E| edges | O(|V||E|) | O(|V||E|) | O(|V|) |