This Fortran program implements the Merge Sort algorithm using recursion. Merge Sort is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the two sorted...

The provided Fortran code implements a recursive Merge Sort algorithm. The `merge_sort` subroutine divides the array into two halves until the base case (an array segment of size 0 or 1) is reached. The `merge` subroutine then combines these sorted halves. It uses a temporary array to store the merged elements, comparing elements from both halves and placing the smaller one into the temporary array. After all elements are merged, they are copied back to the original array segment. The time complexity is O(n log n) for all cases (best, average, worst) because the array is always divided and merged. The space complexity is O(n) due to the temporary array used in the merge step. Edge cases like empty arrays and single-element arrays are handled by the base case of the recursion. The invariant for the `merge` subroutine is that when it begins, `a(low...mid)` and `a(mid+1...high)` are sorted, and when it finishes, `a(low...high)` is sorted. The recursive structure ensures that the entire array is eventually sorted.

PROGRAM merge_sort_recursive_example DECLARE integer array arr INITIALIZE arr with values PRINT original array CALL merge_sort(arr, 1, size(arr)) PRINT sorted array TEST with empty array TEST with single-element array TE...

This Fortran program implements Heap Sort, a comparison-based sorting algorithm that uses a binary heap data structure. It first builds a max-heap from the input array, then repeatedly extracts the maximum element from t...

Heap sort has a time complexity of O(n log n) for all cases (best, average, and worst). Building the initial heap takes O(n) time, and each of the n extraction operations takes O(log n) time. The space complexity is O(1) because it sorts the array in-place. Edge cases include empty arrays or arrays with a single element (handled by loop conditions), and arrays with duplicate elements. The correctness relies on the `heapify` procedure maintaining the max-heap property: the value of a parent node is always greater than or equal to the values of its children. This ensures that the largest element is always at the root.

FUNCTION heap_sort(array, n): FOR i FROM n/2 DOWN TO 1: heapify(array, n, i) FOR i FROM n DOWN TO 2: SWAP array[1], array[i] heapify(array, i-1, 1) FUNCTION heapify(array, n, i): largest = i left = 2*i right = 2*i + 1 IF...

This Fortran program implements the Quick Sort algorithm, an efficient, comparison-based sorting algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays,...

Quick sort has an average-case time complexity of O(n log n) and a worst-case complexity of O(n^2). The worst case occurs when the pivot selection consistently results in highly unbalanced partitions (e.g., always picking the smallest or largest element). The space complexity is O(log n) on average due to the recursion stack, and O(n) in the worst case. Edge cases include empty arrays, arrays with one element (handled by the base case `low < high`), and arrays with duplicate elements. The correctness relies on the partition function correctly placing the pivot and ensuring all elements to its left are smaller and all to its right are larger.

FUNCTION quick_sort(array, low, high): IF low < high: pivot_index = partition(array, low, high) quick_sort(array, low, pivot_index - 1) quick_sort(array, pivot_index + 1, high) FUNCTION partition(array, low, high): pivot...

This Fortran program implements Depth-First Search (DFS), a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a given node and explores each neighbor recursive...

DFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited at most once. The space complexity is O(V) in the worst case for the recursion stack (or an explicit stack if implemented iteratively). Edge cases include disconnected graphs (DFS will only explore the component containing the start node), graphs with cycles (handled by the `visited` array), and starting DFS from an isolated node. The correctness relies on the recursive structure, which naturally explores depth-first, and the `visited` array preventing infinite loops in cyclic graphs.

FUNCTION dfs(graph, adj_list, visited, num_nodes, current_node): Mark current_node as visited PRINT current_node FOR each neighbor v of current_node (from adj_list[current_node]): IF v is not visited: dfs(graph, adj_list...

This Fortran program implements Dijkstra's algorithm to find the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights. It uses an adjacency matrix to represent the graph a...

Dijkstra's algorithm has a time complexity of O(V^2) when using an adjacency matrix and a simple linear scan to find the minimum distance vertex, or O(E + V log V) with a binary heap priority queue. The space complexity is O(V^2) for the adjacency matrix or O(V + E) if using an adjacency list. Edge cases include disconnected graphs (where some nodes will remain at infinite distance), graphs with zero-weight edges, and graphs with only one node. The algorithm's correctness is based on the greedy approach: at each step, it assumes the shortest path to the currently selected vertex is finalized and uses this to potentially find shorter paths to its neighbors. The invariant is that `dist(v)` always holds the shortest path found so far from the source to `v` among visited nodes.

FUNCTION dijkstra(graph, num_nodes, source_node): Initialize dist array of size num_nodes with infinity, dist[source_node] = 0 Initialize visited array of size num_nodes with false FOR i FROM 1 TO num_nodes - 1: Find ver...

This Fortran program implements the merge sort algorithm, a classic divide-and-conquer sorting technique. It recursively divides the input array into smaller halves until each subarray contains only one element, then mer...

Merge sort has a time complexity of O(n log n) in all cases (best, average, and worst) because it consistently divides the problem into halves and performs a linear-time merge operation. The space complexity is O(n) due to the need for temporary arrays during the merge step. Edge cases include empty arrays (handled by the base case of recursion where low >= high), arrays with one element, and arrays with duplicate elements. The correctness relies on the invariant that at each step of the merge, the subarrays being merged are already sorted, and the merge procedure correctly combines them into a larger sorted subarray. The recursive structure ensures that the entire array is eventually sorted.

FUNCTION merge_sort(array, low, high): IF low < high: mid = low + (high - low) / 2 merge_sort(array, low, mid) merge_sort(array, mid + 1, high) merge(array, low, mid, high) FUNCTION merge(array, low, mid, high): Create t...

This Fortran program implements Breadth-First Search (BFS), a graph traversal algorithm. It starts at a given node and explores the graph layer by layer, visiting all neighbors of the current node before moving to the ne...

BFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited at most once. The space complexity is O(V) in the worst case for storing the queue and the visited set. Edge cases include disconnected graphs (BFS will only explore the component containing the start node), graphs with cycles (handled by the `visited` array), and starting BFS from an isolated node. The correctness relies on the FIFO property of the queue, ensuring that nodes are visited in order of their distance from the source.

FUNCTION bfs(graph, adj_list, num_nodes, start_node): Initialize visited array of size num_nodes to false Initialize queue (array) and set front=1, rear=0 Mark start_node as visited Enqueue start_node WHILE queue is not...

This Fortran program implements a basic linear search algorithm. It iterates through an array sequentially, comparing each element with the target value. If a match is found, it returns the index of that element; otherwi...

Linear search has a time complexity of O(n) in the worst and average cases, as it may need to examine every element in the array. In the best case (element is the first one), it's O(1). The space complexity is O(1) as it only uses a few variables for iteration and comparison. Edge cases include searching in an empty array (the loop condition `i = 1, size` would handle this if `size` is 0 or negative, though Fortran arrays are typically 1-indexed and `size` would be positive), searching for the first or last element, and searching for an element that is not present in the array. The algorithm is correct because it systematically checks every possible position for the target value.

FUNCTION linear_search(array, size, value): FOR i FROM 1 TO size: IF array[i] == value: RETURN i RETURN -1