Cztery algorytmy, jedne dane

Porównanie sortowań: wybieranie, wstawianie, scalanie i szybkie - Informatyka - liceum klasa 2, zakres rozszerzony (Python)

Program liczy porównania elementów w czterech sortowaniach na tej samej liście losowej 200 liczb. Sortowanie przez wybieranie i przez wstawianie mają złożoność kwadratową (`n²`), scalanie i szybkie - około `n log₂ n`. Dla `n = 200` to różnica rzędu dziesięciu razy, a rośnie razem z `n`.

import random

def selection(values):
    values, count = list(values), 0
    for i in range(len(values) - 1):
        best = i
        for j in range(i + 1, len(values)):
            count += 1
            if values[j] < values[best]:
                best = j
        values[i], values[best] = values[best], values[i]
    return count

def insertion(values):
    values, count = list(values), 0
    for i in range(1, len(values)):
        x, j = values[i], i - 1
        while j >= 0:
            count += 1
            if values[j] <= x:
                break
            values[j + 1] = values[j]
            j -= 1
        values[j + 1] = x
    return count

def merging(values):
    if len(values) <= 1:
        return 0
    middle = len(values) // 2
    left, right = sorted(values[:middle]), sorted(values[middle:])
    count = merging(values[:middle]) + merging(values[middle:])
    i = j = 0
    while i < len(left) and j < len(right):
        count += 1
        if left[i] <= right[j]:
            i += 1
        else:
            j += 1
    return count

def quick(values):
    if len(values) <= 1:
        return 0
    pivot = values[0]
    rest = values[1:]
    return len(rest) + quick([x for x in rest if x < pivot]) + quick([x for x in rest if x >= pivot])

random.seed(3)
data = [random.randint(1, 1000) for i in range(200)]
for name, f in [("wybieranie", selection), ("wstawianie", insertion), ("scalanie", merging), ("szybkie", quick)]:
    print(name, f(data))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 2, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.