Bellman-Ford

The Bellman-Ford algorithm is a graph algorithm used for finding the shortest paths from a single source vertex to all other vertices in a weighted graph, even if the graph contains negative weight edges. It works as follows: 1. Initialization: Set the distance to the source vertex to zero and the distances to all other vertices to infinity. 2. Relaxation: For each edge in the graph, update the distance to the destination vertex if the distance to the source vertex plus the edge weight is less than the current distance to the destination vertex. Repeat this process for a total of |V| - 1 times, where |V| is the number of vertices in the graph. 3. Negative Cycle Detection: Check for negative weight cycles by iterating through all edges once more. If any distance can be updated, a negative weight cycle exists in the graph. The Bellman-Ford algorithm is slower than Dijkstras algorithm, with a time complexity of O(V * E), but it is more versatile as it can handle graphs with negative weight edges.

Dijkstra's

Dijkstras algorithm is a popular algorithm used in computer science and graph theory to find the shortest path from a starting node (source) to all other nodes in a weighted graph. Here is a brief summary: 1. Initialization: Start with a graph where each node has a tentative distance. Set the distance of the source node to 0 and all other nodes to infinity. Create a priority queue to keep track of the nodes to be evaluated, initially containing only the source node. 2. Node Selection: Select the node with the smallest tentative distance (initially the source node) and consider all its neighbors. 3. **Distance Update**: For each neighboring node, calculate the distance from the source node to that neighbor through the current node. If this calculated distance is less than the current known distance, update the tentative distance of the neighboring node. 4. **Marking Processed Nodes**: Once all neighbors of the current node have been considered, mark the current node as processed. A processed node will not be checked again. 5. **Repeat**: Repeat the process of selecting the node with the smallest tentative distance, updating distances, and marking nodes as processed until all nodes have been processed or the destination nodes shortest distance is found. 6. **Completion**: The algorithm ends when all nodes have been processed or the smallest distance among the unprocessed nodes is infinity (indicating that the remaining nodes are not reachable from the source). The algorithm guarantees the shortest path in graphs with non-negative weights and has a time complexity of \(O((V + E) \log V)\) using a priority queue, where \(V\) is the number of vertices and \(E\) is the number of edges.

Bubble Sort

Bubble sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. The algorithm gets its name because smaller elements "bubble" to the top (beginning of the list) while larger elements sink to the bottom (end of the list) with each pass through the list. Key Characteristics: - Time Complexity: O(n²) in the worst and average cases, where n is the number of elements. - Space Complexity: O(1), as it requires only a constant amount of additional space. - Stability: Bubble sort is a stable sort, meaning that it preserves the relative order of equal elements. - Adaptability: It performs best when the list is nearly sorted, as it can detect if the list is already sorted and terminate early. Algorithm Steps: 1. Compare each pair of adjacent elements. 2. Swap them if they are in the wrong order. 3. Repeat the process for all elements in the list. 4. Continue until no swaps are needed, indicating that the list is sorted.

Insertion Sort

Insertion sort is a simple and intuitive comparison-based sorting algorithm. It builds the sorted list one element at a time by repeatedly taking the next unsorted element and inserting it into its correct position within the sorted portion of the list. Key Characteristics: -Time Complexity: O(n²) in the worst and average cases, but O(n) in the best case when the list is already sorted or nearly sorted. -Space Complexity: O(1), as it requires only a constant amount of additional space. -Stability: Insertion sort is a stable sort, meaning that it preserves the relative order of equal elements. -Adaptability: It performs efficiently for small data sets or nearly sorted lists, making it useful for applications where the data is frequently partially sorted. Algorithm Steps: 1. Start with the second element (consider the first element as a sorted sublist of one element). 2. Compare the current element with the elements in the sorted sublist. 3. Shift all elements in the sorted sublist that are greater than the current element one position to the right. 4. Insert the current element into its correct position. 5. Repeat the process for all elements in the list. By the end of the process, the list will be fully sorted.

Selection Sort

Selection sort is a straightforward comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted portion of the list and swapping it with the first unsorted element, effectively growing the sorted portion of the list one element at a time. Key Characteristics: -Time Complexity: O(n²) for all cases (worst, average, and best), where n is the number of elements. -Space Complexity: O(1), as it requires only a constant amount of additional space. -Stability: Selection sort is not stable, meaning that it does not necessarily preserve the relative order of equal elements. -Adaptability: It is not adaptive, meaning that its performance does not improve with nearly sorted lists. Algorithm Steps: 1. Start with the first element and consider it the minimum. 2. Iterate through the remaining elements to find the smallest element. 3. Swap the smallest element found with the first unsorted element. 4. Move the boundary of the sorted and unsorted portions one element to the right. 5. Repeat the process for the remaining unsorted elements. By the end of the process, the entire list will be sorted.

Heap Sort

Heap sort is an efficient comparison-based sorting algorithm that uses a binary heap data structure. It is particularly noted for its good worst-case time complexity. Key Characteristics: -Time Complexity: O(n log n) for all cases (worst, average, and best), where n is the number of elements. -Space Complexity: O(1) for the in-place version, as it requires only a constant amount of additional space. -Stability: Heap sort is not stable, meaning that it does not necessarily preserve the relative order of equal elements. -Adaptability: It is not adaptive, meaning that its performance does not improve with nearly sorted lists. Algorithm Steps: 1. Build a Max Heap: Arrange the array elements into a max heap, where the largest element is at the root. 2. Extract Elements: Swap the root of the heap with the last element in the array, then reduce the heap size by one. 3. Heapify: Restore the max heap property by heapifying the root. 4. Repeat steps 2 and 3 until all elements are extracted and the array is sorted. By the end of the process, the entire list will be sorted in ascending order. Detailed Steps: 1. Build Max Heap: - Convert the array into a max heap by starting from the last non-leaf node and heapifying each node up to the root. 2. Heap Sort: - Swap the root (maximum element) with the last element of the heap. - Decrease the heap size by one. - Heapify the root to ensure the max heap property is maintained. - Repeat until the heap size is reduced to one. Heap sort's use of a binary heap ensures its efficiency and makes it suitable for large datasets.

Quick Sort

Quick sort is a highly efficient and widely used comparison-based sorting algorithm. It employs a divide-and-conquer strategy to sort elements by partitioning the array into subarrays and recursively sorting them. Key Characteristics: - Time Complexity: - Average case: O(n log n) - Worst case: O(n²), which occurs when the pivot selection is poor (e.g., always picking the smallest or largest element). - Space Complexity: O(log n) due to the recursive stack space. - Stability: Quick sort is not stable, meaning it does not necessarily preserve the relative order of equal elements. - Adaptability: Quick sort is generally efficient for large datasets and can be optimized with good pivot selection strategies. Algorithm Steps: 1.Choose a Pivot: Select an element from the array as the pivot (commonly the first element, last element, or the median). 2.Partition: Rearrange the elements so that all elements less than the pivot are on the left, and all elements greater than the pivot are on the right. 3.Recursively Apply: Apply the same process to the left and right subarrays. Detailed Steps: 1. Partitioning: - Select a pivot element. - Rearrange the array such that elements less than the pivot are on the left and elements greater than the pivot are on the right. This may involve swapping elements. - After partitioning, the pivot is in its final position. 2. Recursion: - Recursively apply the above steps to the subarray of elements with smaller values and the subarray of elements with larger values. Example: 1. Choose a pivot element. 2. Partition the array around the pivot. 3. Recursively sort the subarrays. By repeatedly partitioning and sorting subarrays, quick sort efficiently sorts the entire array. Its performance is heavily dependent on the pivot selection method, and techniques such as randomized pivoting or the median-of-three rule can help improve its efficiency.