KellyHaTran/Insertion-Sort-Visualizer
0
1---2title: insertion-sort-visualizer3emoji: 👀4colorFrom: indigo5colorTo: blue6sdk: gradio7sdk_version: 6.1.08app_file: app.py9pinned: false10---11***Algorithm Name: Insertion Sort Visualizer***12 13*Why was Insertion Sort Chosen?*14 15I chose to implement Insertion Sort because the visualizer provided in class felt difficult to follow and did not clearly show how values move during the sorting process. By building my own visualizer, I was able to present each comparison, shift, and insertion step in a way that is much easier to understand.16 17Insertion Sort is also an excellent algorithm for learning purposes because:18 19 20- It mirrors how humans naturally sort items (like cards in a hand).21- It allows students to observe step-by-step changes in the array.22- It is simple enough for beginners, yet still demonstrates key algorithmic ideas such as comparisons, shifting, and incremental ordering.23- Its behavior is easy to visualize, making it ideal for an educational tool.24 25Overall, creating my own visualizer provides a clear, intuitive, and accessible representation of the algorithm, helping students understand not just the final result but the process of sorting itself.26 27*Overall Problem*28 29An interactive way to teach and visualize insertion sort:30- Show how the algorithm takes one element at a time.31- Show how it compares and shifts elements.32- Let the user follow what happens to a specific number they care about.33- Present feedback in plain English instead of just code.34 35*How the Code Solves It*361. Generate List37 - Use Python’s random.sample to create 10 unique integers between 1 and 49.38 - Show this list in a read-only textbox labeled List.392. Insertion Sort with Logging40 - Copy the generated list into a local arr so the original can still be displayed.41 - Run standard insertion sort.42 At each pass:43 - Log what “current value” we are inserting.44 - Log which values it is being compared to.45 - Log when shifting stops.46 - Log the full array after the pass, plus where the tracked number ended up (if provided).473. User Interface (Gradio)48 - gen_btn triggers generate_list.49 - run_btn triggers insertion_sort_on_state.50 Multiple textboxes show:51 - The original unsorted list.52 - Up to MAX_STEPS messages describing the passes.53 - A final result summary.54 55 56***Computational Thinking: Four Pillars***57 58*Decomposition*59Break the problem into smaller, manageable subtasks:60 1. State management61 - arr_state (Gradio State) stores the current unsorted list between button clicks.62 2. List generation63 - Function generate_list():64 - Produces data: a list of integers.65 - Produces display: a string Random Unsorted List:\n[...].66 3. Sorting logic67 Function insertion_sort_on_state():68 - Validates that the list exists.69 - Reads the optional user-provided number to track.70 - Runs insertion sort on a copy of the list.71 4. Step logging72 - Inner helper log_step(msg):73 - Appends explanatory messages to steps until MAX_STEPS is reached.74 5. Presentation75 Return values from insertion_sort_on_state are mapped to:76 77 - list_box (original list text)78 - A series of step_boxes (detailed messages)79 - result_box (summary of sorted list and tracked index)80 81*Pattern Recognition*82 83Insertion sort itself has a clear repeating pattern:84 85 For each index i from 1 to n-1:86 1. Take the value at index i (called current_value).87 2. Look left from j = i - 1 down to 0:88 - While items are bigger than current_value, shift them one spot to the right.89 3. Insert current_value in the first spot where it’s not smaller than the item to its left.90 91*Abstraction*92- hide low-level details and present a simplified mental model:93 1. Hidden from user:94 - Python syntax (for loops, indices, list assignments).95 - Internal storage (arr_state, steps).96 - Edge cases like empty lists and type casting.97 2. Shown to user:98 - Natural language explanations:99 - “Compare 27 with arr[2] = 43.”100 - “Stop shifting: 27 ≥ arr[1] = 35.”101 Full array after each pass:102 - They see how the left part becomes sorted over time.103 3. Simple description in the UI:104 - “Press ‘Generate List’ to generate a random list. Pick a number to track…”105- Abstraction allows the app to be used by someone who doesn’t know Python at all—they just need to understand that we are sorting numbers and following the steps.106 107*Algorithmic Thinking*108 109 ```110 111PSEUDOCODE FOR INSERTION SORT VISUALIZER112 113 114CONSTANT MAX_STEPS = 200115 116------------------------------------------------------------117PROCEDURE GenerateList()118 arr ← randomly select 10 unique integers from range 1..49119 display_text ← "Random Unsorted List:\n" + arr120 RETURN (display_text, arr)121END PROCEDURE122------------------------------------------------------------123 124 125 126------------------------------------------------------------127PROCEDURE InsertionSortOnState(user_number, custom_list_str, arr_state)128 arr ← null129 source_label ← ""130 131 132 # Stage A: Determine which list to use133 134 135 IF custom_list_str is not empty THEN136 TRY137 tokens ← replace commas with spaces in custom_list_str138 tokens ← split tokens on spaces139 arr ← convert each token to an integer140 source_label ← "Custom List"141 CATCH conversion error142 RETURN ("Error: invalid list input",143 empty_step_boxes(MAX_STEPS),144 "Invalid custom list input.")145 END TRY146 END IF147 148 IF arr = null THEN149 IF arr_state is empty THEN150 RETURN ("Please generate a list or enter your own.",151 empty_step_boxes(MAX_STEPS),152 "No list to sort.")153 ELSE154 arr ← copy of arr_state155 source_label ← "Random Unsorted List"156 END IF157 END IF158 159 original_display ← source_label + ":\n" + arr160 n ← length(arr)161 162 163 # Stage B: Optional tracked number164 165 highlight ← null166 IF user_number provided THEN167 TRY highlight ← integer(user_number)168 CATCH → highlight remains null169 END IF170 171 172 # Stage C: Perform insertion sort while logging steps173 174 steps ← empty list175 176 FUNCTION LogStep(text)177 append text to steps178 END FUNCTION179 180 FOR i FROM 1 TO n-1 DO181 current_value ← arr[i]182 j ← i - 1183 184 LogStep("Pass " + i + ": take value " + current_value +185 " from index " + i + " and insert into sorted portion.")186 187 WHILE j ≥ 0 DO188 LogStep("Compare " + current_value +189 " with arr[" + j + "] = " + arr[j])190 191 IF arr[j] > current_value THEN192 LogStep("Shift: " + arr[j] + " > " + current_value +193 ", move " + arr[j] + " to index " + (j+1))194 arr[j+1] ← arr[j]195 j ← j - 1196 ELSE197 LogStep("No shift needed: " + current_value +198 " ≥ " + arr[j] + " (stop shifting).")199 BREAK200 END IF201 END WHILE202 203 LogStep("Insert " + current_value +204 " at position " + (j+1))205 arr[j+1] ← current_value206 207 message ← "After pass " + i + ": " + arr208 209 IF highlight ≠ null AND highlight is in arr THEN210 index ← index of highlight in arr211 message ← message + 212 " | Tracked number " + highlight +213 " is at index " + index214 END IF215 216 LogStep(message)217 END FOR218 219 220 # Stage D: Final summary message221 222 IF highlight ≠ null AND highlight in arr THEN223 final_msg ← "Sorted: " + arr +224 ", tracked number " + highlight +225 " is at index " + index_of(highlight)226 ELSE IF highlight ≠ null THEN227 final_msg ← "Sorted: " + arr +228 ", tracked number " + highlight +229 " is not in the list"230 ELSE231 final_msg ← "Sorted: " + arr232 END IF233 234 235 # Stage E: Map steps into UI step boxes236 237 step_updates ← empty list238 239 FOR i FROM 0 TO MAX_STEPS-1 DO240 IF i < length(steps) THEN241 append update(value = steps[i], visible = true)242 ELSE243 append update(value = "", visible = false)244 END IF245 END FOR246 247 RETURN (original_display,248 step_updates...,249 final_msg)250 251END PROCEDURE252------------------------------------------------------------253 254UI SUMMARY 255 256 257User clicks "Generate List":258 - Calls GenerateList259 - Displays the list260 - Saves arr_state261 262User enters list or number (optional) and clicks "Run Insertion Sort":263 - Calls InsertionSortOnState264 - Shows:265 - Chosen list266 - A dynamic number of step boxes267 - Final result (sorted array + tracked number index)268------------------------------------------------------------269 ```270 271 272Time complexity:273 - Worst case: O(n²) comparisons/shifts (e.g., when the list is in descending order).274 - Best case: O(n) when the list is already sorted (no shifting inside the while loop).275 276 277 278***Test And Verify***279 280*Random generated list with tracked number* 281 282283284 285 286*Custom list with tracked number* 287 288289290 291*Random list with no tracked number*292 293294295 296*Custom list with no tracked number*297 298299300 301*Custom list with invalid input*302 303304 305*Random list with tracked number not in list*306 307308309 310*Custom list with tracked number not in list*311 312313314 315*Custom list with spaces instead of commas*316 317318319 320 321***Steps to Run***3221. Install dependencies:323 324 325 ```326 pip install gradio327 ```328 329 3302. Save code as app.py3313. Run code:332 python app.py333 334***Hugging Face link***: https://huggingface.co/spaces/KellyHaTran/Insertion-Sort-Visualizer335 336***Author & Acknowledgment***337 338 339Author: Kelly Ha Tran340 341 342Algorithm implemented: Insertion Sort343 344 345Language / Frameworks:346- Python 347- Gradio