[go: up one dir, main page]
Scribd
Upload
5 views2 pages

Rom Graphviz Import Digraph

The document contains a Python implementation of the merge sort algorithm, including functions for visualizing the sorting process using Graphviz. It defines a recursive approach to sort an array and provides a method to merge two sorted arrays. An example usage is included, demonstrating the visualization and sorting of a sample input array.

Uploaded by

vanshikabhadani7
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
5 views2 pages

Rom Graphviz Import Digraph

The document contains a Python implementation of the merge sort algorithm, including functions for visualizing the sorting process using Graphviz. It defines a recursive approach to sort an array and provides a method to merge two sorted arrays. An example usage is included, demonstrating the visualization and sorting of a sample input array.

Uploaded by

vanshikabhadani7
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

rom graphviz import Digraph

from IPython.display import display

def visualize_merge_sort(arr, depth=0, parent=None, dot=None):


if dot is None:
dot = Digraph()

if len(arr) <= 1:
dot.node(str(arr), label=str(arr), shape='ellipse')
dot.edge(parent, str(arr))
return dot

mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]

# Create nodes for current splits


dot.node(str(arr), label=str(arr), shape='rectangle')
if parent is not None:
dot.edge(parent, str(arr))

# Visualize left half


visualize_merge_sort(left_half, depth + 1, str(arr), dot)
# Visualize right half
visualize_merge_sort(right_half, depth + 1, str(arr), dot)

return dot

def merge(B, C):


p = len(B)
q = len(C)
A = [0] * (p + q) # Create an array to hold the merged result
i = j = k = 0

while i < p and j < q:


if B[i] <= C[j]:
A[k] = B[i]
i += 1
else:
A[k] = C[j]
j += 1
k += 1

while i < p:
A[k] = B[i]
i += 1
k += 1

while j < q:
A[k] = C[j]
j += 1
k += 1

return A

def merge_sort(arr):
if len(arr) <= 1:
return arr

mid = len(arr) // 2
left_half = merge_sort(arr[:mid]) # Recursively sort the left half
right_half = merge_sort(arr[mid:]) # Recursively sort the right half

return merge(left_half, right_half) # Merge the sorted halves

# Example usage
input_array = [8, 3, 2, 9, 7, 1, 5, 4]

# Visualize merge sort


dot = visualize_merge_sort(input_array)
display(dot)

# Perform merge sort


sorted_array = merge_sort(input_array)
print("Sorted Array:", sorted_array)

You might also like