Алгоритм поиска и сортировки JavaScript - упражнения, практика, решение

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

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

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

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

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

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

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

7. Напишите программу на JavaScript для сортировки списка элементов, используя Bubble sort. Перейти к редактору
Согласно Википедии «Пузырьковая сортировка, иногда называемая тонкой сортировкой, представляет собой простой алгоритм сортировки, который последовательно проходит по списку для сортировки, сравнивает каждую пару смежных элементов и меняет их местами, если они находятся в неправильном порядке. Список повторяется до тех пор, пока не требуется перестановка, что указывает на сортировку списка. Алгоритм, который является сортировкой сравнения, назван так, как меньшие элементы «всплывают» в верхнюю часть списка. Хотя алгоритм прост, он является слишком медленным и непрактичным для большинства проблем, даже если сравнивать с сортировкой вставкой. Это может быть практичным, если входные данные обычно находятся в порядке сортировки, но иногда могут иметь некоторые неупорядоченные элементы, находящиеся почти на месте ».
Нажмите меня, чтобы увидеть решение

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

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

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

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

12. Напишите программу на JavaScript для сортировки списка элементов с помощью Flash sort. Перейти к редактору
Flashsort - это алгоритм сортировки распределения, показывающий линейную вычислительную сложность O (n) для равномерно распределенных наборов данных и относительно небольшую потребность в дополнительной памяти. Оригинальная работа была опубликована в 1998 году Карлом-Дитрихом Нойбертом. Основная идея флэш-сортировки заключается в том, что в наборе данных с известным распределением легко сразу оценить, где должен быть размещен элемент после сортировки, когда известен диапазон набора.
Нажмите меня, чтобы увидеть решение

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

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

Еще не все !

* Чтобы запустить код, наведите курсор мыши на панель результатов и нажмите кнопку «RERUN». *

Демонстрация в реальном времени:

См. Javascript-common-editor Pen от w3resource ( @ w3resource ) в CodePen .