Структуры и алгоритмы данных Python: поиск и сортировка - упражнения, практика, решение

Структуры данных и алгоритмы: поиск и сортировка [23 упражнения с решением]

[ Внизу страницы доступен редактор для написания и выполнения сценариев. ]

1. Напишите программу на Python для бинарного поиска. Перейти к редактору
Бинарный поиск: В компьютерных науках алгоритм бинарного поиска или полуинтервального поиска находит позицию целевого значения в отсортированном массиве. Алгоритм двоичного поиска может быть классифицирован как алгоритм поиска типа «разделяй и властвуй» и выполняется в логарифмическом времени.
Тестовые данные :
двоичный_поиск ([1,2,3,5,8], 6) -> False
двоичный_поиск ([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 для бинарного поиска упорядоченного списка. Перейти к редактору
Тестовые данные :
Ordered_binary_Search ([0, 1, 3, 8, 14, 18, 19, 34, 52], 3) -> True
Ordered_binary_Search ([0, 1, 3, 8, 14, 18, 19, 34, 52], 17) -> False
Нажмите меня, чтобы увидеть образец решения

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 для сортировки списка элементов, используя алгоритм сортировки оболочки. Перейти к редактору
Примечание. Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки». пары элементов далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».
Нажмите меня, чтобы увидеть образец решения

8. Напишите программу на Python для сортировки списка элементов, используя алгоритм сортировки слиянием. Перейти к редактору
Примечание. Согласно Википедии «Сортировка слиянием (также обычно пишется слиянием) является алгоритмом сортировки на основе сравнения O (n log n). Большинство реализаций производят стабильную сортировку, что означает, что реализация сохраняет порядок ввода равных элементов в отсортированной выход."
Нажмите меня, чтобы увидеть образец решения

9. Напишите программу на Python для сортировки списка элементов с использованием алгоритма быстрой сортировки. Перейти к редактору
Примечание. Согласно Википедии «Быстрая сортировка - это сортировка сравнения, это означает, что она может сортировать элементы любого типа, для которых определено отношение« меньше »(формально, общий порядок). Неэффективные реализации это не стабильная сортировка, то есть что относительный порядок элементов одинаковой сортировки не сохраняется. Быстрая сортировка может работать на месте с массивом, требуя небольших дополнительных объемов памяти для выполнения сортировки. "
Нажмите меня, чтобы увидеть образец решения

10. Напишите программу на Python для подсчета сортировки. Перейти к редактору
Согласно Википедии "В компьютерных науках сортировка подсчета - это алгоритм сортировки коллекции объектов по ключам, которые являются маленькими целыми числами; то есть это алгоритм целочисленной сортировки. Он работает путем подсчета количества объектов, у которых есть каждый отдельный ключ значение и использование арифметики по этим подсчетам для определения позиций каждого значения ключа в выходной последовательности. Время его выполнения линейно по количеству элементов и разности между максимальным и минимальным значениями ключа, поэтому оно подходит только для непосредственного использования в ситуациях, когда изменение в ключах не намного больше, чем количество элементов. Однако оно часто используется в качестве подпрограммы в другом алгоритме сортировки, основанном на сортировке, который может обрабатывать большие ключи более эффективно ».
Нажмите меня, чтобы увидеть образец решения

11. Напишите код Python для создания программы для Битонической сортировки. Перейти к редактору
Битоновая сортировка: согласно rutgers.edu - Битоновая сортировка - это алгоритм сортировки, основанный на сравнении, который может выполняться параллельно. Основное внимание уделяется преобразованию случайной последовательности чисел в битонную последовательность, которая монотонно увеличивается, а затем уменьшается. Вращения битовой последовательности также являются битонными. Более конкретно, битоническая сортировка может быть смоделирована как тип сети сортировки. Исходная несортированная последовательность поступает через входные каналы, где ряды компараторов переключают две записи в порядке возрастания или убывания. Алгоритм, созданный Кеном Бэтчером в 1968 году, состоит из двух частей. Во-первых, несортированная последовательность встроена в битовую последовательность; затем серия разбивается несколько раз на более мелкие последовательности, пока входные данные не будут отсортированы.
Нажмите меня, чтобы увидеть образец решения

12. Напишите программу на Python для сортировки списка элементов, используя сортировку Bogosort. Перейти к редактору
В информатике Bogosort - это особенно неэффективный алгоритм сортировки, основанный на парадигме генерации и тестирования. Алгоритм последовательно генерирует перестановки своего ввода, пока не найдет отсортированный. Это не полезно для сортировки, но может использоваться в образовательных целях, чтобы противопоставить его другим более реалистичным алгоритмам. Существуют две версии алгоритма: детерминированная версия, которая перечисляет все перестановки, пока не достигнет отсортированной, и рандомизированная версия, которая случайным образом переставляет свои входные данные. Аналогия для работы последней версии заключается в сортировке колоды карт, подбрасывая колоду в воздух, подбирая карты случайным образом и повторяя процесс, пока колода не отсортирована. Его название происходит от слова фиктивный.
Нажмите меня, чтобы увидеть образец решения

13. Напишите программу на Python для сортировки списка элементов с использованием сортировки Gnome. Перейти к редактору
Сортировка гномов - это алгоритм сортировки, первоначально предложенный доктором Хамидом Сарбази-Азадом (профессором вычислительной техники в Шарифском технологическом университете) в 2000 году и названный «глупой сортировкой» (не путать с богосортом), а затем описанный Диком. Грун и назвал "гномом рода". Алгоритм всегда находит первое место, где два соседних элемента находятся в неправильном порядке, и меняет их местами. Он использует тот факт, что выполнение обмена может привести к появлению новой неупорядоченной соседней пары только рядом с двумя замененными элементами.
Нажмите меня, чтобы увидеть образец решения

14. Напишите программу на Python для сортировки списка элементов, используя сортировку Cocktail shaker. Перейти к редактору
Из Википедии, коктейльный шейкер, [1] также известный как двунаправленная пузырьковая сортировка, [2] коктейльная сортировка, шейкерная сортировка (которая также может относиться к варианту выборочной сортировки), пульсация, случайная сортировка, [3] или челночная сортировка. , является разновидностью пузырьковой сортировки, которая является одновременно алгоритмом стабильной сортировки и сравнительной сортировкой. Алгоритм отличается от пузырьковой сортировки тем, что он сортирует в обоих направлениях при каждом проходе по списку. Этот алгоритм сортировки лишь немного сложнее в реализации, чем пузырьковая сортировка, и он решает проблему черепах в пузырьковых видах. Он обеспечивает лишь незначительные улучшения производительности и не улучшает асимптотическую производительность; Подобно пузырьковой сортировке, она не представляет практического интереса (сортировка вставок предпочтительнее для простых сортировок), хотя она находит некоторое применение в образовании.
Нажмите меня, чтобы увидеть образец решения

15. Напишите программу на Python для сортировки списка элементов с использованием Comb sort. Перейти к редактору
Расческа - это разновидность пузырчатой сортировки. Подобно сортировке «Шелл», сортировка «Гребень» увеличивает разрыв, используемый в сравнениях и обменах. Некоторые реализации используют сортировку вставкой, когда зазор меньше определенной величины. Основная идея состоит в том, чтобы исключить черепах или небольшие значения в конце списка, поскольку в пузырьковой сортировке они значительно замедляют сортировку. Кролики, большие значения в начале списка не представляют проблемы при пузырьковой сортировке. В пузырьковой сортировке, когда сравниваются любые два элемента, они всегда имеют разрыв 1. Основная идея гребенчатой сортировки состоит в том, что разрыв может быть намного больше 1.
Нажмите меня, чтобы увидеть образец решения

16. Напишите программу на Python для сортировки списка элементов с помощью Cycle sort. Перейти к редактору
Циклическая сортировка - это нестабильный алгоритм сортировки на месте, сортировка сравнения, которая теоретически оптимальна с точки зрения общего числа записей в исходный массив, в отличие от любого другого алгоритма сортировки на месте. Он основан на идее, что перестановка, подлежащая сортировке, может быть разбита на циклы, которые можно поворачивать по отдельности, чтобы получить отсортированный результат.
Нажмите меня, чтобы увидеть образец решения

17. Напишите программу на Python для сортировки списка элементов, используя сортировку Heap. Перейти к редактору
В информатике, heapsort (изобретенный JWJ Williams в 1964 году) является алгоритмом сортировки на основе сравнения. Heapsort можно рассматривать как улучшенную сортировку выбора: подобно этому алгоритму, он делит свои входные данные на отсортированную и несортированную области и интерактивно сжимает несортированную область, выделяя самый большой элемент и перемещая его в отсортированную область. Улучшение состоит в использовании структуры данных кучи, а не линейного поиска времени, чтобы найти максимум. Хотя на некоторых машинах он работает несколько медленнее, чем хорошо реализованная быстрая сортировка, он обладает преимуществом более благоприятного времени выполнения O (n log n) в худшем случае. Heapsort - это алгоритм на месте, но он не является стабильным. Запуск алгоритма heapsort, сортирующий массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются в соответствии со свойством кучи. Перед фактической сортировкой кратко показана древовидная структура кучи для иллюстрации.
Нажмите меня, чтобы увидеть образец решения

18. Напишите программу на Python для сортировки списка элементов, используя сортировку по массе. Перейти к редактору
Сортировка блинов - разговорный термин для математической задачи сортировки неупорядоченной стопки блинов в порядке их размера, когда шпатель может быть вставлен в любую точку стопки и использован для переворачивания всех блинов над ней. Число блинов - это минимальное количество бросков, необходимое для данного количества блинов. Впервые эту проблему обсудил американский геометр Джейкоб Э. Гудман. Это разновидность проблемы сортировки, в которой единственной допустимой операцией является обращение элементов некоторого префикса последовательности в обратном порядке.
Нажмите меня, чтобы увидеть образец решения

19. Напишите программу на Python для сортировки списка элементов, используя сортировку Radix. Перейти к редактору
Согласно Википедии «В компьютерной науке радикальная сортировка представляет собой не сравнительный алгоритм целочисленной сортировки, который сортирует данные по целочисленным ключам путем группировки ключей по отдельным цифрам, которые имеют одинаковые значимые позиции и значения».
Нажмите меня, чтобы увидеть образец решения

20. Напишите программу на Python для сортировки списка элементов, используя сортировку Selection. Перейти к редактору
Согласно Википедии «В компьютерной науке сортировка выбора является алгоритмом сортировки, в частности сортировкой по месту. Она имеет временную сложность O (n2), что делает ее неэффективной в больших списках и в целом работает хуже, чем аналогичная сортировка вставкой».
Нажмите меня, чтобы увидеть образец решения

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

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

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

Редактор кода Python:

Еще не все !

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