algorithms/sort.py

"""
USSU Algorithm Analyzer v4.0 - Sorting Algorithms Suite
With step capture for cyberpunk visualization and full metrics.
"""
import math
import random
from typing import List, Dict, Any, Optional, Tuple
from utils.core import profile_algorithm, OperationCounter


class SortingAlgorithms(OperationCounter):
    """Complete suite of sorting algorithms with operation counting and step logging"""

    def __init__(self, capture_steps: bool = False):
        super().__init__()
        self.capture_steps = capture_steps
        self.steps: List[Dict] = []
        self.sorted_data: List[Any] = []

    def reset(self):
        self.reset_counters()
        self.steps = []
        self.sorted_data = []

    def _log_step(self, arr: List[Any], title: str = "Sorting",
                  compare: Optional[Tuple[int, int]] = None,
                  swap: Optional[Tuple[int, int]] = None,
                  sorted_prefix: int = 0):
        if self.capture_steps:
            self.steps.append({
                'array': arr.copy(),
                'title': title,
                'compare': compare,
                'swap': swap,
                'sorted_prefix': sorted_prefix
            })

    def _make_result(self, name: str, arr: List[Any], time_c: str, space_c: str, stable: bool) -> Dict:
        return {
            'algorithm': name,
            'sorted': arr,
            'time_complexity': time_c,
            'space_complexity': space_c,
            'stable': stable,
            'comparisons': self.comparisons,
            'swaps': self.swaps,
            'accesses': self.accesses,
            'recursions': self.recursions,
            'steps': self.steps if self.capture_steps else [],
        }

    @profile_algorithm
    def bubble_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        n = len(a)
        for i in range(n):
            swapped = False
            for j in range(0, n - i - 1):
                self.comparisons += 1
                self.accesses += 2
                self._log_step(a, "Bubble Sort", compare=(j, j+1), sorted_prefix=n-i)
                if a[j] > a[j + 1]:
                    a[j], a[j + 1] = a[j + 1], a[j]
                    self.swaps += 1
                    swapped = True
                    self._log_step(a, "Bubble Sort - Swap", swap=(j, j+1), sorted_prefix=n-i)
            if not swapped:
                break
        self._log_step(a, "Bubble Sort - Complete", sorted_prefix=n)
        return self._make_result('Bubble Sort', a, 'O(n²)', 'O(1)', True)

    @profile_algorithm
    def selection_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        n = len(a)
        for i in range(n):
            min_idx = i
            for j in range(i + 1, n):
                self.comparisons += 1
                self.accesses += 1
                if a[j] < a[min_idx]:
                    min_idx = j
            if min_idx != i:
                a[i], a[min_idx] = a[min_idx], a[i]
                self.swaps += 1
                self._log_step(a, "Selection Sort", swap=(i, min_idx), sorted_prefix=i)
        self._log_step(a, "Selection Sort - Complete", sorted_prefix=n)
        return self._make_result('Selection Sort', a, 'O(n²)', 'O(1)', False)

    @profile_algorithm
    def insertion_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        for i in range(1, len(a)):
            key = a[i]
            self.accesses += 1
            j = i - 1
            while j >= 0:
                self.comparisons += 1
                self.accesses += 1
                if a[j] > key:
                    a[j + 1] = a[j]
                    self.swaps += 1
                    j -= 1
                else:
                    break
            a[j + 1] = key
            self.swaps += 1
            self._log_step(a, "Insertion Sort", sorted_prefix=i)
        self._log_step(a, "Insertion Sort - Complete", sorted_prefix=len(a))
        return self._make_result('Insertion Sort', a, 'O(n²)', 'O(1)', True)

    @profile_algorithm
    def merge_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()

        def merge(left: List, right: List) -> List:
            result = []
            i = j = 0
            while i < len(left) and j < len(right):
                self.comparisons += 1
                self.accesses += 2
                if left[i] <= right[j]:
                    result.append(left[i]); i += 1
                else:
                    result.append(right[j]); j += 1
            result.extend(left[i:])
            result.extend(right[j:])
            return result

        def sort(sub_arr: List) -> List:
            self.recursions += 1
            if len(sub_arr) <= 1:
                return sub_arr
            mid = len(sub_arr) // 2
            left = sort(sub_arr[:mid])
            right = sort(sub_arr[mid:])
            merged = merge(left, right)
            self._log_step(merged, "Merge Sort - Merge")
            return merged

        sorted_arr = sort(a)
        self._log_step(sorted_arr, "Merge Sort - Complete")
        return self._make_result('Merge Sort', sorted_arr, 'O(n log n)', 'O(n)', True)

    @profile_algorithm
    def quick_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()

        def partition(low: int, high: int) -> int:
            pivot = a[high]
            self.accesses += 1
            i = low - 1
            for j in range(low, high):
                self.comparisons += 1
                self.accesses += 1
                if a[j] <= pivot:
                    i += 1
                    a[i], a[j] = a[j], a[i]
                    self.swaps += 1
            a[i + 1], a[high] = a[high], a[i + 1]
            self.swaps += 1
            self._log_step(a, "Quick Sort - Partition", swap=(i+1, high))
            return i + 1

        def sort(low: int, high: int):
            self.recursions += 1
            if low < high:
                pi = partition(low, high)
                sort(low, pi - 1)
                sort(pi + 1, high)

        sort(0, len(a) - 1)
        self._log_step(a, "Quick Sort - Complete")
        return self._make_result('Quick Sort', a, 'O(n log n) avg', 'O(log n)', False)

    @profile_algorithm
    def heap_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        n = len(a)

        def heapify(size: int, root: int):
            largest = root
            left = 2 * root + 1
            right = 2 * root + 2
            self.accesses += 1
            if left < size and a[left] > a[largest]:
                largest = left
            self.accesses += 1
            if right < size and a[right] > a[largest]:
                largest = right
            self.comparisons += 1
            if largest != root:
                a[root], a[largest] = a[largest], a[root]
                self.swaps += 1
                heapify(size, largest)

        for i in range(n // 2 - 1, -1, -1):
            heapify(n, i)
            self._log_step(a, "Heap Sort - Build Heap")
        for i in range(n - 1, 0, -1):
            a[0], a[i] = a[i], a[0]
            self.swaps += 1
            heapify(i, 0)
            self._log_step(a, "Heap Sort - Extract", swap=(0, i), sorted_prefix=n-i)
        self._log_step(a, "Heap Sort - Complete")
        return self._make_result('Heap Sort', a, 'O(n log n)', 'O(1)', False)

    @profile_algorithm
    def shell_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        n = len(a)
        gap = n // 2
        while gap > 0:
            for i in range(gap, n):
                temp = a[i]
                self.accesses += 1
                j = i
                while j >= gap:
                    self.comparisons += 1
                    self.accesses += 1
                    if a[j - gap] > temp:
                        a[j] = a[j - gap]
                        self.swaps += 1
                        j -= gap
                    else:
                        break
                a[j] = temp
                self.swaps += 1
            self._log_step(a, f"Shell Sort - Gap {gap}")
            gap //= 2
        self._log_step(a, "Shell Sort - Complete")
        return self._make_result('Shell Sort', a, 'O(n log² n)', 'O(1)', False)

    @profile_algorithm
    def cocktail_shaker_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        n = len(a)
        swapped = True
        start = 0
        end = n - 1
        while swapped:
            swapped = False
            for i in range(start, end):
                self.comparisons += 1
                self.accesses += 2
                if a[i] > a[i + 1]:
                    a[i], a[i + 1] = a[i + 1], a[i]
                    self.swaps += 1
                    swapped = True
            if not swapped:
                break
            swapped = False
            end -= 1
            for i in range(end - 1, start - 1, -1):
                self.comparisons += 1
                self.accesses += 2
                if a[i] > a[i + 1]:
                    a[i], a[i + 1] = a[i + 1], a[i]
                    self.swaps += 1
                    swapped = True
            start += 1
            self._log_step(a, "Cocktail Shaker Sort", sorted_prefix=start)
        self._log_step(a, "Cocktail Shaker Sort - Complete")
        return self._make_result('Cocktail Shaker Sort', a, 'O(n²)', 'O(1)', True)

    @profile_algorithm
    def comb_sort(self, arr: List[Any]) -> Dict:
        self.reset()
        a = arr.copy()
        n = len(a)
        gap = n
        shrink = 1.3
        sorted_flag = False
        while not sorted_flag:
            gap = int(gap / shrink)
            if gap <= 1:
                gap = 1
                sorted_flag = True
            i = 0
            while i + gap < n:
                self.comparisons += 1
                self.accesses += 2
                if a[i] > a[i + gap]:
                    a[i], a[i + gap] = a[i + gap], a[i]
                    self.swaps += 1
                    sorted_flag = False
                i += 1
            self._log_step(a, f"Comb Sort - Gap {gap}")
        self._log_step(a, "Comb Sort - Complete")
        return self._make_result('Comb Sort', a, 'O(n²/2^p)', 'O(1)', False)

    @profile_algorithm
    def counting_sort(self, arr: List[int]) -> Dict:
        self.reset()
        if not arr:
            return self._make_result('Counting Sort', [], 'O(n + k)', 'O(k)', True)
        a = arr.copy()
        max_val = max(a)
        min_val = min(a)
        range_val = max_val - min_val + 1
        count = [0] * range_val
        output = [0] * len(a)
        for num in a:
            self.accesses += 1
            count[num - min_val] += 1
        for i in range(1, len(count)):
            count[i] += count[i - 1]
        for i in range(len(a) - 1, -1, -1):
            self.accesses += 1
            output[count[a[i] - min_val] - 1] = a[i]
            count[a[i] - min_val] -= 1
            self.swaps += 1
        self._log_step(output, "Counting Sort - Complete")
        return self._make_result('Counting Sort', output, 'O(n + k)', 'O(k)', True)

    @profile_algorithm
    def radix_sort(self, arr: List[int]) -> Dict:
        self.reset()
        if not arr:
            return self._make_result('Radix Sort', [], 'O(d(n+k))', 'O(n + k)', True)
        a = arr.copy()
        max_num = max(abs(x) for x in a)
        exp = 1
        while max_num // exp > 0:
            counting = [[] for _ in range(10)]
            for num in a:
                self.accesses += 1
                digit = (abs(num) // exp) % 10
                counting[digit].append(num)
            a = []
            for bucket in counting:
                a.extend(bucket)
                self.swaps += len(bucket)
            self._log_step(a, f"Radix Sort - Exp {exp}")
            exp *= 10
        negatives = [x for x in a if x < 0]
        positives = [x for x in a if x >= 0]
        a = negatives + positives
        self._log_step(a, "Radix Sort - Complete")
        return self._make_result('Radix Sort', a, 'O(d(n+k))', 'O(n + k)', True)

    @profile_algorithm
    def bucket_sort(self, arr: List[float], bucket_count: int = 10) -> Dict:
        self.reset()
        if not arr:
            return self._make_result('Bucket Sort', [], 'O(n + k)', 'O(n + k)', True)
        a = arr.copy()
        min_val, max_val = min(a), max(a)
        buckets = [[] for _ in range(bucket_count)]
        for num in a:
            self.accesses += 1
            idx = int((num - min_val) / (max_val - min_val) * (bucket_count - 1))
            buckets[idx].append(num)
        sorted_arr = []
        for b in buckets:
            sorted_arr.extend(sorted(b))
            self.swaps += len(b)
        self._log_step(sorted_arr, "Bucket Sort - Complete")
        return self._make_result('Bucket Sort', sorted_arr, 'O(n + k)', 'O(n + k)', True)

    @profile_algorithm
    def tim_sort(self, arr: List[Any]) -> Dict:
        """Python's built-in Timsort for comparison"""
        self.reset()
        a = arr.copy()
        self.accesses += len(a)
        a.sort()
        self.swaps += len(a)  # Approximation
        self._log_step(a, "Timsort - Complete")
        return self._make_result('Timsort (Python)', a, 'O(n log n)', 'O(n)', True)

    def compare_all(self, arr: List[Any]) -> List[Dict]:
        """Benchmark all sorting algorithms"""
        algorithms = [
            ('Bubble Sort', self.bubble_sort),
            ('Selection Sort', self.selection_sort),
            ('Insertion Sort', self.insertion_sort),
            ('Merge Sort', self.merge_sort),
            ('Quick Sort', self.quick_sort),
            ('Heap Sort', self.heap_sort),
            ('Shell Sort', self.shell_sort),
            ('Cocktail Shaker', self.cocktail_shaker_sort),
            ('Comb Sort', self.comb_sort),
            ('Timsort', self.tim_sort),
        ]
        if arr and all(isinstance(x, int) for x in arr):
            algorithms.extend([
                ('Counting Sort', self.counting_sort),
                ('Radix Sort', self.radix_sort),
                ('Bucket Sort', lambda a: self.bucket_sort([float(x) for x in a])),
            ])
        results = []
        for name, algo in algorithms:
            try:
                if len(arr) > 2000 and name in ['Bubble Sort', 'Selection Sort', 'Insertion Sort', 'Cocktail Shaker']:
                    results.append({'name': name, 'time_ms': float('inf'), 'complexity': 'Skipped', 'stable': '-'})
                    continue
                res = algo(arr)
                results.append({
                    'name': name,
                    'time_ms': res.get('execution_time_ms', 0),
                    'complexity': res.get('time_complexity', 'N/A'),
                    'space': res.get('space_complexity', 'N/A'),
                    'stable': 'Yes' if res.get('stable') else 'No',
                    'comparisons': res.get('comparisons', 0),
                })
            except Exception as e:
                results.append({'name': name, 'error': str(e)})
        return results