Практика 6 Алгоритмы сортировки

В программировании часто встречаются задачи, которые трудно решить «в лоб». Представим, что нам нужно избавиться от повторяющихся элементов в массиве. Попробуем найти все числа, которые встречаются здесь больше, чем один раз:

7, 3, 1, 9, 10, 2, 3, 6, 9, 4, 7, 5, 5, 4, 2, 8, 4, 7

Чтобы это сделать, нужно написать сложный алгоритм. Можно упростить задачу и отсортировать массив. В нем повторяющиеся элементы находятся рядом, поэтому их легко обнаружить, сравнивая соседние числа:

1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 7, 7, 8, 9, 9, 10

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

Существуют десятки алгоритмов сортировки. В силу ограниченности времени рассмотрим лишь некоторые из них

• Пузырьковая сортировка
• Гномья сортировка
• Поразрядная
• Быстрая сортировка

Все три алгоритма сортируют исходный массив, меняя местами его элементы и не требуя дополнительного пространства.

Эти алгоритмы помогут понять, как работает сортировка. На их примере вы изучите, какие техники программисты применяют при разработке алгоритмов.

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

1 Разработка интерфейса

Начнем с того,что зададим константы:

• Ширина и высота окна
• Цвет фона
• Цвет кнопок
• Цвет столбцов
• Размер массива

import pygame
import random
import time

# Настройки окна
WIDTH, HEIGHT = 800, 600
ARRAY_SIZE = 50
BAR_WIDTH = WIDTH // ARRAY_SIZE

# Цвета
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
BLUE = (100, 100, 255)
RED = (255, 100, 100)

#include <SFML/Graphics.hpp>
#include <vector>
#include <algorithm>
#include <random>
#include <thread>
#include <chrono>
#include <locale>

const int WIDTH = 800;
const int HEIGHT = 600;
const int ARRAY_SIZE = 50;
const int BAR_WIDTH = WIDTH / ARRAY_SIZE;

Инциализация окна

pygame.init() # инциализация игры 
screen = pygame.display.set_mode((WIDTH, HEIGHT)) # создание окна
pygame.display.set_caption("Алгоритмы сортировки") # название окна
font = pygame.font.Font(None, 36) # установка шрифта

setlocale(LC_ALL, "ru_RU.UTF-8"); // как обычно боремся с проблемами русского языка 

sf::RenderWindow window(sf::VideoMode(WIDTH, HEIGHT), "Алгоритмы сортировки"); // создание окна
if (!font.loadFromFile("arial.ttf")) { // установка шрифта. Учтите, тут чтение идет из файла!
    return -1;
}

Отрисовка кнопок

Кнопки по сути являются прямоугольниками, следовательно отрисуем их соовтествующими объектами и дадим имена

button_random = pygame.Rect(0, 550, 300, 30)
button_algorithm = pygame.Rect(320, 550, 200, 30)
button_sort = pygame.Rect(550, 550, 250, 30)

sf::RectangleShape buttonRandom(sf::Vector2f(300, 30));
buttonRandom.setPosition(0, 550);
buttonRandom.setFillColor(sf::Color::Red);

sf::RectangleShape buttonAlgorithm(sf::Vector2f(200, 30));
buttonAlgorithm.setPosition(320, 550);
buttonAlgorithm.setFillColor(sf::Color::Red);

sf::RectangleShape buttonSort(sf::Vector2f(250, 30));
buttonSort.setPosition(550, 550);
buttonSort.setFillColor(sf::Color::Red);

Инциализация массива

Создайте функцию generateArray, которая будет создавать массива размера ARRAY_SIZE и со значения от 10 до HEIGHT-100

Обратите внимание, что в Python вам понадобиться random.randint, а в C++ все несколько сложнее через std::random_device rd;

Инциализация главного цикла

running = True  # Устанавливаем флаг для работы основного цикла
while running:  # Основной цикл программы
    screen.fill(WHITE)  # Очищаем экран и заполняем его белым цветом

    # Отрисовка массива: рисуем каждый элемент массива как прямоугольник
    for i, value in enumerate(array):
        # Рисуем столбец (бар) для текущего значения массива
        sort_visualizer.draw.rect(screen, BLUE, (i * BAR_WIDTH, HEIGHT - value - 50, BAR_WIDTH - 2, value))

    # Отрисовка кнопок: рисуем кнопки на экране
    sort_visualizer.draw.rect(screen, RED, button_sort)  # Кнопка сортировки
    sort_visualizer.draw.rect(screen, RED, button_algorithm)  # Кнопка выбора алгоритма

    # Отображение текста на кнопках
    screen.blit(font.render("Start Sorting", True, WHITE), (button_sort.x + 40, button_sort.y + 10))  # Текст на кнопке сортировки
    screen.blit(font.render(selected_algorithm, True, WHITE), (button_algorithm.x + 20, button_algorithm.y + 10))  # Текст на кнопке выбора алгоритма

    # Обработка событий: проверка всех событий (клики, закрытие окна и т.д.)
    for event in sort_visualizer.event.get():
        if event.type == sort_visualizer.QUIT:  # Если окно закрыто, выходим из цикла
            running = False
        if event.type == sort_visualizer.MOUSEBUTTONDOWN:  # Если нажата кнопка мыши
            # Проверяем, была ли нажата кнопка сортировки
            if button_sort.collidepoint(event.pos):
                array = generate_array()  # Перегенерация массива (пока без сортировки)
            # Проверяем, была ли нажата кнопка смены алгоритма
            elif button_algorithm.collidepoint(event.pos):
                # Меняем индекс алгоритма на следующий
                algorithm_index = (algorithm_index + 1) % len(algorithms)
                selected_algorithm = algorithms[algorithm_index]  # Обновляем выбранный алгоритм

    sort_visualizer.display.flip()  # Обновляем экран для отображения изменений

// Основной цикл приложения, продолжается, пока окно открыто
while (window.isOpen()) {

    // Обрабатываем все события, которые происходят в окне
    sf::Event event;
    while (window.pollEvent(event)) {

        // Если событие закрытия окна, то закрываем окно
        if (event.type == sf::Event::Closed)
            window.close();

        // Если нажата кнопка мыши
        if (event.type == sf::Event::MouseButtonPressed) {
            // Получаем текущую позицию мыши относительно окна
            sf::Vector2i mousePos = sf::Mouse::getPosition(window);

            // Проверяем, была ли нажата кнопка для генерации массива
            if (buttonRandom.getGlobalBounds().contains(mousePos.x, mousePos.y)) {
                generateArray(); // Генерируем новый массив
            }
            // Проверяем, была ли нажата кнопка для смены алгоритма
            else if (buttonAlgorithm.getGlobalBounds().contains(mousePos.x, mousePos.y)) {
                // Меняем индекс алгоритма (циклично через список алгоритмов)
                algorithm_index = (algorithm_index + 1) % algorithms.size();
            }
            // Проверяем, была ли нажата кнопка для сортировки
            else if (buttonSort.getGlobalBounds().contains(mousePos.x, mousePos.y)) {
                bubbleSort(window); // Запускаем сортировку пузырьком
            }
        }
    }

    // Очищаем окно, устанавливаем белый фон
    window.clear(sf::Color::White);

    // Рисуем столбцы для визуализации массива
    for (int i = 0; i < ARRAY_SIZE; i++) {
        // Создаём прямоугольник для каждого элемента массива
        sf::RectangleShape bar(sf::Vector2f(BAR_WIDTH - 2, array[i]));
        // Устанавливаем позицию столбца на экране
        bar.setPosition(i * BAR_WIDTH, HEIGHT - array[i] - 50);
        // Устанавливаем цвет столбца
        bar.setFillColor(sf::Color::Blue);
        // Отображаем столбец на экране
        window.draw(bar);
    }

    // Рисуем кнопки на экране
    window.draw(buttonRandom);
    window.draw(buttonAlgorithm);
    window.draw(buttonSort);

    // Создаём текстовый объект для отображения надписей на кнопках
    sf::Text text;
    text.setFont(font); // Устанавливаем шрифт
    text.setCharacterSize(20); // Устанавливаем размер текста
    text.setFillColor(sf::Color::White); // Устанавливаем цвет текста

    // Устанавливаем текст для кнопки "Генерировать массив" и отображаем
    text.setString(sf::String(L"Генерировать массив"));
    text.setPosition(30, 555); // Позиция текста на экране
    window.draw(text);

    // Устанавливаем текст для кнопки с текущим алгоритмом и отображаем
    text.setString(sf::String(algorithms[algorithm_index]));
    text.setPosition(350, 555); // Позиция текста на экране
    window.draw(text);

    // Устанавливаем текст для кнопки "Отсортировать" и отображаем
    text.setString(sf::String(L"Отсортировать"));
    text.setPosition(580, 555); // Позиция текста на экране
    window.draw(text);

    // Обновляем экран для отображения всех изменений
    window.display(); 
}

2 Итоговый код

PythonC++

3 Алгоритмы и их применение

• Быстрая сортировка и Сортировка слиянием — самые быстрые на практике, с временной сложностью O(n log n). Эти алгоритмы разделяют массив на подмассивы, что обеспечивает их эффективность.
• Пузырьковая сортировка, Сортировка вставками и Сортировка выбором — алгоритмы с временной сложностью O(n²). Они имеют простую реализацию, но менее эффективны для больших массивов. Подходят для сортировки небольших наборов данных.
• Пирамидальная сортировка также имеет временную сложность O(n²), отличается простотой реализации и низкими накладными расходами.

Сортировки с временной сложностью O(n log n) рекомендованы для работы с большими массивами данных, в то время как алгоритмы с O(n²) могут быть полезны для маленьких массивов или когда нужна простота реализации.

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

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

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

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

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

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

Задание для команды:

• Тестировщики пишут Unit-tests (договоритесь как будет называться фукнция, которую выбудете тестировать!)
• Программисты реализуют код программы, используя описание
• Менеджеры производят оценку алгоритма (наилучший, наихудший, средний случай), рисуют блок-схему , используя окно ниже:

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

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

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

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

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

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

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

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

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

Можно сделать сортировку еще быстрее, если менять местами не соседние элементы, а элементы на самом большом расстоянии друг от друга.

QuickSort является существенно улучшенным вариантом алгоритма сортировки с помощью прямого обмена (его варианты известны как «Пузырьковая сортировка» и «Шейкерная сортировка»), известного в том числе своей низкой эффективностью.

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

Общая идея алгоритма

1. Выбрать опорный элемент из массива. Это может быть любой элемент, но выбор влияет на эффективность алгоритма.
2. Разделить массив на три части:
   • элементы меньше опорного,
   • элементы, равные опорному,
   • элементы больше опорного.
3. Рекурсивно отсортировать подмассивы «меньших» и «больших» значений, если их длина больше единицы.

Псевдокодом реализация будет следующая:

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

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

На практике массив обычно делят не на три, а на две части, например: «меньшие опорного» и «равные и большие». Такой подход упрощает алгоритм разделения и делает его более эффективным.

Алгоритм был разработан Тони Хоаром в ходе работы над машинным переводом. В то время словарь хранился на магнитной ленте, и сортировка слов позволяла ускорить процесс перевода, так как переводы можно было находить за один прогон ленты без перемотки назад. QuickSort был придуман Хоаром в период его пребывания в СССР, где он изучал машинный перевод в МГУ и работал над созданием русско-английского разговорника.

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

def quick_sort_visual(start, end):
    if start >= end:
        return

    pivot = array[end]
    left = start
    for right in range(start, end):
        if array[right] < pivot:
            array[left], array[right] = array[right], array[left]
            left += 1
    array[left], array[end] = array[end], array[left]

    screen.fill(WHITE)
    for k, value in enumerate(array):
        color = RED if k == left or k == end else BLUE
        pygame.draw.rect(screen, color, (k * BAR_WIDTH, HEIGHT - value - 50, BAR_WIDTH - 2, value))
    pygame.draw.rect(screen, RED, button_random)
    pygame.draw.rect(screen, RED, button_algorithm)
    pygame.draw.rect(screen, RED, button_sort)
    screen.blit(font.render("Генерировать массив", True, WHITE), (button_random.x + 30, button_random.y + 5))
    screen.blit(font.render("Отсортировать", True, WHITE), (button_sort.x + 30, button_sort.y + 5))
    screen.blit(font.render(selected_algorithm, True, WHITE), (button_algorithm.x + 30, button_algorithm.y + 5))
    pygame.display.flip()
    time.sleep(0.05)

    quick_sort_visual(start, left - 1)
    quick_sort_visual(left + 1, end)

int partition(int low, int high) {
    int pivot = array[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (array[j] < pivot) {
            i++;
            std::swap(array[i], array[j]);
        }
    }
    std::swap(array[i + 1], array[high]);
    return (i + 1);
}

void quickSort(sf::RenderWindow& window, int low, int high) {
    if (low < high) {
        int pi = partition(low, high);

        // Рекурсивный вызов для сортировки двух частей
        quickSort(window, low, pi - 1);
        quickSort(window, pi + 1, high);
    }

    // Визуализация после каждого шага
    window.clear(sf::Color::White);
    for (int i = 0; i < array.size(); i++) {
        sf::RectangleShape bar(sf::Vector2f(BAR_WIDTH - 2, array[i]));
        bar.setPosition(i * BAR_WIDTH, HEIGHT - array[i] - 50);
        bar.setFillColor(sf::Color::Blue);
        window.draw(bar);
    }
    window.display();
    std::this_thread::sleep_for(std::chrono::milliseconds(20));
}

Примечание для желающих продолжить

Братец кролик предавался воспоминаниям о том, как когда-то он был участником одного интернет-форума. Там обитали разные любители головоломок и всяческих загадок, в том числе и компьютерных. Поскольку аудитория была не искушена каким-то сложным программированием, то и загадки из области общей эрудированности. Известно, что существует такое направление, как "Стеганография". Стеганография — это способ спрятать информацию внутри другой информации или физического объекта так, чтобы ее нельзя было обнаружить. В отличие от криптографии, которая скрывает содержимое тайного сообщения, стеганография скрывает сам факт его существования. Как правило, сообщение будет выглядеть как что-либо иное, например, как изображение, статья, список покупок, письмо или судоку.

Существует пять основных видов цифровой стеганографии.

• Текстовая стеганография
• Стеганография в изображениях
• Стеганография в видео
• Стеганография в звуке
• Сетевая стеганография

Самым простым методом стеганографии можно считать использование невидимых чернил (невидимого текста) или микрошрифтов.

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