Упражнения по программированию на языке C, практика, решение: поиск и сортировка

C Алгоритм поиска и сортировки [17 упражнений с решением]

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

1. Напишите программу на C для бинарного поиска. Перейти к редактору
Бинарный поиск: В компьютерных науках алгоритм бинарного поиска или полуинтервального поиска находит позицию целевого значения в отсортированном массиве. Алгоритм двоичного поиска может быть классифицирован как алгоритм поиска типа «разделяй и властвуй» и выполняется в логарифмическом времени.
Нажмите меня, чтобы увидеть решение

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

3. Напишите программу на C для сортировки списка элементов, используя алгоритм пузырьковой сортировки. Перейти к редактору
Bubble Sort работает путем многократного обмена смежными элементами, если они находятся в неправильном порядке.
Нажмите меня, чтобы увидеть решение

4. Напишите программу на C для сортировки списка элементов, используя алгоритм сортировки вставками. Перейти к редактору
Вставка сортировки - это простой алгоритм сортировки, который создает окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен в больших списках, чем другие алгоритмы, такие как быстрая сортировка, heapsort или сортировка слиянием.
Нажмите меня, чтобы увидеть решение

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

6. Напишите программу на C для сортировки чисел с использованием алгоритма кучи (MAX heap). Перейти к редактору
Алгоритм сортировки, который работает, сначала организуя данные, которые будут отсортированы в специальный тип двоичного дерева, называемого кучей.
Нажмите меня, чтобы увидеть решение

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

8. Напишите программу на C для сортировки списка элементов с использованием алгоритма сортировки по основанию. Перейти к редактору
Radix sort - это не сравнительный алгоритм целочисленной сортировки, который сортирует данные по целочисленным ключам путем группировки ключей по отдельным цифрам, которые имеют одинаковые значимые позиции и значения.
Нажмите меня, чтобы увидеть решение

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

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

11. Напишите программу на C, которая сортирует числа, используя метод сортировки оболочки. Перейти к редактору
Согласно Википедии «Сортировка оболочки или метод Shell является сортировкой сравнения на месте. Это можно рассматривать как обобщение сортировки по обмену (пузырьковая сортировка) или сортировку по вставке (вставка сортировки). Метод начинается с сортировки пар элементы находятся далеко друг от друга, а затем постепенно сокращается разрыв между сравниваемыми элементами. Начиная с далеко расположенных элементов, можно перемещать некоторые неуместные элементы в положение быстрее, чем простой обмен ближайшими соседями ».
Нажмите меня, чтобы увидеть решение

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

13. Напишите программу на C, которая сортирует числа, используя метод сортировки по бисеру. Перейти к редактору
Согласно Википедии, «сортировка по бисеру, также называемая гравитационной сортировкой, является естественным алгоритмом сортировки, разработанным Джошуа Дж. Аруланандхамом, Кристианом С. Калуде и Майклом Дж. Диннином в 2002 году и опубликованным в Бюллетене Европейской ассоциации теоретических компьютерных наук». Как цифровые, так и аналоговые аппаратные реализации сортировки по бусинкам могут достигать времени сортировки O (n), однако реализация этого алгоритма, как правило, значительно медленнее в программном обеспечении и может использоваться только для сортировки списков положительных целых чисел. Казалось бы, даже в лучшем случае алгоритм требует O (n2) пробела ».
Нажмите меня, чтобы увидеть решение

14. Напишите программу на C, которая сортирует числа, используя метод сортировки Bogo. Перейти к редактору
В информатике Bogo Sort - это особенно неэффективный алгоритм сортировки, основанный на парадигме генерации и тестирования. Алгоритм последовательно генерирует перестановки своего ввода, пока не найдет отсортированный. Это не полезно для сортировки, но может использоваться в образовательных целях, чтобы противопоставить его другим более реалистичным алгоритмам.
Нажмите меня, чтобы увидеть решение

15. Напишите программу на C, которая сортирует числа, используя метод Cocktail Sort. Перейти к редактору
Коктейльный шейкер (также известный как двунаправленная пузырьковая сортировка, коктейльная сортировка, шейкерная сортировка, пульсация, случайная сортировка или челночная сортировка) - это разновидность пузырьковой сортировки, которая является одновременно алгоритмом стабильной сортировки и сравнительной сортировкой. Алгоритм отличается от пузырьковой сортировки тем, что он сортирует в обоих направлениях при каждом проходе по списку. Этот алгоритм сортировки лишь немного сложнее в реализации, чем пузырьковая сортировка, и он решает проблему черепах в пузырьковых видах. Он обеспечивает лишь незначительные улучшения производительности и не улучшает асимптотическую производительность; Подобно пузырьковому типу, он не представляет практического интереса, хотя и находит некоторое применение в образовании.
Нажмите меня, чтобы увидеть решение

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

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

Редактор кода программирования C:

Еще не все !

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