ДЗ Лабораторная работа №3 "Алгоритмы сортировки"

В отчете должно быть указано следующие:

1. Титульный лист, где указаны ФИО преподавателя, номер задания, номер варианта
2. Формулировка задания
3. Ссылка на github-репозиторий с работающим кодом
4. Блок-схема каждого алгоритма отдельно с описанием алгоритма
5. После каждого описания идет листинг кода
6. Пример входных и выходных данных (таблицей)
7. Произвести асимптотическую оценку (лучший случай, худший случай, средний случай)
8. В конце работы приводятся реальные замеры на вашем ЭВМ в виде таблицы и графика

Примечание 1: Для реализации Unit-test рекомендуется произвести тестрование при помощи assertEqual и Assert::Is

Примечание 2: Оси графиков должны быть подписаны — указаны название показателя и единицы его измерения. Например, «Время выполнения алгоритмы, с», «Количество элементов в массиве». Под графиком размещается подрисуночная подпись с пояснением зависимость какой величины от какого параметра на нем показана.

1 Описания алгоритмов

Для реализации ниже дано словесное описание алгоритма и его псевдокод. Блок-схемы составляете самостоятельно, например, при помощи сервиса programforyou

Сортировка пузырьком

Сортировка пузырьком — это простейший и один из самых известных алгоритмов сортировки. Идея заключается в последовательном сравнении значений соседних элементов. Если текущий элемент больше следующего, меняем их местами. Алгоритм необходимо повторять до тех пор, пока массив не будет отсортирован.

Функция пузырьковаяСортировка(массив):
    n ← длина(массив)
    для i от 0 до n - 2:
        для j от 0 до n - 2:
            если массив[j] > массив[j + 1] то:
                поменять местами(массив[j], массив[j + 1])
            конец если
        конец внутреннего цикла
    конец внешнего циикла
конец функции

Гномья сортировка

Гномья сортировка — это алгоритм сортировки, основанный на идее, что мы можем перемещать элементы в массиве, как будто "гуляем" по нему, начиная с конца. Если текущий элемент больше следующего, то они меняются местами и продолжаем двигаться назад, пока не окажемся на месте, где элементы расположены в правильном порядке.

Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на текущий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.

Функция гномьяСортировка(массив):
    i ← 1
    пока i < длина(массив):
        если i > 0 и массив[i - 1] > массив[i] то:
            поменять местами(массив[i - 1], массив[i])
            i ← i - 1
        иначе:
            i ← i + 1
    конец цикла
конец функции

Сортировка расческой

Сортировка расческой — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии.

Сортировка расческой — это улучшение сортировки пузырьком. Основная идея заключается в том, чтобы с каждым шагом уменьшать интервал, на котором происходят сравнения и обмены элементов, а не всегда сравнивать только соседние элементы, как в сортировке пузырьком. Начинаем с большого интервала (расстояния) между сравниваемыми элементами и постепенно уменьшаем его. Алгоритм продолжает работать до тех пор, пока не произойдут обмены на самом маленьком интервале, что гарантирует завершение сортировки.

Функция сортировкаРасческой(массив):
    n ← длина(массив)
    шаг ← n - 1  # Начальный шаг
    пока шаг > 1:
        шаг ← шаг // 1.3  # Уменьшаем шаг
        i ← 0
        пока i + шаг < n:
            если массив[i] > массив[i + шаг] то:
                поменять местами(массив[i], массив[i + шаг])
            конец если
            i ← i + 1
        конец цикла
    конец цикла
конец функции

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

Сортировка слиянием — это эффективный алгоритм сортировки, который использует метод "разделяй и властвуй". Алгоритм рекурсивно делит массив на два подмассива, сортирует их и затем сливает их обратно в один отсортированный массив. Это деление продолжается до тех пор, пока каждый подмассив не станет содержать только один элемент, после чего начинается процесс слияния.

Функция сортировкаСлиянием(массив):
    если длина(массив) > 1 то:
        середина ← длина(массив) // 2
        леваяПоловина ← массив[0:середина]
        праваяПоловина ← массив[середина:конец]

        сортировкаСлиянием(леваяПоловина)
        сортировкаСлиянием(праваяПоловина)

        i ← 0  # Индекс для левой половины
        j ← 0  # Индекс для правой половины
        k ← 0  # Индекс для исходного массива

        пока i < длина(леваяПоловина) и j < длина(праваяПоловина):
            если леваяПоловина[i] < праваяПоловина[j] то:
                массив[k] ← леваяПоловина[i]
                i ← i + 1
            иначе:
                массив[k] ← праваяПоловина[j]
                j ← j + 1
            конец если
            k ← k + 1

        пока i < длина(леваяПоловина):
            массив[k] ← леваяПоловина[i]
            i ← i + 1
            k ← k + 1

        пока j < длина(праваяПоловина):
            массив[k] ← праваяПоловина[j]
            j ← j + 1
            к ← к + 1
    конец если
конец функции

Сортировка вставками

Сортировка вставками — это один из простейших алгоритмов сортировки, который работает по принципу пошагового построения отсортированной части массива, где каждый новый элемент вставляется в нужное место в уже отсортированной части. Этот алгоритм эффективно работает на малых объемах данных, но его производительность значительно ухудшается на больших объемах.

Идея работы алгоритма:

• Начинаем с второго элемента массива и сравниваем его с предыдущим.
• Если текущий элемент меньше предыдущего, перемещаем его на нужную позицию в отсортированную часть массива, сдвигая остальные элементы вправо.
• Повторяем эти шаги для всех элементов массива, постепенно расширяя отсортированную часть.

Функция сортировкаВставками(массив):
    для i от 1 до длина(массив) - 1:
        текущий ← массив[i]
        j ← i - 1
        пока j >= 0 и массив[j] > текущий:
            массив[j + 1] ← массив[j]
            j ← j - 1
        конец пока
        массив[j + 1] ← текущий
    конец цикла
конец функции

Сортировка Шелла

Сортировка Шелла — это улучшение сортировки вставками, которое делает ее более эффективной за счет использования шагов для сравнения и перемещения элементов, что позволяет значительно ускорить процесс сортировки. В отличие от стандартной сортировки вставками, которая сравнивает только соседние элементы, сортировка Шелла использует интервалы (шаги) между элементами для более быстрого сдвига элементов в правильное положение.

Идея заключается в том, чтобы сначала отсортировать элементы с большими интервалами, а затем постепенно уменьшать шаг, пока не достигнем единичного шага, что приведет к окончательной сортировке.

Функция сортировкаШелла(массив):
    n ← длина(массив)
    шаг ← n // 2  # Начальный шаг
    
    пока шаг > 0:
        для i от шаг до n - 1:
            временный ← массив[i]
            j ← i
            пока j >= шаг и массив[j - шаг] > временный:
                массив[j] ← массив[j - шаг]
                j ← j - шаг
            конец пока
            массив[j] ← временный
        конец цикла
        шаг ← шаг // 2  # Уменьшаем шаг
    конец цикла
конец функции

Поразрядная сортировка

Поразрядная сортировка (Radix Sort) — это алгоритм сортировки, который работает путем обработки элементов по разрядам (цифрам, буквам и т. д.), начиная с наименее значимого разряда (или наоборот — с наиболее значимого).

Основные этапы алгоритма:

• Алгоритм обрабатывает числа или строки по разрядам.
• Сортирует элементы на каждом разряде с использованием другого алгоритма сортировки (чаще всего сортировки подсчетом).
• Повторяет процесс для каждого разряда, начиная с младшего и заканчивая старшим.
• После завершения сортировки элементов по всем разрядам массив становится отсортированным.

Функция поразряднаяСортировка(массив):
    максимальноеЧисло ← максимальное(массив)
    разряд ← 1
    пока максимальноеЧисло // разряд > 0:
        сортироватьПоРазряду(массив, разряд)
        разряд ← разряд * 10
    конец цикла
конец функции

Функция сортироватьПоРазряду(массив, разряд):
    # Используем сортировку по подсчету для данного разряда
    корзины ← [пустой список для 10 разрядов]
    для числа в массиве:
        индексКорзины ← (число // разряд) % 10
        корзины[индексКорзины].добавить(число)
    конец цикла
    массив ← объединитьКорзины(корзины)
конец функции

Функция объединитьКорзины(корзины):
    объединенныйМассив ← пустой список
    для корзины в корзинах:
        объединенныйМассив.расширить(корзина)
    конец цикла
    вернуть объединенныйМассив

Быстрая сортировка

Быстрая сортировка (Quick Sort) — это один из самых быстрых алгоритмов сортировки. Она также использует метод "разделяй и властвуй", но отличается от сортировки слиянием тем, что данные не нужно копировать в дополнительные массивы. Алгоритм основывается на выборе опорного элемента, который затем используется для разделения массива на две части — элементы меньшие опорного и элементы большие опорного. После этого рекурсивно сортируются эти части.

Основные этапы алгоритма:

1. Выбирается опорный элемент.
2. Массив переставляется так, чтобы все элементы, меньшие опорного, оказались слева от него, а все элементы, большие — справа.
3. Рекурсивно повторяем сортировку для левой и правой части массива.

Функция быстраяСортировка(массив, низ, высокий):
    если низ < высокий то:
        опорныйИндекс ← разделить(массив, низ, высокий)
        быстраяСортировка(массив, низ, опорныйИндекс - 1)
        быстраяСортировка(массив, опорныйИндекс + 1, высокий)
    конец если

Функция разделить(массив, низ, высокий):
    опорный ← массив[высокий]
    i ← низ - 1
    для j от низ до высокий - 1:
        если массив[j] <= опорный то:
            i ← i + 1
            поменять местами(массив[i], массив[j])
    поменять местами(массив[i + 1], массив[высокий])
    вернуть i + 1

2 Варианты