Бисерная сортировка
Необычный и в значительной степени непрактичный алгоритм сортировки, основанный на принципах подсчета.
Каждый элемент несортированного списка представляет собой набор бусинок на наборе стержней. Каждый стержень соответствует индексу, а количество бусин на каждом стержне представляет значение пожалуйста этим индексом в массиве.
Пусть сила тяжести потянет бусины вниз, заставляя их скапливаться в нижней части каждого стержня. Количество бусин в каждой стопке соответствует количеству элементов с определенной цифрой в несортированном списке.
После того, как сила тяжести потянет бусины вниз, перенесите бусины со стержней обратно в исходный список, сформировав новый список.
Список будет отсортирован в порядке возрастания.
Сложность:
Необычный и в значительной степени непрактичный алгоритм сортировки, основанный на принципах подсчета.
Каждый элемент несортированного списка представляет собой набор бусинок на наборе стержней. Каждый стержень соответствует индексу, а количество бусин на каждом стержне представляет значение пожалуйста этим индексом в массиве.
Пусть сила тяжести потянет бусины вниз, заставляя их скапливаться в нижней части каждого стержня. Количество бусин в каждой стопке соответствует количеству элементов с определенной цифрой в несортированном списке.
После того, как сила тяжести потянет бусины вниз, перенесите бусины со стержней обратно в исходный список, сформировав новый список.
Список будет отсортирован в порядке возрастания.
Сложность:
O(n^2)Алгоритм линейного поиска
Простой и понятный алгоритм поиска, используемый для поиска определенного элемента в списке, массиве или наборе данных.
Алгоритм:
Начните с начала списка и сравните каждый элемент один за другим с элементом, который надо найти.
- Если текущий элемент соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента в списке.
- Если текущий элемент не соответствует целевому элементу, перейдите к следующему элементу в списке и повторите сравнение.
Иногда конец списка достигается без обнаружения целевого элемента, и в этом случае поиск не увенчается успехом, и для обозначения этого часто возвращается специальное значение (например, -1).
Сложность:
Простой и понятный алгоритм поиска, используемый для поиска определенного элемента в списке, массиве или наборе данных.
Алгоритм:
Начните с начала списка и сравните каждый элемент один за другим с элементом, который надо найти.
- Если текущий элемент соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента в списке.
- Если текущий элемент не соответствует целевому элементу, перейдите к следующему элементу в списке и повторите сравнение.
Иногда конец списка достигается без обнаружения целевого элемента, и в этом случае поиск не увенчается успехом, и для обозначения этого часто возвращается специальное значение (например, -1).
Сложность:
O(n)Бинарный поиск
Алгоритм поиска, используемый для поиска определенного элемента в отсортированном массиве.
Шаг 1: Установите два указателя: один в начале списка и один в конце списка.
Шаг 2: Вычислите среднее положение между левым и правым указателями и сравните элемент в средней позиции с целевым элементом.
- Если элемент в средней позиции соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента.
- Если средний элемент больше целевого элемента, удалите правую половину пространства поиска, переместив правый указатель на одну позицию перед средним.
- Если средний элемент меньше целевого элемента, удалите левую половину пространства поиска, переместив левый указатель на одну позицию после середины.
Сложность:
Алгоритм поиска, используемый для поиска определенного элемента в отсортированном массиве.
Шаг 1: Установите два указателя: один в начале списка и один в конце списка.
Шаг 2: Вычислите среднее положение между левым и правым указателями и сравните элемент в средней позиции с целевым элементом.
- Если элемент в средней позиции соответствует целевому элементу, поиск успешен и возвращается позиция (индекс) целевого элемента.
- Если средний элемент больше целевого элемента, удалите правую половину пространства поиска, переместив правый указатель на одну позицию перед средним.
- Если средний элемент меньше целевого элемента, удалите левую половину пространства поиска, переместив левый указатель на одну позицию после середины.
Сложность:
O(log n)Ternary Search
Алгоритм поиска элемента в упорядоченном массиве.
Алгоритм:
Начинаем сравнивать искомое значение с элементами на двух точках деления:
- Если искомое значение меньше значения на первой точке деления, то поиск продолжается только в первой трети массива.
- Если искомое значение больше значения на первой точке деления, но меньше значения на второй точке деления, то поиск продолжается во второй трети массива.
- Если искомое значение больше значения на второй точке деления, то поиск продолжается только в третьей трети массива.
- Если искомое значение равно значению на одной из точек деления, то поиск заканчивается, и эта позиция возвращается как результат.
- Если искомое значение не найдено в массиве, то поиск продолжается до тех пор, пока длина промежутка не станет равной 0.
Сложность:
Алгоритм поиска элемента в упорядоченном массиве.
Алгоритм:
Начинаем сравнивать искомое значение с элементами на двух точках деления:
- Если искомое значение меньше значения на первой точке деления, то поиск продолжается только в первой трети массива.
- Если искомое значение больше значения на первой точке деления, но меньше значения на второй точке деления, то поиск продолжается во второй трети массива.
- Если искомое значение больше значения на второй точке деления, то поиск продолжается только в третьей трети массива.
- Если искомое значение равно значению на одной из точек деления, то поиск заканчивается, и эта позиция возвращается как результат.
- Если искомое значение не найдено в массиве, то поиск продолжается до тех пор, пока длина промежутка не станет равной 0.
Сложность:
O(log3 N)Jump Search
Алгоритм поиска элемента в упорядоченном массиве, который переходит через определенное количество элементов на каждой итерации для нахождения нужного значения.
Алгоритм:
Начинаем сравнивать искомое значение с элементом на каждом шаге, прыгая через фиксированное количество элементов.
- Если искомое значение меньше значения на текущей позиции, поиск вернется назад на фиксированное количество шагов и продолжит поиск в предыдущем интервале элементов.
- Если искомое значение больше значения на текущей позиции, поиск продолжится дальше, прыгая через фиксированное количество элементов.
- Если искомое значение равно значению на текущей позиции, то поиск заканчивается, и эта позиция возвращается как результат.
- Если искомое значение не найдено в массиве, алгоритм продолжает прыгать и сравнивать, пока не будет найдено значение или пока превысит размер массива.
Сложность:
Алгоритм поиска элемента в упорядоченном массиве, который переходит через определенное количество элементов на каждой итерации для нахождения нужного значения.
Алгоритм:
Начинаем сравнивать искомое значение с элементом на каждом шаге, прыгая через фиксированное количество элементов.
- Если искомое значение меньше значения на текущей позиции, поиск вернется назад на фиксированное количество шагов и продолжит поиск в предыдущем интервале элементов.
- Если искомое значение больше значения на текущей позиции, поиск продолжится дальше, прыгая через фиксированное количество элементов.
- Если искомое значение равно значению на текущей позиции, то поиск заканчивается, и эта позиция возвращается как результат.
- Если искомое значение не найдено в массиве, алгоритм продолжает прыгать и сравнивать, пока не будет найдено значение или пока превысит размер массива.
Сложность:
O(sqrt(n))Интерполяционный поиск
Алгоритм поиска элемента в упорядоченном массиве, который использует интерполяцию для приближенного нахождения позиции искомого значения.
Алгоритм:
Шаг 1: В цикле вычислите значение «pos», используя формулу положения датчика.
Шаг 2: Если это совпадение, верните индекс элемента и выйдите.
Шаг 3: Если элемент меньше arr[pos], вычислите положение зонда левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
Шаг 4: Повторяйте до тех пор, пока не будет найдено совпадение или пока подмассив не уменьшится до нуля.
Сложность:
Алгоритм поиска элемента в упорядоченном массиве, который использует интерполяцию для приближенного нахождения позиции искомого значения.
Алгоритм:
Шаг 1: В цикле вычислите значение «pos», используя формулу положения датчика.
Шаг 2: Если это совпадение, верните индекс элемента и выйдите.
Шаг 3: Если элемент меньше arr[pos], вычислите положение зонда левого подмассива. В противном случае вычислите то же самое в правом подмассиве.
Шаг 4: Повторяйте до тех пор, пока не будет найдено совпадение или пока подмассив не уменьшится до нуля.
Сложность:
O(log(log(n)))Sentinel Linear Search
Представляет собой тип линейного поиска, в котором количество сравнений уменьшено по сравнению с традиционным линейным поиском.
Основная идея заключается в добавлении дополнительного элемента в конец массива (т. е. значения дозорного), который соответствует ключу поиска.
Поступая так, мы можем избежать условной проверки конца массива в цикле и прекратить поиск раньше, как только найдем контрольный элемент. Это устраняет необходимость отдельной проверки конца массива, что приводит к небольшому улучшению производительности алгоритма в среднем случае.
Сложность:
Представляет собой тип линейного поиска, в котором количество сравнений уменьшено по сравнению с традиционным линейным поиском.
Основная идея заключается в добавлении дополнительного элемента в конец массива (т. е. значения дозорного), который соответствует ключу поиска.
Поступая так, мы можем избежать условной проверки конца массива в цикле и прекратить поиск раньше, как только найдем контрольный элемент. Это устраняет необходимость отдельной проверки конца массива, что приводит к небольшому улучшению производительности алгоритма в среднем случае.
Сложность:
O(n)Поиск в глубину
Алгоритм, используемый для обхода или поиска древовидных и графовых структур данных.
Алгоритм:
Шаг 1: Выберите начальную вершину (или узел), чтобы начать обход.
Шаг 2: Посетите выбранную вершину и отметьте ее как посещенную (чтобы она не посещалась повторно).
Шаг 3: Посетите каждого непосещенного соседа текущей вершины в систематическом порядке (например, слева направо или в любом определенном порядке).
- Если непосещенных соседей нет, вернитесь к предыдущей вершине. Именно здесь алгоритм приобретает свой характер «сначала глубина»; он идет как можно глубже вдоль ветки, прежде чем вернуться назад.
Шаг 4: Продолжайте процесс посещения, исследования и возврата до тех пор, пока не будут посещены все вершины.
Алгоритм, используемый для обхода или поиска древовидных и графовых структур данных.
Алгоритм:
Шаг 1: Выберите начальную вершину (или узел), чтобы начать обход.
Шаг 2: Посетите выбранную вершину и отметьте ее как посещенную (чтобы она не посещалась повторно).
Шаг 3: Посетите каждого непосещенного соседа текущей вершины в систематическом порядке (например, слева направо или в любом определенном порядке).
- Если непосещенных соседей нет, вернитесь к предыдущей вершине. Именно здесь алгоритм приобретает свой характер «сначала глубина»; он идет как можно глубже вдоль ветки, прежде чем вернуться назад.
Шаг 4: Продолжайте процесс посещения, исследования и возврата до тех пор, пока не будут посещены все вершины.
Поиск в ширину
Алгоритм, используемый для исследования и обхода древовидных и графовых структур данных.
Алгоритм:
Шаг 1: Выберите начальную вершину (или узел), чтобы начать обход.
Шаг 2: Посетите выбранную вершину и отметьте ее как посещенную (чтобы она не посещалась повторно).
Шаг 3: Исследуйте всех непосещенных соседей текущей вершины на текущем уровне.
Шаг 4: Используйте очередь для управления обходом. Поставьте в очередь непосещенных соседей.
Шаг 5: Исключить из очереди следующую вершину, чтобы она стала новой текущей вершиной.
Шаг 6: Продолжайте процесс посещения, исследования и постановки в очередь, пока не будут посещены все вершины.
Алгоритм, используемый для исследования и обхода древовидных и графовых структур данных.
Алгоритм:
Шаг 1: Выберите начальную вершину (или узел), чтобы начать обход.
Шаг 2: Посетите выбранную вершину и отметьте ее как посещенную (чтобы она не посещалась повторно).
Шаг 3: Исследуйте всех непосещенных соседей текущей вершины на текущем уровне.
Шаг 4: Используйте очередь для управления обходом. Поставьте в очередь непосещенных соседей.
Шаг 5: Исключить из очереди следующую вершину, чтобы она стала новой текущей вершиной.
Шаг 6: Продолжайте процесс посещения, исследования и постановки в очередь, пока не будут посещены все вершины.
Алгоритм Дейкстры
Алгоритм, который используется для поиска кратчайшего пути от одной исходной вершины ко всем остальным вершинам взвешенного графа, где каждое ребро имеет неотрицательный вес. Это особенно полезно для поиска оптимальных маршрутов в сетях, таких как дорожные карты или компьютерные сети.
Ключевые идеи:
- Кратчайший путь из одного источника.
Алгоритм Дейкстры фокусируется на поиске кратчайшего пути от одной исходной вершины ко всем остальным вершинам графа.
- Взвешенный граф.
Работает с графами, в которых каждое ребро имеет неотрицательный вес, представляющий стоимость или расстояние между двумя вершинами.
- Жадный подход.
Алгоритм Дейкстры использует жадный подход, итеративно выбирая вершину с наименьшим известным расстоянием до источника в качестве следующей вершины для исследования.
Сложность:
Алгоритм, который используется для поиска кратчайшего пути от одной исходной вершины ко всем остальным вершинам взвешенного графа, где каждое ребро имеет неотрицательный вес. Это особенно полезно для поиска оптимальных маршрутов в сетях, таких как дорожные карты или компьютерные сети.
Ключевые идеи:
- Кратчайший путь из одного источника.
Алгоритм Дейкстры фокусируется на поиске кратчайшего пути от одной исходной вершины ко всем остальным вершинам графа.
- Взвешенный граф.
Работает с графами, в которых каждое ребро имеет неотрицательный вес, представляющий стоимость или расстояние между двумя вершинами.
- Жадный подход.
Алгоритм Дейкстры использует жадный подход, итеративно выбирая вершину с наименьшим известным расстоянием до источника в качестве следующей вершины для исследования.
Сложность:
O(V^2)Шифр Rail Fence
Классический шифр, являющийся одним из простых методов шифрования текста, который основан на перестановке символов.
В этом шифре открытый текст вписывается в таблицу-шаблон, содержащую заданное количество строк – высоту изгороди. В каждую строку поочередно записывается одна буква со смещением от левого края шаблона, подобно изгороди. Зашифрованный текст создается объединением наборов символов из различных строк таблицы шаблона.
Для увеличения криптостойкости этого шифра можно использовать смещение при записи открытого текста в шаблон.
Классический шифр, являющийся одним из простых методов шифрования текста, который основан на перестановке символов.
В этом шифре открытый текст вписывается в таблицу-шаблон, содержащую заданное количество строк – высоту изгороди. В каждую строку поочередно записывается одна буква со смещением от левого края шаблона, подобно изгороди. Зашифрованный текст создается объединением наборов символов из различных строк таблицы шаблона.
Для увеличения криптостойкости этого шифра можно использовать смещение при записи открытого текста в шаблон.
Шифр Scytale
В криптографии шифр «Сцитала», известный также как шифр Древней Спарты, представляет собой прибор, используемый для осуществления перестановочного шифрования.
Прибор состоит из граненого цилиндра (жезла) и узкой полоски пергамента, которая обматывается вокруг цилиндра по спирали. На гранях цилиндра записывалось сообщение.
В криптографии шифр «Сцитала», известный также как шифр Древней Спарты, представляет собой прибор, используемый для осуществления перестановочного шифрования.
Прибор состоит из граненого цилиндра (жезла) и узкой полоски пергамента, которая обматывается вокруг цилиндра по спирали. На гранях цилиндра записывалось сообщение.
Шифр Цезаря
Шифр Цезаря – один из древнейших шифров. Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки.
Шифрование основано на использовании таблицы замен: в одну строку таблицы записываются буквы алфавита, а в другую – тот же алфавит, но сдвинутый влево на выбранное значение смещения. Символ, находящийся под символом исходного алфавита, – это заменяющий символ в шифротексте.
Шифр Цезаря – один из древнейших шифров. Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки.
Шифрование основано на использовании таблицы замен: в одну строку таблицы записываются буквы алфавита, а в другую – тот же алфавит, но сдвинутый влево на выбранное значение смещения. Символ, находящийся под символом исходного алфавита, – это заменяющий символ в шифротексте.
Шифр моноалфавитной подстановки
Метод шифрования, при котором каждая буква исходного текста заменяется на другую букву или символ из определенного набора подстановки.
Шифрование основано на использовании таблицы замен: в одну строку таблицы записываются буквы алфавита языка исходного сообщения, а в другую строку – символы, на которые заменяются буквы исходного сообщения.
Key – это кодовое слово, на основе которого формируется алфавит шифротекста. Первым шагом создания нового алфавита служит удаление всех повторяющихся букв, которые присутствуют в кодовом слове. Затем из алфавита удаляются все буквы кодового слова. На заключительном шаге кодовое слово внедряется в алфавит со смещением первого элемента кодового слова на величину параметра Offset.
Метод шифрования, при котором каждая буква исходного текста заменяется на другую букву или символ из определенного набора подстановки.
Шифрование основано на использовании таблицы замен: в одну строку таблицы записываются буквы алфавита языка исходного сообщения, а в другую строку – символы, на которые заменяются буквы исходного сообщения.
Key – это кодовое слово, на основе которого формируется алфавит шифротекста. Первым шагом создания нового алфавита служит удаление всех повторяющихся букв, которые присутствуют в кодовом слове. Затем из алфавита удаляются все буквы кодового слова. На заключительном шаге кодовое слово внедряется в алфавит со смещением первого элемента кодового слова на величину параметра Offset.
Шифр двойной перестановки
Метод шифрования, основанный на перестановке символов или букв входного текста. Он представляет собой комбинацию двух этапов перестановки: по строкам и по столбцам матрицы.
Процесс шифрования начинается с разбивки открытого текста на строки, которые затем заполняются в матрицу. Затем происходит перестановка символов по строкам и столбцам в матрице в соответствии с заданным ключом или алгоритмом. Полученная матрица становится шифротекстом.
Метод шифрования, основанный на перестановке символов или букв входного текста. Он представляет собой комбинацию двух этапов перестановки: по строкам и по столбцам матрицы.
Процесс шифрования начинается с разбивки открытого текста на строки, которые затем заполняются в матрицу. Затем происходит перестановка символов по строкам и столбцам в матрице в соответствии с заданным ключом или алгоритмом. Полученная матрица становится шифротекстом.
Шифр Виженера
Шифр Виженера можно рассматривать, как шифр, состоящий из последовательности нескольких шифров Цезаря с различными значениями сдвига алфавитов.
Для зашифровывания используется таблица замен, в которой каждой букве алфавита языка исходного сообщения ставится в соответствие несколько вариантов букв для представления в шифротексте. Для этого выбирается кодовое слово длиной n, которое делит открытый текст на отрезки та- кой же длины.
Далее составляется так называемая таблица Виженера: горизонтально записывается алфавит языка исходного сообщения, а вертикально под первым символом алфавита записывается кодовое слово. Заполнение таблицы осуществляется символами алфавита, начинающегося с очередной буквы кодового слова и циклически замыкающегося.
Элемент шифротекста выбирается на пересечении столбца, соответствующего букве открытого текста, и строки, соответствующей букве кодового слова.
Шифр Виженера можно рассматривать, как шифр, состоящий из последовательности нескольких шифров Цезаря с различными значениями сдвига алфавитов.
Для зашифровывания используется таблица замен, в которой каждой букве алфавита языка исходного сообщения ставится в соответствие несколько вариантов букв для представления в шифротексте. Для этого выбирается кодовое слово длиной n, которое делит открытый текст на отрезки та- кой же длины.
Далее составляется так называемая таблица Виженера: горизонтально записывается алфавит языка исходного сообщения, а вертикально под первым символом алфавита записывается кодовое слово. Заполнение таблицы осуществляется символами алфавита, начинающегося с очередной буквы кодового слова и циклически замыкающегося.
Элемент шифротекста выбирается на пересечении столбца, соответствующего букве открытого текста, и строки, соответствующей букве кодового слова.
Шифр Хилла
Шифр, основанный на матричном преобразовании текста.
Перед шифрованием необходимо каждому символу алфавита следует сопоставить код равный порядковому номеру символа в алфавите.
Затем коды символов открытого текста записываются в матрицу размером n × m и создается шифрующая матрица n × n.
Для шифрования матрица открытого текста умножается на шифрующую матрицу и вычисляется остаток от деления значения элементов матрицы-произведения на число символов выбранного алфавита.
Шифр, основанный на матричном преобразовании текста.
Перед шифрованием необходимо каждому символу алфавита следует сопоставить код равный порядковому номеру символа в алфавите.
Затем коды символов открытого текста записываются в матрицу размером n × m и создается шифрующая матрица n × n.
Для шифрования матрица открытого текста умножается на шифрующую матрицу и вычисляется остаток от деления значения элементов матрицы-произведения на число символов выбранного алфавита.
Комбинированный шифр ADFGVX
Шифр ADFGVX – один из самых известных шифров времен Первой мировой войны, который использовался немецкой армией. Особенность шифра заключается в том, что он основан на комбинации базовых операций замены и перестановки.
Шифрование осуществляется в два этапа:
1. На первом этапе сначала задается матрица-ключ 6 × 6, заполненная произвольно символами алфавита и цифрами от 0 до 9. Индексами строк и столбцов этой матрицы служат буквы A, D, F, G, V, X. Далее каждый символ открытого текста кодируется парой буквенных индексов, на пересечении которых в матрице-ключе он находится.
2. На втором этапе задается кодовое слово для перестановки столбцов, а затем ранее закодированный открытый текст переписывается построчно в матрицу с числом столбцов, равным длине ключевого слова. В завершение столбцы этой матрицы переставляются в соответствии с лексикографическим порядком букв ключевого слова и итоговый шифротекст образуется конкатенацией строк этой матрицы.
Шифр ADFGVX – один из самых известных шифров времен Первой мировой войны, который использовался немецкой армией. Особенность шифра заключается в том, что он основан на комбинации базовых операций замены и перестановки.
Шифрование осуществляется в два этапа:
1. На первом этапе сначала задается матрица-ключ 6 × 6, заполненная произвольно символами алфавита и цифрами от 0 до 9. Индексами строк и столбцов этой матрицы служат буквы A, D, F, G, V, X. Далее каждый символ открытого текста кодируется парой буквенных индексов, на пересечении которых в матрице-ключе он находится.
2. На втором этапе задается кодовое слово для перестановки столбцов, а затем ранее закодированный открытый текст переписывается построчно в матрицу с числом столбцов, равным длине ключевого слова. В завершение столбцы этой матрицы переставляются в соответствии с лексикографическим порядком букв ключевого слова и итоговый шифротекст образуется конкатенацией строк этой матрицы.
Шифр Плейфера
Шифр подстановки, который использует матрицу, называемую таблицей Плейфера, для шифрования и расшифровки сообщений.
Чтобы зашифровать текст, его необходимо разбить на пары символов (блоки).
Процесс шифрования подчиняется следующим правилам:
⁃ Если два символа совпадают или остался один символ, то к первому символу добавляется X и шифруется уже эта пара.
⁃ Если символы находятся в одной строке, то они замещаются на сим- волы, расположенные в ближайших от них ячейках справа.
⁃ Если символы находятся в одном столбце, то они замещаются на рас- положенные ниже в ближайших от них клетках
⁃ Если символы находятся в разных углах образуемого ими прямо- угольника, то они заменяются на символы, стоящие в противоположных углах этого прямоугольника в тех же строках.
Шифр подстановки, который использует матрицу, называемую таблицей Плейфера, для шифрования и расшифровки сообщений.
Чтобы зашифровать текст, его необходимо разбить на пары символов (блоки).
Процесс шифрования подчиняется следующим правилам:
⁃ Если два символа совпадают или остался один символ, то к первому символу добавляется X и шифруется уже эта пара.
⁃ Если символы находятся в одной строке, то они замещаются на сим- волы, расположенные в ближайших от них ячейках справа.
⁃ Если символы находятся в одном столбце, то они замещаются на рас- положенные ниже в ближайших от них клетках
⁃ Если символы находятся в разных углах образуемого ими прямо- угольника, то они заменяются на символы, стоящие в противоположных углах этого прямоугольника в тех же строках.