Упражнение 16: сортировка пузырьком, быстрая сортировка и сортировка слиянием

процедура bubbleSort(A : список сортируемых элементов)
    n = длина(A)
    повторять
        swapped = false
        для i = 1 до n-1 включительно делать
            /* Если эта пара элементов расположена неправильно */
            если A[i-1] > A[i] то
                /* Обменять их местами и помнить об этом */
                swap(A[i-1], A[i])
                swapped = true
            конец если
        конец для
    пока swapped
конец процедуры
```Вы заметите, что псевдокод представляет собой лишь приближенное описание алгоритма, которое может сильно различаться от одного источника к другому — книг, авторов или страниц Википедии. Он предполагает, что вы можете прочитать этот "контур" программы и адаптировать его под свои нужды. Иногда это может напоминать старый язык программирования Algol, а иногда выглядеть как некорректно оформленный JavaScript или Python. Вам просто нужно догадываться о значении этого контура и переводить его в нужный вам формат. Вот мой начальный перевод данного конкретного псевдокода:

```py
def bubble_sort(numbers):
    """Сортирует список чисел методом пузырьковой сортировки."""
    while True:
        # Начнём с предположения, что список уже отсортирован
        is_sorted = True
        # Будем сравнивать пары элементов, пропустив первый элемент
        node = numbers.begin.next
        while node:
            # Пройдёмся по списку и сравним текущий элемент со следующим
            if node.prev.value > node.value:
                # Если предыдущий элемент больше, меняем их местами
                node.prev.value, node.value = node.value, node.prev.value
                # Это значит, что нам потребуется ещё один проход по списку
                is_sorted = False
            node = node.next

        # Если мы сделали полный проход по списку и ничего не поменяли,
        # значит он уже отсортирован
        if is_sorted: break
```Я добавил эти комментарии, чтобы вы могли учиться и следовать за процессом. Сравните, что я сделал здесь, с исходным псевдокодом. Также обратите внимание, что структура данных, используемая на страницах Википедии, отличается от `DoubleLinkedList`. Код Википедии предполагает работу с массивами или списками. Вам следует заменить эту строчку:

```python
if A[i-1] > A[i] then

if node.prev.value > node.value:

import sorting
from dllist import DoubleLinkedList
from random import randint
``````markdown
max_numbers = 30

def random_list(count):
    numbers = DoubleLinkedList()
    for i in range(count, 0, -1):
        numbers.shift(randint(0, 10000))
    return numbers


def is_sorted(numbers):
    node = numbers.begin
    while node and node.next:
        if node.value > node.next.value:
            return False
        else:
            node = node.next

    return True


def test_bubble_sort():
    numbers = random_list(max_numbers)

    sorting.bubble_sort(numbers)

    assert is_sorted(numbers)


def test_merge_sort():
    numbers = random_list(max_numbers)

    sorting.merge_sort(numbers)

    assert is_sorted(numbers)


Этот тестовый код включает важную часть, где используется функция `random.randint` для генерации случайных данных для тестирования. Этот тест не проверяет многие граничные случаи, но это начало, которое мы будем улучшать впоследствии. Вспомните, что вы еще не реализовали `sort.merge_sort`, поэтому вы можете не писать этот тестовый метод или закомментировать его.

Как только вы завершите тестирование и напишете этот код, снова изучите страницу Википедии, а затем попробуйте несколько других версий `bubble_sort` перед тем, как пробовать `merge_sort`.

### Слиянием сортировка

Я пока не готов был вас попросить самостоятельно её реализовать. Я повторю этот процесс для функции `merge_sort`, но на этот раз я хочу, чтобы вы попробовали реализовать алгоритм слиянием сортировки, используя псевдокод с страницы Википедии. После этого вы сможете сравнить вашу реализацию с моей.

Несколько реализаций предлагается, но я использую "сверху вниз" версию:
``````py
def merge_sort(m):
    if len(m) <= 1:
        return m

    left = []
    right = []

    for i, x in enumerate(m):
        if i < len(m) / 2:
            left.append(x)
        else:
            right.append(x)

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


def merge(left, right):
    result = []

    while left and right:
        if left[0] <= right[0]:
            result.append(left[0])
            left = left[1:]
        else:
            result.append(right[0])
            right = right[1:]

    while left:
        result.append(left[0])
        left = left[1:]

    while right:
        result.append(right[0])
        right = right[1:]

    return result


# Для test_merge_sort напишите оставшиеся тестовые случаи функции, а затем попробуйте её реализацию.
# Вам может потребоваться способ вычисления количества узлов от данного узла.
# Это то, что DoubleLinkedList не делает.


def count(node):
    count = 0

    while node:
        node = node.next
        count += 1

    return count

def сортировка_слиянием(числа):
    числа.begin = слияние_узел(числа.begin)

    # ужасный способ получить конец
    узел = числа.begin
    while узел.next:
        узел = узел.next
    числа.end = узел


def слияние_узел(начало):
    """Сортирует список чисел методом сортировки слиянием."""
    if начало.next == None:
        return начало

    средняя = len(начало) // 2

    # сканирование до середины
    сканер = начало
    for i in range(0, средняя - 1):
        сканер = сканер.next

    # установка узла середины сразу после точки сканирования
    средний_узел = сканер.next
    # разрыв в точке середины
    сканер.next = None
    средний_узел.prev = None

    слева = слияние_узел(начало)
    справа = слияние_узел(средний_узел)

    return слияние(слева, справа)


def слияние(слева, справа):
    """Выполняет слияние двух списков."""
    результат = None

    if слева == None: 
        return справа
    if справа == None: 
        return слева

    if значение(слева) > значение(права): 
        результат = справа
        результат.next = слияние(слева, справа.next)
    else:
        результат = слева
        результат.next = слияние(слева.next, справа)

    результат.next.prev = результат
    return результат