Sorting Algorithms

Types of Sorting Algorithms:
- Comparison-based sorting: e.g., Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, Heap Sort
- Non-comparison sorting: e.g., Counting Sort, Radix Sort, Bucket Sort
Complexity Analysis:
- Time complexity: O(n^2) for Bubble Sort, Selection Sort, Insertion Sort; O(n log n) for Merge Sort, Quick Sort, Heap Sort
- Space complexity: O(1) for In-place sorting algorithms; O(n) for Not-in-place sorting algorithms
Stability: A sorting algorithm is stable if it maintains the relative order of equal sort elements

Types of Searching Algorithms:
- Linear Search: O(n) time complexity
- Binary Search: O(log n) time complexity; requires sorted array
Search in Unsorted Array: Linear Search
Search in Sorted Array: Binary Search

Types of Graphs:
- Weighted/Unweighted: edges have/have no weights
- Directed/Undirected: edges have/do not have direction
Graph Traversal:
- Breadth-First Search (BFS): traverse level by level
- Depth-First Search (DFS): traverse as far as possible along each branch
Shortest Path Algorithms:
- Dijkstra's Algorithm: O(|E| + |V|log|V|) time complexity
- Bellman-Ford Algorithm: O(|E| * |V|) time complexity
Minimum Spanning Tree Algorithms:
- Kruskal's Algorithm: O(|E|log|E|) time complexity
- Prim's Algorithm: O(|E|log|V|) time complexity

Memoization: storing solutions to subproblems to avoid redundancy
Tabulation: building solutions to subproblems in a bottom-up manner
Dynamic Programming Approach:
1. Define the problem and its subproblems
2. Identify the overlapping subproblems
3. Solve the subproblems and store the solutions
4. Combine the solutions to solve the original problem
Dynamic Programming Examples:
- \\Fibonacci Series
- Longest Common Subsequence
- Shortest Paths

Greedy Choice Property: locally optimal choice leads to a global optimum
Greedy Algorithm Approach:
1. Define the problem and its optimal substructure
2. Identify the greedy choice
3. Make the greedy choice and solve the subproblem
4. Combine the solutions to solve the original problem
Greedy Algorithm Examples:
- Huffman Coding
- Activity Selection Problem
- Coin Changing Problem

Comparison-based sorting includes algorithms like Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort.
Non-comparison sorting includes algorithms like Counting Sort, Radix Sort, and Bucket Sort.
Time complexity for Bubble Sort, Selection Sort, and Insertion Sort is O(n^2), while for Merge Sort, Quick Sort, and Heap Sort it is O(n log n).
Space complexity for In-place sorting algorithms is O(1) and for Not-in-place sorting algorithms is O(n).
A sorting algorithm is stable if it maintains the relative order of equal sort elements.

Linear Search has a time complexity of O(n).
Binary Search has a time complexity of O(log n) and requires a sorted array.
Search in Unsorted Array uses Linear Search.
Search in Sorted Array uses Binary Search.

Weighted graphs have edges with weights, while unweighted graphs have edges with no weights.
Directed graphs have edges with direction, while undirected graphs have edges with no direction.
Breadth-First Search (BFS) traverses the graph level by level.
Depth-First Search (DFS) traverses the graph as far as possible along each branch.
Dijkstra's Algorithm has a time complexity of O(|E| + |V|log|V|).
Bellman-Ford Algorithm has a time complexity of O(|E| * |V|).
Kruskal's Algorithm has a time complexity of O(|E|log|E|).
Prim's Algorithm has a time complexity of O(|E|log|V|).

Memoization involves storing solutions to subproblems to avoid redundancy.
Tabulation involves building solutions to subproblems in a bottom-up manner.
Dynamic Programming Approach involves defining the problem, identifying overlapping subproblems, solving and storing the solutions, and combining the solutions to solve the original problem.
Dynamic Programming Examples include Fibonacci Series, Longest Common Subsequence, and Shortest Paths.

Greedy Choice Property states that locally optimal choices lead to a global optimum.
Greedy Algorithm Approach involves defining the problem, identifying the optimal substructure, making the greedy choice, and combining the solutions to solve the original problem.
Greedy Algorithm Examples include Huffman Coding, Activity Selection Problem, and Coin Changing Problem.