algorithms.py

"""
All of the following functions are generator functions.
They are used because they can print the process step-by-step, unlike traditional functions which take an input and show an output.
"""

def quicksort_generator(arr):
    """
    Quicksort implementation that yields the results, instead of simply returning a value.
    This way we can use it inside the canvas containing the visualizer
    """
    step_counter = [0]  # Using list to maintain reference across recursive calls
    
    def quicksort_recursive(arr, low, high, step_counter):
        if low < high:
            # Partition and get the generator and final pivot index
            partition_gen = partition(arr, low, high, step_counter)
            pivot_index = None
            for state in partition_gen:
                if 'pivot_index' in state:
                    pivot_index = state['pivot_index']
                else:
                    yield state
            
            # Recursively sort left and right subarrays
            if pivot_index is not None:
                yield from quicksort_recursive(arr, low, pivot_index - 1, step_counter)
                yield from quicksort_recursive(arr, pivot_index + 1, high, step_counter)
    
    def partition(arr, low, high, step_counter):
        pivot = arr[high]
        i = low - 1
        
        step_counter[0] += 1
        highlights = {high: 'pivot'}
        for j in range(low, high):
            highlights[j] = 'partitioning'
        
        yield {
            'array': arr[:],
            'highlights': highlights,
            'description': f'Partitioning: Pivot = {pivot} at index {high}',
            'step': step_counter[0]
        }
        
        for j in range(low, high):
            step_counter[0] += 1
            highlights = {high: 'pivot', j: 'comparing'}
            
            yield {
                'array': arr[:],
                'highlights': highlights,
                'description': f'Comparing {arr[j]} with pivot {pivot}',
                'step': step_counter[0]
            }
            
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
                
                if i != j:
                    step_counter[0] += 1
                    highlights = {high: 'pivot', i: 'comparing', j: 'comparing'}
                    yield {
                        'array': arr[:],
                        'highlights': highlights,
                        'description': f'Swapped {arr[j]} and {arr[i]}',
                        'step': step_counter[0]
                    }
        
        # Place pivot in correct position
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        step_counter[0] += 1
        
        highlights = {}
        for k in range(low, i + 1):
            highlights[k] = 'partitioning'
        highlights[i + 1] = 'pivot'
        for k in range(i + 2, high + 1):
            highlights[k] = 'partitioning'
        
        yield {
            'array': arr[:],
            'highlights': highlights,
            'description': f'Pivot {pivot} placed at position {i + 1}',
            'step': step_counter[0]
        }
        
        # Yield the final pivot index
        yield {'pivot_index': i + 1}
    
    # Start the sorting process
    yield from quicksort_recursive(arr, 0, len(arr) - 1, step_counter)
    
    # Final sorted state
    step_counter[0] += 1
    highlights = {i: 'sorted' for i in range(len(arr))}
    yield {
        'array': arr[:],
        'highlights': highlights,
        'description': 'Sorting complete!',
        'step': step_counter[0],
        'sorted': True
    }

def mergesort_generator(arr):
    """
    Mergesort implementation that yields states for visualization
    """
    step_counter = [0]
    
    def mergesort_recursive(arr, left, right, step_counter):
        if left < right:
            mid = (left + right) // 2
            
            step_counter[0] += 1
            highlights = {}
            for i in range(left, mid + 1):
                highlights[i] = 'merging'
            for i in range(mid + 1, right + 1):
                highlights[i] = 'partitioning'
            
            yield {
                'array': arr[:],
                'highlights': highlights,
                'description': f'Dividing array: [{left}:{mid}] | [{mid+1}:{right}]',
                'step': step_counter[0]
            }
            
            # Sort left half
            yield from mergesort_recursive(arr, left, mid, step_counter)
            
            # Sort right half
            yield from mergesort_recursive(arr, mid + 1, right, step_counter)
            
            # Merge the sorted halves
            yield from merge(arr, left, mid, right, step_counter)
    
    def merge(arr, left, mid, right, step_counter):
        """Merge two sorted subarrays"""
        # Create temporary arrays
        left_arr = arr[left:mid + 1]
        right_arr = arr[mid + 1:right + 1]
        
        step_counter[0] += 1
        highlights = {}
        for i in range(left, mid + 1):
            highlights[i] = 'merging'
        for i in range(mid + 1, right + 1):
            highlights[i] = 'partitioning'
        
        yield {
            'array': arr[:],
            'highlights': highlights,
            'description': f'Merging subarrays [{left}:{mid}] and [{mid+1}:{right}]',
            'step': step_counter[0]
        }
        
        # Merge the temp arrays back
        i = j = 0
        k = left
        
        while i < len(left_arr) and j < len(right_arr):
            step_counter[0] += 1
            
            highlights = {left + i: 'comparing', mid + 1 + j: 'comparing'}
            for m in range(left, k):
                highlights[m] = 'sorted'
            
            yield {
                'array': arr[:],
                'highlights': highlights,
                'description': f'Comparing {left_arr[i]} and {right_arr[j]}',
                'step': step_counter[0]
            }
            
            if left_arr[i] <= right_arr[j]:
                arr[k] = left_arr[i]
                i += 1
            else:
                arr[k] = right_arr[j]
                j += 1
            k += 1
            
            step_counter[0] += 1
            highlights = {}
            for m in range(left, k):
                highlights[m] = 'sorted'
            
            yield {
                'array': arr[:],
                'highlights': highlights,
                'description': f'Placed {arr[k-1]} at position {k-1}',
                'step': step_counter[0]
            }
        
        # Copy remaining elements
        while i < len(left_arr):
            arr[k] = left_arr[i]
            i += 1
            k += 1
            
            step_counter[0] += 1
            highlights = {}
            for m in range(left, k):
                highlights[m] = 'sorted'
            
            yield {
                'array': arr[:],
                'highlights': highlights,
                'description': f'Placed remaining {arr[k-1]} at position {k-1}',
                'step': step_counter[0]
            }
        
        while j < len(right_arr):
            arr[k] = right_arr[j]
            j += 1
            k += 1
            
            step_counter[0] += 1
            highlights = {}
            for m in range(left, k):
                highlights[m] = 'sorted'
            
            yield {
                'array': arr[:],
                'highlights': highlights,
                'description': f'Placed remaining {arr[k-1]} at position {k-1}',
                'step': step_counter[0]
            }
        
        # Show merged result
        step_counter[0] += 1
        highlights = {}
        for m in range(left, right + 1):
            highlights[m] = 'sorted'
        
        yield {
            'array': arr[:],
            'highlights': highlights,
            'description': f'Merged subarray [{left}:{right}]',
            'step': step_counter[0]
        }
    
    # Start the sorting process
    yield from mergesort_recursive(arr, 0, len(arr) - 1, step_counter)
    
    # Final sorted state
    step_counter[0] += 1
    highlights = {i: 'sorted' for i in range(len(arr))}
    yield {
        'array': arr[:],
        'highlights': highlights,
        'description': 'Sorting complete!',
        'step': step_counter[0],
        'sorted': True
    }

def binary_search_generator(arr, target):
    low = 0
    high = len(arr) - 1
    step = 0
    
    while low <= high:
        mid = (low + high) // 2
        step += 1
        
        yield {
            'low': low,
            'high': high,
            'mid': mid,
            'description': f'Searching range [{low}:{high}], mid={mid}, value={arr[mid]}',
            'step': step
        }
        
        if arr[mid] == target:
            step += 1
            yield {
                'found_index': mid,
                'description': f'Found {target} at index {mid}!',
                'step': step
            }
            return
        elif arr[mid] < target:
            low = mid + 1
            step += 1
            yield {
                'low': low,
                'high': high,
                'description': f'{arr[mid]} < {target}, searching right half',
                'step': step
            }
        else:
            high = mid - 1
            step += 1
            yield {
                'low': low,
                'high': high,
                'description': f'{arr[mid]} > {target}, searching left half',
                'step': step
            }
    
    # Not found
    step += 1
    yield {
        'description': f'{target} not found in the array',
        'step': step
    }