Поиск и сортировка [39 упражнений с решением]
[ Внизу страницы доступен редактор для написания и выполнения сценариев. ]
1. Напишите программу Python для двоичного поиска. Перейдите в редактор.
Двоичный поиск: в информатике алгоритм двоичного поиска или полуинтервального поиска находит позицию целевого значения в отсортированном массиве. Алгоритм бинарного поиска можно классифицировать как алгоритм поиска по дихотомии «разделяй и властвуй» и выполняется за логарифмическое время.
Тестовые данные :
binary_search ([1, 2,3,5,8], 6) -> False
binary_search ([1,2,3,5,8], 5) -> True
Щелкните меня, чтобы увидеть пример решения
2. Напишите программу на Python для последовательного поиска. Перейдите в редактор.
Последовательный поиск: В информатике линейный поиск или последовательный поиск — это метод поиска определенного значения в списке, который проверяет каждый элемент последовательно, пока не будет найден нужный элемент или пока список не будет исчерпан. Список не нужно упорядочивать.
Тестовые данные :
Sequential_Search ([11,23,58,31,56,77,43,12,65, 19], 31) -> (True, 3)
Щелкните меня, чтобы увидеть пример решения
3. Напишите программу Python для двоичного поиск по упорядоченному списку. Перейдите в редактор
Test Data :
Ordered_binary_Search ([0, 1, 3, 8, 14, 18, 19, 34, 52], 3) -> Истина
Ordered_binary_Search ([0, 1, 3, 8, 14, 18, 19, 34, 52], 17) -> Ложь
Щелкните меня, чтобы увидеть пример решения
4. Напишите программу Python для сортировки списка элементов с помощью алгоритма пузырьковой сортировки. Перейдите в редактор.
Примечание. Согласно Википедии, «пузырьковая сортировка, иногда называемая сортировкой по убыванию», представляет собой простой алгоритм сортировки, который многократно проходит через список для сортировки, сравнивает каждую пару соседних элементов и меняет их местами, если они расположены в неправильном порядке. Прохождение по списку повторяется до тех пор, пока не перестанут нуждаться в заменах, что указывает на то, что список отсортирован. Алгоритм, который является сортировкой сравнения, назван в честь того, как более мелкие элементы «всплывают» вверх списка. Хотя алгоритм прост, он слишком медленный и непрактичный для большинства проблем даже по сравнению с сортировкой вставкой. Это может быть практично, если входные данные обычно находятся в порядке сортировки, но иногда могут иметь некоторые неупорядоченные элементы почти в позиции. «
Примеры данных : [14,46,43,27,57,41,45,21,70]
Ожидаемый результат : [14, 21, 27, 41, 43, 45, 46, 57, 70]
Щелкните меня, чтобы увидеть пример решения
5. Напишите программу Python для сортировки списка элементов, используя алгоритм сортировки выбора. Перейдите в редактор
Примечание. Сортировка выбора улучшает пузырьковую сортировку, выполняя только один обмен для каждого прохода по списку..
Примеры данных : [14,46,43,27,57,41,45,21,70]
Ожидаемый результат : [14, 21, 27, 41, 43, 45, 46, 57, 70]
Щелкните меня, чтобы увидеть пример решения
6. Напишите программу Python для сортировки списка элементов с использованием алгоритма сортировки вставкой. Перейдите в редактор
Примечание. Согласно Википедии «Сортировка вставкой — это простой алгоритм сортировки, который строит окончательный отсортированный массив (или список) по одному элементу за раз. Он намного менее эффективен для больших списков, чем более продвинутые алгоритмы. такие как быстрая сортировка, сортировка в кучу или сортировка слиянием. «
Примеры данных : [14,46,43,27,57,41,45,21,70]
Ожидаемый результат : [14, 21, 27, 41, 43, 45, 46, 57, 70]
Щелкните меня, чтобы увидеть образец решения
7. Напишите программу Python для сортировки списка элементов с использованием алгоритма сортировки оболочки. Перейдите в редактор
Примечание. Согласно Википедии «Сортировка оболочки или метод оболочки, это сортировка на месте сравнения. Ее можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировки путем вставки ( сортировка вставкой). Этот метод начинается с сортировки пар элементов на большом расстоянии друг от друга, а затем постепенного уменьшения разрыва между сравниваемыми элементами. Начиная с удаленных друг от друга элементов, некоторые элементы, расположенные далеко друг от друга, могут перемещаться на место быстрее, чем простой ближайший соседний обмен. «
Щелкните меня, чтобы увидеть пример решения
8. Напишите программу Python для сортировки списка элементов с помощью сортировки слиянием алгоритм. Перейдите в редактор
Примечание. Согласно Википедии «Сортировка слиянием (также обычно обозначается слиянием) — это алгоритм сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода одинаковых элементов в отсортированном выводе. «
Щелкните меня, чтобы увидеть пример решения
9. Напишите программу Python для сортировки список элементов с использованием алгоритма быстрой сортировки. Перейдите в редактор
Примечание. Согласно Википедии «Быстрая сортировка — это сортировка сравнения, означающая, что она может сортировать элементы любого типа, для которых определено отношение« меньше »(формально общий порядок). Неэффективно реализациях это нестабильная сортировка, что означает, что относительный порядок одинаковых элементов сортировки не сохраняется. Quicksort может работать на месте в массиве, требуя небольшого дополнительного объема памяти для выполнения сортировки. «
Щелкните меня чтобы увидеть пример решения
10. Напишите программу на Python для подсчета сортировки. Перейти к редактору
Согласно Википедии «В информатике подсчетная сортировка — это алгоритм для сортировки коллекции объектов по ключам, которые являются небольшими целыми числами; то есть это алгоритм целочисленной сортировки. Он работает путем подсчета количество объектов, которые имеют каждое отдельное значение ключа, и использование арифметических операций с этими счетчиками для определения позиций каждого значения ключа в выходной последовательности. Время его работы линейно зависит от количества элементов и разницы между максимальным и минимальным значениями ключа, поэтому он подходит для прямого использования только в ситуациях, когда вариация ключей не намного превышает количество элементов. Однако он часто используется в качестве подпрограммы в другом алгоритме сортировки, сортировке по основанию, который может более эффективно обрабатывать большие ключи ».
Щелкните меня, чтобы увидеть пример решения
11. Напишите код Python для создания программы для Bitonic Sort. Перейдите в редактор.
Bitonic Sort: Согласно rutgers.edu — Bitonic sort — это алгоритм сортировки на основе сравнения, который может быть работать параллельно. Он ориентирован на преобразование случайной последовательности чисел в битонную последовательность, которая монотонно увеличивается, а затем уменьшается. Вращения битонической последовательности также являются битонными. Более конкретно, битонная сортировка может быть смоделирована как тип сортировочной сети. Первоначальная несортированная последовательность поступает через входные каналы, где ряд компараторов переключает две записи в порядке возрастания или убывания. Алгоритм, созданный Кеном Батчером в 1968 году, состоит из двух частей. Во-первых, несортированная последовательность встроена в битоническая последовательность; затем серия несколько раз разбивается на sma Следите за порядком, пока входные данные не будут отсортированы.
Щелкните меня, чтобы увидеть пример решения
12. Напишите программу Python для сортировки списка элементов с помощью сортировки Богосорт. Перейти к редактору
В информатике Богосорт — это особенно неэффективный алгоритм сортировки, основанный на парадигме генерации и тестирования. Алгоритм последовательно генерирует перестановки своих входных данных, пока не найдет ту, которая отсортирована. Он бесполезен для сортировки, но может использоваться в образовательных целях, чтобы противопоставить его другим более реалистичным алгоритмам. Существуют две версии алгоритма: детерминированная версия, которая перечисляет все перестановки, пока не попадет в отсортированную, и рандомизированная версия, которая случайным образом переставляет свой ввод. Аналогия работы последней версии — отсортировать колоду карт, подбрасывая колоду в воздух, случайным образом выбирая карты и повторяя этот процесс до тех пор, пока колода не будет отсортирована. Его название происходит от слова bogus.
Щелкните меня, чтобы увидеть образец решения
13. Напишите программу Python для сортировки списка элементов используя сортировку Gnome. Перейти к редактору
Gnome sort — это алгоритм сортировки, первоначально предложенный доктором Хамидом Сарбази-Азадом (профессором компьютерной инженерии Технологического университета Шарифа) в 2000 году и названный «глупая сортировка» (не путать с bogosort ), а затем позже описан Диком Грюном и назван «сортировка гномов». Алгоритм всегда находит первое место, где два соседних элемента находятся в неправильном порядке, и меняет их местами. Он использует тот факт, что при выполнении обмена новая смежная пара вне очереди может появиться только рядом с двумя замененными элементами.
Щелкните меня, чтобы увидеть пример решения
14. Напишите программу на Python для сортировки списка элементов с помощью сортировки с помощью коктейльного шейкера. Перейдите в редактор.
Из Википедии, Сортировка коктейлей [1], также известная как двунаправленная пузырьковая сортировка, [2] сортировка коктейлей, сортировка шейкер (что также может относиться к варианту сортировки по выбору), сортировка по пульсации, Сортировка в случайном порядке [3] или челночная сортировка — это разновидность пузырьковой сортировки, которая является одновременно стабильным алгоритмом сортировки и сортировкой сравнения. Алгоритм отличается от пузырьковой сортировки тем, что при каждом проходе по списку выполняется сортировка в обоих направлениях. Этот алгоритм сортировки лишь незначительно труднее реализовать, чем пузырьковая сортировка, и решает проблему черепах при пузырьковой сортировке. Он обеспечивает лишь незначительное улучшение производительности и не улучшает асимптотическую производительность; подобно пузырьковой сортировке, она не представляет практического интереса (для простых сортировок предпочтительна сортировка вставкой), хотя она находит некоторое применение в образовании.
Щелкните меня, чтобы увидеть образец решения
15. Напишите программу на Python для сортировки списка элементов с помощью сортировки Comb. Перейдите в редактор
Сортировка гребней — это вариант пузырьковой сортировки. Как и сортировка Shell, гребенчатая сортировка увеличивает разрыв, используемый при сравнениях и обменах. В некоторых реализациях используется сортировка вставкой, когда разрыв меньше определенной величины. Основная идея состоит в том, чтобы исключить черепах или небольшие значения в конце списка, поскольку при пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка не представляют проблемы при пузырьковой сортировке. При пузырьковой сортировке, когда любые два элемента сравниваются, у них всегда есть пробел, равный 1. Основная идея сортировки соты заключается в том, что пробел может быть намного больше, чем 1.
Щелкните меня, чтобы увидеть пример решения
16. Напишите программу Python для сортировки списка элементов с помощью циклической сортировки . Перейти к редактору
Циклическая сортировка — это нестабильный алгоритм сортировки на месте, сортировка сравнения, которая теоретически оптимальна с точки зрения общего количества записей в исходный массив, в отличие от любого другого алгоритма сортировки на месте. Он основан на идее, что сортируемую перестановку можно разложить на циклы, которые можно индивидуально чередовать для получения отсортированного результата.
Щелкните меня, чтобы увидеть пример решения
17. Напишите программу Python для сортировки списка элементов с помощью сортировки кучи. Перейти к редактору
В информатике heapsort (изобретенный Дж. У. Дж. Уильямсом в 1964 г.) — это алгоритм сортировки, основанный на сравнении. Кучную сортировку можно рассматривать как улучшенную сортировку выбора: как и этот алгоритм, он делит входные данные на отсортированную и несортированную область и интерактивно сжимает несортированную область, извлекая самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не поиска в линейном времени для поиска максимума. Хотя на практике на большинстве машин он несколько медленнее, чем хорошо реализованная быстрая сортировка, он имеет преимущество в более благоприятном времени выполнения O (n log n) в худшем случае.. Heapsort — это алгоритм на месте, но это не стабильная сортировка. Запуск алгоритма heapsort, сортирующего массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой вкратце показана древовидная структура кучи для иллюстрации.
Щелкните меня, чтобы увидеть пример решения
18. Напишите программа Python для сортировки списка элементов с помощью сортировки Pancake. Перейти в редактор
Сортировка блинов — это разговорный термин для математической задачи сортировки неупорядоченной стопки блинов по размеру, когда лопатку можно вставить в любую точку стопки и использовать для переворачивания всех блинов над ней. . Число блинов — это минимальное количество переворотов, необходимое для заданного количества блинов. Проблема была впервые обсуждена американским геометром Джейкобом Э. Гудманом. Это разновидность задачи сортировки, в которой единственная разрешенная операция — перевернуть элементы некоторого префикса последовательности.
Щелкните меня, чтобы увидеть пример решения
19. Напишите программу на Python для сортировки списка элементов с помощью сортировки Radix. Перейти к редактору
Согласно Википедии, «В информатике основанная на системе счисления сортировка — это алгоритм несравнительной целочисленной сортировки, который сортирует данные с целочисленными ключами путем группировки ключей по отдельным цифрам, которые имеют одинаковую значащую позицию и значение».
Щелкните меня, чтобы увидеть пример решения
20. Напишите программу Python для сортировки списка элементов с помощью сортировки по выбору. Перейти к редактору
Согласно Википедии «В информатике сортировка по выбору — это алгоритм сортировки, в частности сортировка на месте сравнения. Она имеет временную сложность O (n2), что делает ее неэффективной для больших списков и в целом работает хуже, чем аналогичная сортировка вставкой «.
Щелкните меня, чтобы увидеть пример решения
21. Напишите программу Python для сортировки списка элементы с помощью сортировки по времени. Перейдите в редактор
Щелкните меня, чтобы увидеть пример решения
22. Напишите программу Python для сортировки списка элементов с использованием топологической сортировки. Перейдите в редактор
Щелкните меня, чтобы увидеть пример решения
23. Напишите программу Python для сортировки списка элементов с помощью сортировки по дереву. Перейдите в редактор
Щелкните меня, чтобы увидеть пример решения
24. Напишите программу Python для сортировки номеров несортированного массива с помощью сортировки Wiggle. Перейдите в редактор.
Wiggle Sort:
Учитывая несортированный массив nums, измените его порядок на месте так, чтобы nums [0] = nums [2]. Например, если nums = [3, 5, 2, 1, 6, 4], один из возможных ответов — [1, 6, 2, 5, 3, 4].
Щелкните меня, чтобы увидеть образец решения
25. Напишите программу на Python для сортировки несортированных чисел с помощью Timsort.. Перейдите в редактор.
Из Википедии:
Timsort — это гибридный стабильный алгоритм сортировки, созданный на основе сортировки слиянием и сортировки вставкой, разработанный для хорошей работы со многими типами реальных данных. Он был реализован Тимом Петерсом в 2002 году для использования в языке программирования Python. Алгоритм находит подпоследовательности данных, которые уже упорядочены (запускаются), и использует их для более эффективной сортировки остатка. Это делается путем объединения прогонов до тех пор, пока не будут выполнены определенные критерии. Timsort является стандартным алгоритмом сортировки Python с версии 2.3.
Щелкните меня, чтобы увидеть пример решения
26. Напишите программу Python для сортировки несортированных числа с использованием сортировки Strand. Перейти в редактор
Strand sort — это рекурсивный алгоритм сортировки, который сортирует элементы списка в порядке возрастания. Он имеет наихудшую временную сложность O (n2), которая возникает при обратной сортировке входного списка. Он имеет временную сложность в лучшем случае O (n), которая возникает, когда входные данные представляют собой список, который уже отсортирован. Сортировка цепочек не выполняется, так как ее сложность по пространству составляет O (n).
Щелкните меня, чтобы увидеть пример решения
27. Напишите программа Python для сортировки несортированных чисел с помощью сортировки Stooge. Перейти в редактор
Stooge sort — это рекурсивный алгоритм сортировки. Он отличается исключительно плохой временной сложностью O (n log 3/log 1.5 ) = O (n 2.7095 … ). Таким образом, время выполнения алгоритма медленнее по сравнению с разумными алгоритмами сортировки и медленнее, чем пузырьковая сортировка, канонический пример довольно неэффективной сортировки. Однако он более эффективен, чем Slowsort. Название происходит от «Трех марионеток».
Щелкните меня, чтобы увидеть образец решения
28. Напишите программу Python для сортировки несортированных чисел с помощью рекурсивного Быстрая сортировка. Перейдите в редактор.
Quicksort — это алгоритм «разделяй и властвуй». Сначала он делит входной массив на два меньших подмассива: нижние элементы и высокие элементы. Затем он рекурсивно сортирует подмассивы.
Щелкните меня, чтобы увидеть пример решения
29. Напишите программу Python для сортировки данной коллекции чисел и их длины в порядке возрастания с использованием сортировки с рекурсивной вставкой. Перейдите в редактор
Щелкните меня, чтобы увидеть пример решения
30. Напишите программу Python для сортировки несортированных чисел с помощью рекурсивной пузырьковой сортировки. Перейдите в редактор
Щелкните меня, чтобы увидеть пример решения
31. Напишите программу Python для сортировки несортированных чисел с помощью быстрой сортировки произвольной сводной таблицы. Выбирает случайный индекс в качестве точки поворота. Перейдите в редактор
Щелкните меня, чтобы увидеть пример решения
32. Напишите программу Python для сортировки несортированных чисел с помощью быстрой сортировки с помощью нескольких клавиш. Перейдите в редактор
Из Википедии —
Быстрая сортировка по нескольким клавишам:
Этот алгоритм представляет собой комбинацию сортировки по основанию и быстрой сортировки. Выберите элемент из массива (стержень) и рассмотрите первый символ (ключ) строки (мульти-ключ). Разделите оставшиеся элементы на три набора: те, чей соответствующий символ меньше, равен и больше символа поворота. Рекурсивно отсортируйте разделы «меньше» и «больше» по одному и тому же символу.
Щелкните меня, чтобы увидеть пример решения
33. Напишите программу на Python для сортировки несортированных чисел с помощью сортировки в голубятне. Перейдите в редактор.
Сортировка «голубятня» — это алгоритм сортировки, который подходит для сортировки списков элементов, в которых количество элементов (n) и длина диапазона возможных значений ключа (N) примерно одинаковы. Это требует времени O (n + N). Это похоже на сортировку с подсчетом, но отличается тем, что она «перемещает элементы дважды: один раз в массив ведра и снова в конечный пункт назначения [тогда как] сортировка с подсчетом создает вспомогательный массив, а затем использует массив для вычисления конечного назначения каждого элемента и перемещения элемент там. «
Алгоритм откладывания ячеек работает следующим образом:
1. Задав массив значений для сортировки, настройте вспомогательный массив изначально пустых« ячеек », по одной ячейке для каждого ключа в диапазон ключей в исходном массиве.
2. Перейдя по исходному массиву, поместите каждое значение в ячейку, соответствующую его ключу, так, чтобы каждая ячейка в конечном итоге содержала список всех значений с этим ключом.
3.Перебирайтесь по массиву ячеек в возрастающем порядке ключей и для каждой ячейки помещайте его элементы в исходный массив в порядке возрастания.
Щелкните меня, чтобы увидеть пример решения
34. Напишите программу на Python для сортировки несортированных чисел с помощью сортировки по терпению. Перейти в редактор
Из Википедии:
В информатике сортировка по терпению — это алгоритм сортировки, вдохновленный и названный в честь терпения карточной игры. Вариант алгоритма эффективно вычисляет длину самой длинной возрастающей подпоследовательности в данном массиве.
Название алгоритма происходит от упрощенного варианта карточной игры терпения. Игра начинается с перетасованной колоды карт. Карты раздаются по одной в стопки на столе в соответствии со следующими правилами:
1. изначально стопок нет. Первая сданная карта образует новую стопку, состоящую из одной карты.
2. Каждая последующая карта кладется в крайнюю левую существующую стопку, верхняя карта которой имеет значение, большее или равное значению новой карты, или справа от всех существующих стопок, образуя новую стопку.
3.Когда не остается карт для раздачи, игра заканчивается.
Щелкните меня, чтобы увидеть образец решения
35. Напишите программу Python для сортировки нечетно-четной сортировки или нечетно-четной сортировки с транспонированием. Перейдите в редактор.
Из Википедии:
В вычислениях сортировка по нечетно-четному или нечетно-четному транспонированию (также известная как самопубликуемый источник с сортировкой по кирпичикам) или сортировка по четности является относительно простой алгоритм сортировки, изначально разработанный для использования на параллельных процессорах с локальными соединениями. Это сортировка сравнения, связанная с пузырьковой сортировкой, с которой она имеет много общих характеристик. Он работает, сравнивая все нечетные/четные индексированные пары смежных элементов в списке, и, если пара находится в неправильном порядке (первая больше, чем вторая), элементы меняются местами. На следующем шаге это повторяется для пар четных/нечетных индексов (соседних элементов). Затем он чередует нечетные/четные и четные/нечетные шаги, пока список не будет отсортирован.
Щелкните меня, чтобы увидеть образец решения
36. Напишите программу на Python для сортировки несортированных чисел, используя непараллельную реализацию сортировки с транспонированием нечетно-четно. Перейдите в редактор.
Из Википедии:
В вычислительной технике сортировка нечетно-четной или нечетно-четной транспозиции (также известная как сортировка по кирпичикам или сортировка по четности) является относительно простым алгоритмом сортировки, первоначально разработанным для использования на параллельных процессорах с локальными соединениями. Это сортировка сравнения, связанная с пузырьковой сортировкой, с которой она имеет много общих характеристик. Он работает, сравнивая все нечетные/четные индексированные пары соседних элементов в списке, и, если пара находится в неправильном порядке (первая больше, чем вторая), элементы меняются местами. На следующем шаге это повторяется для пар четных/нечетных индексов (соседних элементов). Затем поочередно выполняется чередование нечетных/четных и четных/нечетных шагов до тех пор, пока список не будет отсортирован.
Щелкните меня, чтобы увидеть образец решения
37. Напишите программу Python для сортировки несортированных чисел с помощью параллельной сортировки с нечетным четным транспонированием. Перейдите в редактор.
Нечетная четная транспозиция Параллельная сортировка:
Это реализация сортировки нечетно-четной транспозиции.
Она работает, выполняя серию параллельных перестановок между нечетными и четными парами переменных в списке.
Эта реализация представляет каждую переменную в списке с процессом, и каждый процесс взаимодействует со своими соседними процессами в списке для выполнения сравнений.
Они синхронизируются с блокировками и передачей сообщений но можно использовать и другие формы синхронизации.
Щелкните меня, чтобы увидеть пример решения
38. Напишите программу Python для сортировки несортированных строк, используя натуральный сорт. Перейдите в редактор.
Естественный порядок сортировки — это упорядочение строк в алфавитном порядке, за исключением того, что многозначные числа обрабатываются атомарно, то есть как если бы они были одним символом. Естественный порядок сортировки продвигался как более удобный («естественный»), чем машинно-ориентированный чистый алфавитный порядок..
Например, при сортировке по алфавиту «z11» будет отсортировано перед «z2», потому что «1» отсортировано как меньшее, чем «2», в то время как при естественной сортировке «z2» сортируется перед «z11», потому что «2 «сортируется как меньше» 11 «.
Алфавитная сортировка:
z11
z2
Естественная сортировка:
z2
z11
Щелкните меня, чтобы увидеть пример решения
39. Напишите программу Python для сортировки несортированных чисел с помощью сортировки слиянием и вставкой. Перейти к редактору
Из Википедии,
В информатике сортировка слиянием и вставкой или алгоритм Форда-Джонсона — это алгоритм сортировки сравнения, опубликованный в 1959 году Л. Р. Фордом-младшим и Селмером М. Джонсоном. В худшем случае он использует меньше сравнений, чем лучшие из ранее известных алгоритмов, сортировка двоичной вставкой и сортировка слиянием, и в течение 20 лет это был алгоритм сортировки с наименьшим количеством известных сравнений. Хотя это и не имеет практического значения, он остается теоретическим интересом в связи с проблемой сортировки с минимальным числом сравнений. Тот же алгоритм мог быть независимо открыт Станиславом Трибулой и Ченом Пингом.
Щелкните меня, чтобы увидеть образец решения
Редактор кода Python:
Еще впереди!
Не отправляйте никаких решений из приведенных выше упражнений здесь, если вы хотите внести свой вклад, перейдите на соответствующую страницу упражнений.
Проверьте свои навыки Python с помощью викторины w3resource
