정렬

main.py

from random import randint

def bubble_sort(arr):
    n = len(arr)

    for i in range(n):
        done_sort = True

        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

                done_sort = False
        if done_sort:
            break
    return arr


def insertion_sort(arr):
    n = len(arr)

    for i in range(1, n):
        key_item = arr[i]

        j = i - 1

        while j >= 0 and arr[j] > key_item:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key_item
    return arr


def merge_sort(arr):
    def merge(left, right):
        left_len = len(left)
        right_len = len(right)

        result = []

        left_index = right_index = 0

        while len(result) < left_len + right_len:
            if left[left_index] <= right[right_index]:
                result.append(left[left_index])
                left_index += 1
            else:
                result.append(right[right_index])
                right_index += 1
            if right_index == right_len:
                result.extend(left[left_index:])
                break
            if left_index == left_len:
                result.extend(right[right_index:])
                break
        return result

    n = len(arr)
    if n < 2:
        return arr
    mid_index = n // 2
    left = merge_sort(arr[:mid_index])
    right = merge_sort(arr[mid_index:])
    return merge(left, right)


def quicksort(arr):
    arr_len = len(arr)
    if arr_len < 2:
        return arr

    low, same, high = [], [], []

    pivot = arr[randint(0, arr_len - 1)]

    for item in arr:
        if item < pivot:
            low.append(item)
        elif item == pivot:
            same.append(item)
        elif item > pivot:
            high.append(item)
    return quicksort(low) + same + quicksort(high)


def binary_search(arr, key, start, end):
    if end - start <= 1:
        if arr[start] > key:
            return start - 1
    else:
        return start

    mid = (start + end) // 2

    if arr[mid] < key:
        return binary_search(arr, key, mid, end)
    elif arr[mid] > key:
        return binary_search(arr, key, start, mid)
    else:
        return mid


def insertion_sort(arr, run_s=0, run_e=None):
    if run_e is None:
        run_e = len(arr) - 1

    for i in range(run_s + 1, run_e + 1):
        v = arr[i]
        pos = binary_search(arr, v, run_s, i) + 1

        for k in range(i, pos, -1):
            arr[k] = arr[k - 1]
        arr[pos] = v


def timsort(arr):

    def merge(left, right):
        left_len = len(left)
        right_len = len(right)

        result = []

        left_index = right_index = 0

        while len(result) < left_len + right_len:
            if left[left_index] <= right[right_index]:
                result.append(left[left_index])
                left_index += 1
            else:
                result.append(right[right_index])
                right_index += 1
            if right_index == right_len:
                result.extend(left[left_index:])
                break
            if left_index == left_len:
                result.extend(right[right_index:])
                break
        return result

    min_run = 32

    n = len(arr)

    for i in range(0, n, min_run):
        insertion_sort(arr, i, min((i + min_run - 1), n - 1))

    size = min_run
    while size < n:
        for start in range(0, n, size * 2):
            mid = start + size - 1
            end = min((start + size * 2 - 1), (n - 1))

            merged = merge(arr[start:mid + 1], arr[mid + 1:end + 1])
            arr[start:start + len(merged)] = merged
        size *= 2
    return arr



if __name__ == "__main__":
    input_array = [randint(0, 100) for i in range(100)]
    res = timsort(input_array)
    print(f'{sorted(res)}')
    print(f'{sorted(input_array) == res}')