madisonmac789/MergeSortVisualization
0
1import gradio as gr2import matplotlib.pyplot as plt3from io import BytesIO4from PIL import Image5import random6 7# --- Helper Functions ---8def parse_numbers(list_str: str):9 if not list_str or list_str.strip() == "":10 raise ValueError("Input list is empty. Please enter at least one number.")11 parts = list_str.split(",")12 numbers = []13 for p in parts:14 p = p.strip()15 if p == "": continue16 try:17 number = int(p)18 except ValueError:19 raise ValueError(f"'{p}' is not a valid integer.")20 numbers.append(number)21 if len(numbers) == 0:22 raise ValueError("No valid numbers found. Please enter integers separated by commas.")23 return numbers24 25def generate_test_array(case: str, size=12):26 if case == "Best Case (Sorted)":27 return list(range(1, size + 1))28 elif case == "Worst Case (Reverse Sorted)":29 return list(range(size, 0, -1))30 elif case == "Average Case (Random)":31 return random.sample(range(1, size * 2), size)32 else:33 return []34 35# Visualization36def make_bar_image(values, title, highlight_indices=None):37 if highlight_indices is None: highlight_indices = []38 colors = ['#C1CCD4'] * len(values)39 for idx in highlight_indices:40 if 0 <= idx < len(values):41 colors[idx] = '#4F8BF9'42 fig, ax = plt.subplots(figsize=(4, 2.5))43 ax.bar(range(len(values)), values, color=colors)44 ax.set_xticks(range(len(values)))45 ax.set_xticklabels([str(int(v)) for v in values])46 ax.set_ylabel("Value")47 ax.set_title(title)48 fig.tight_layout()49 buf = BytesIO()50 fig.savefig(buf, format="png")51 plt.close(fig)52 buf.seek(0)53 return Image.open(buf)54 55# --- Merge Sort Algorithm ---56def merge(arr, low, mid, high, lines, visual_steps, depth):57 left_arr = arr[low:mid + 1]58 right_arr = arr[mid + 1:high + 1]59 i = j = 0; k = low60 indent = " " * depth61 lines.append(f"{indent}Merge: {left_arr} and {right_arr}") 62 active_indices = list(range(low, high + 1))63 visual_steps.append((f"Merge Start: Combining [{low}-{mid}] and [{mid+1}-{high}]", arr.copy(), active_indices))64 while i < len(left_arr) and j < len(right_arr):65 if left_arr[i] <= right_arr[j]: 66 arr[k] = left_arr[i]67 lines.append(f"{indent} -> take {left_arr[i]} from left")68 i += 169 else: 70 arr[k] = right_arr[j]71 lines.append(f"{indent} -> take {right_arr[j]} from right")72 j += 173 k += 174 while i < len(left_arr): 75 arr[k] = left_arr[i]76 lines.append(f"{indent} -> append remaining {left_arr[i]} from left")77 i += 1; k += 178 while j < len(right_arr): 79 arr[k] = right_arr[j]80 lines.append(f"{indent} -> append remaining {right_arr[j]} from right")81 j += 1; k += 182 lines.append(f"{indent}Result of segment [{low}-{high}]: {arr[low:high+1]}")83 visual_steps.append((f"Merge Complete: Segment [{low}-{high}] is sorted", arr.copy(), active_indices))84 85def merge_sort_trace(arr, low, high, lines, visual_steps, depth=0):86 indent = " " * depth87 if low >= high:88 lines.append(f"{indent}Base case: List element at index {low} is sorted: {arr[low]}")89 visual_steps.append((f"Base Case: Element at index {low}", arr.copy(), [low]))90 return91 mid = (low + high) // 292 lines.append(f"{indent}Call merge_sort on segment [{low}-{high}]: {arr[low:high+1]}")93 visual_steps.append((f"Splitting: Active Segment [{low}-{high}]", arr.copy(), list(range(low, high + 1))))94 lines.append(f"{indent}Split Left: Recurse on [{low}-{mid}]")95 merge_sort_trace(arr, low, mid, lines, visual_steps, depth + 1)96 lines.append(f"{indent}Split Right: Recurse on [{mid+1}-{high}]")97 merge_sort_trace(arr, mid + 1, high, lines, visual_steps, depth + 1)98 merge(arr, low, mid, high, lines, visual_steps, depth)99 100 101def run_merge_sort(custom_list_str: str, case_selection: str, show_steps: bool):102 if case_selection == "Define Custom Array":103 try: numbers = parse_numbers(custom_list_str)104 except ValueError as e: return f"❌ Input error: {e}", "", ""105 else: numbers = generate_test_array(case_selection)106 107 if not numbers: return "⚠️ Please define a custom list or select a test case.", "", ""108 109 full_arr = numbers.copy(); lines = []; visual_steps = []110 visual_steps.append(("Start: Unsorted Array", full_arr.copy(), list(range(len(full_arr)))))111 merge_sort_trace(full_arr, 0, len(full_arr) - 1, lines, visual_steps, depth=0)112 sorted_list = full_arr113 114 summary_lines = [f"✅ Merge Sort completed.", f"Input type: **{case_selection}**", f"Original list: {numbers}", f"Sorted list (ascending): {sorted_list}"]115 summary = "\n".join(summary_lines)116 117 # Generate the teaching view trace118 teaching_view = "\n".join(lines)119 120 images = []121 for idx, (label, state, highlights) in enumerate(visual_steps, start=1):122 title = f"Step {idx}: {label}" 123 img = make_bar_image(state, title, highlights)124 images.append(img)125 126 return summary, teaching_view, images127 128# --- CUSTOM THEME DEFINITION ---129 130custom_theme = gr.themes.Soft(131 primary_hue="blue", 132 secondary_hue="gray",133).set(134 body_background_fill="#E0FFFF", 135 block_background_fill="#FFFFFF", 136 button_primary_background_fill="#228B22", 137 button_primary_background_fill_hover="#1F7A1F", 138 button_primary_text_color="white", 139 color_accent_soft="#228B22",140)141 142# --- Gradio Interface Setup ---143 144with gr.Blocks(title="Merge Sort Visualizer") as demo: 145 gr.Markdown("## 📊 Recursive Merge Sort Visualizer")146 147 # Define outputs148 summary_output = gr.Textbox(label="Summary and Test Case Results", lines=10)149 # Set visible=True by default to match the checkbox's initial value150 teaching_view_output = gr.Textbox(label="Teaching View: Merge Sort Steps", lines=20, visible=True) 151 gallery_output = gr.Gallery(152 label="Visual Merge Sort (Click through the steps below!)",153 columns=1, 154 rows=1,155 height='auto',156 preview=False157 )158 159 with gr.Row():160 # Column 1: Visualization (Left Side)161 with gr.Column(scale=2):162 gr.Markdown("### Visualization Trace (Step-by-Step)")163 gallery_output 164 165 # Column 2: Inputs and Text Outputs (Right Side)166 with gr.Column(scale=1):167 gr.Markdown("### Controls and Results")168 169 # Input Controls170 case_selection_input = gr.Radio(171 ["Best Case (Sorted)", "Worst Case (Reverse Sorted)", "Average Case (Random)", "Define Custom Array"],172 label="1. Select Input Array Type",173 value="Average Case (Random)",174 )175 custom_list_input = gr.Textbox(176 label="2. Custom Array Input (e.g. 5, 2, 4, 7, 1, 3)",177 placeholder="Enter numbers separated by commas",178 lines=1,179 )180 show_steps_checkbox = gr.Checkbox(181 label="3. Show detailed console-like trace in Teaching View",182 value=True,183 )184 185 # Action Button186 run_button = gr.Button("▶️ Run Merge Sort and Visualize")187 188 gr.Markdown("---")189 190 # Outputs191 summary_output 192 teaching_view_output 193 194 # Ensure the checkbox controls the visibility of the teaching view195 def update_teaching_view_visibility(checked):196 return gr.update(visible=checked)197 198 show_steps_checkbox.change(199 update_teaching_view_visibility, 200 [show_steps_checkbox],201 [teaching_view_output]202 )203 204 # Define the interaction flow205 run_button.click(206 fn=run_merge_sort,207 inputs=[custom_list_input, case_selection_input, show_steps_checkbox],208 outputs=[summary_output, teaching_view_output, gallery_output]209 )210 211if __name__ == "__main__":212 demo.launch(theme=custom_theme)