Sorting Algorithms

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

Searching Algorithms

• 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

Graph Algorithms

• 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

Dynamic Programming

• 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 Algorithms

• 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

Sorting Algorithms

• 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.

Searching Algorithms

• 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.

Graph Algorithms

• 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|).

Dynamic Programming

• 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 Algorithms

• 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.