gokaymeydan/sorting-algorithm-visualizer

1# algorithms.py with metrics2import math3import time4 5 6def _snap(steps, record_steps, a, active_i, boundary=-1):7    if record_steps:8        steps.append(9            {"array": a.copy(), "active_index": active_i, "sorted_boundary": boundary}10        )11 12 13def insertion_sort(arr, record_steps: bool = True):14    a = arr.copy()15    steps = []16    comparisons = 017    moves = 018    start = time.perf_counter()19    for i in range(1, len(a)):20        key = a[i]21        j = i - 122        # at least one comparison if entering the while loop23        while j >= 0:24            comparisons += 125            if a[j] > key:26                a[j + 1] = a[j]27                moves += 128                _snap(steps, record_steps, a, j + 1, i)29                j -= 130            else:31                break32        a[j + 1] = key33        moves += 134        _snap(steps, record_steps, a, j + 1, i)35    end = time.perf_counter()36    metrics = {"comparisons": comparisons, "moves": moves, "seconds": end - start}37    return steps, metrics38 39 40def merge_sort(arr, record_steps: bool = True):41    a = arr.copy()42    steps = []43    comparisons = 044    moves = 045    start = time.perf_counter()46 47    def merge(left, mid, right):48        nonlocal comparisons, moves49        # Create copies of subarrays50        left_part = a[left : mid + 1]51        right_part = a[mid + 1 : right + 1]52        i = j = 053        k = left54 55        # Merge while both parts have elements56        while i < len(left_part) and j < len(right_part):57            comparisons += 1  # one comparison each loop58            if left_part[i] <= right_part[j]:59                a[k] = left_part[i]60                moves += 161                _snap(steps, record_steps, a, k, right)62                i += 163            else:64                a[k] = right_part[j]65                moves += 166                _snap(steps, record_steps, a, k, right)67                j += 168            k += 169 70        # Copy remaining elements of left_part71        while i < len(left_part):72            a[k] = left_part[i]73            moves += 174            _snap(steps, record_steps, a, k, right)75            i += 176            k += 177 78        # Copy remaining elements of right_part79        while j < len(right_part):80            a[k] = right_part[j]81            moves += 182            _snap(steps, record_steps, a, k, right)83            j += 184            k += 185 86    def sort(left, right):87        if left >= right:88            return89        mid = (left + right) // 290        sort(left, mid)91        sort(mid + 1, right)92        merge(left, mid, right)93 94    if len(a) > 0:95        sort(0, len(a) - 1)96 97    end = time.perf_counter()98    metrics = {"comparisons": comparisons, "moves": moves, "seconds": end - start}99    return steps, metrics100 101 102def quick_sort(arr, record_steps: bool = True):103    a = arr.copy()104    steps = []105    comparisons = 0106    moves = 0107 108    def swap(i, j, *, active_i=None, sorted_b=None):109        nonlocal moves110        if i == j:111            return112        (113            a[i],114            a[j],115        ) = (116            a[j],117            a[i],118        )119        moves += 2120        _snap(121            steps,122            record_steps,123            a,124            i if active_i is None else active_i,125            -1 if sorted_b is None else sorted_b,126        )127 128    def partition(low, high):129        nonlocal comparisons, moves130        pivot = a[high]131        i = low - 1132        # compare high-1 and pivot133        for j in range(low, high):134            comparisons += 1135            if a[j] <= pivot:136                i += 1137                swap(i, j, active_i=j)138        # put pivot back to place139        swap(i + 1, high, active_i=i + 1, sorted_b=i + 1)140        return i + 1141 142    def qs(low, high):143        if low < high:144            p = partition(low, high)145            qs(low, p - 1)146            qs(p + 1, high)147 148    start = time.perf_counter()149    if a:150        qs(0, len(a) - 1)151    seconds = time.perf_counter() - start152 153    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}154    return steps, metrics155 156 157def counting_sort(arr, k=None, record_steps: bool = True):158    a = arr.copy()159    steps = []160    comparisons = 0161    moves = 0162    if not a:163        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}164 165    # negatifleri desteklemiyorsak koruma (istersen offset ile destekleyebilirsin)166    if min(a) < 0:167        raise ValueError("Counting Sort: negatif değerler desteklenmiyor.")168 169    # k (değer aralığı) verilmediyse max+1 al170    if k is None:171        k = max(a) + 1172 173    start = time.perf_counter()174 175    count = [0] * k176    for v in a:177        count[v] += 1178    for i in range(1, k):179        count[i] += count[i - 1]180 181    out = [0] * len(a)182    for v in reversed(a):183        count[v] -= 1184        out[count[v]] = v185 186    for i, v in enumerate(out):187        a[i] = v188        moves += 1189        _snap(steps, record_steps, a, i, i)190 191    seconds = time.perf_counter() - start192    return steps, {"comparisons": comparisons, "moves": moves, "seconds": seconds}193 194 195def radix_sort_lsd(arr, base=10, record_steps: bool = True):196    a = arr.copy()197    steps = []198    comparisons = 0199    moves = 0200 201    if not a:202        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}203    if base < 2:204        raise ValueError("radix base must be >= 2")205 206    start = time.perf_counter()207 208    def digit(x, exp):209        return (x // exp) % base210 211    exp = 1212    maxv = max(a)213 214    # for each digit place215    while maxv // exp > 0:216        # stable counting sort by current digit217        count = [0] * base218 219        # count220        for v in a:221            d = digit(v, exp)222            count[d] += 1223 224        # prefix sums225        for i in range(1, base):226            count[i] += count[i - 1]227 228        # build output(scan from right)229        out = [0] * len(a)230        for i in range(len(a) - 1, -1, -1):231            v = a[i]232            d = digit(v, exp)233            count[d] -= 1234            out[count[d]] = v235 236        for i, v in enumerate(out):237            a[i] = v238            moves += 1239            _snap(steps, record_steps, a, i, i)240        exp *= base241 242    seconds = time.perf_counter() - start243    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}244    return steps, metrics245 246 247# --- Heap Sort (max-heap, in-place) with metrics & step recording ---248# steps: her adımda {"array": a.copy(), "active_index": i, "sorted_boundary": b}249# - active_index: o karede yeni yazılan / swap’e giren indeks250# - sorted_boundary: heapsort’ta sıralı kuyruk (suffix) başlangıcı; j >= boundary -> "sorted"251# metrics:252# - comparisons: her a[l] > a[m] veya a[r] > a[m] kontrolü 1 karşılaştırma253# - moves: diziye her yazma 1; swap 2 move254def heap_sort(arr, record_steps: bool = True):255    a = arr.copy()256    steps = []257    comparisons = 0258    moves = 0259 260    heap_sorted = -1261 262    def snapshot(active_i, boundary):263        _snap(steps, record_steps, a, active_i, boundary)264 265    def swap(i, j):266        nonlocal moves267        if i == j:268            return269        a[i], a[j] = a[j], a[i]270        moves += 2271        snapshot(i, heap_sorted)272 273    def heapify(n, i):274        nonlocal comparisons275        while True:276            largest = i277            l = 2 * i + 1278            r = 2 * i + 2279 280            if l < n:281                comparisons += 1282                if a[l] > a[largest]:283                    largest = l284            if r < n:285                comparisons += 1286                if a[r] > a[largest]:287                    largest = r288            if largest == i:289                break290 291            swap(i, largest)292            i = largest293 294    start = time.perf_counter()295 296    n = len(a)297    if n <= 1:298        metrics = {"comparisons": 0, "moves": 0, "seconds": 0.0}299        return steps, metrics300 301    # build max heap302    for i in range(n // 2 - 1, -1, -1):303        heapify(n, i)304    # extract max305    for end in range(n - 1, 0, -1):306        swap(0, end)307        heap_sorted = end308        heapify(end, 0)309 310    seconds = time.perf_counter() - start311    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}312    return steps, metrics313 314 315def shell_sort(arr, record_steps: bool = True):316    a = arr.copy()317    steps = []318    comparisons = 0319    moves = 0320 321    def snap(active_i, boundary=-1):322        _snap(steps, record_steps, a, active_i, boundary)323 324    start = time.perf_counter()325 326    n = len(a)327    if n <= 1:328        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}329 330    gap = n // 2331    while gap > 0:332        for i in range(gap, n):333            key = a[i]334            j = i - gap335 336            while j >= 0:337                comparisons += 1338                if a[j] > key:339                    a[j + gap] = a[j]340                    moves += 1341                    snap(j + gap)342                    j -= gap343                else:344                    break345            a[j + gap] = key346            moves += 1347            snap(j + gap)348 349        gap //= 2350 351    seconds = time.perf_counter() - start352    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}353    return steps, metrics354 355 356def bucket_sort(arr, num_buckets=None, record_steps: bool = True):357    a = arr.copy()358    steps = []359    comparisons = 0360    moves = 0361 362    if not a:363        return steps, {"comparisons": 0, "moves": 0, "seconds": 0.0}364 365    n = len(a)366 367    if num_buckets is None:368        num_buckets = max(1, int(math.sqrt(n)))369 370    start = time.perf_counter()371 372    maxv = max(a)373 374    # normlize values range between 0 and 1375    if maxv == 0:376        seconds = time.perf_counter() - start377 378        for i, v in enumerate(a):379            _snap(steps, record_steps, a, i, i)380        return steps, {"comparisons": 0, "moves": 0, "seconds": seconds}381 382    normalized = [x / (maxv + 1.0) for x in a]383 384    # create buckets385    buckets = [[] for _ in range(num_buckets)]386 387    # split values to buckets388    for v_norm, v_orig in zip(normalized, a):389        idx = int(v_norm * num_buckets)390        if idx >= num_buckets:391            idx = num_buckets - 1392        buckets[idx].append(v_orig)393 394    # sort buckets395 396    for b in buckets:397        for i in range(1, len(b)):398            key = b[i]399            j = i - 1400            while j >= 0:401                comparisons += 1402                if b[j] > key:403                    b[j + 1] = b[j]404                    j -= 1405                else:406                    break407            b[j + 1] = key408 409    # save at main410    write_i = 0411    for b in buckets:412        for v in b:413            a[write_i] = v414            moves += 1415            _snap(steps, record_steps, a, write_i, write_i)416            write_i += 1417 418    seconds = time.perf_counter() - start419    metrics = {"comparisons": comparisons, "moves": moves, "seconds": seconds}420    return steps, metrics421