Алгоритмы. Сортировка Шелла. Реализация на Python и Java.

Подписаться 6 тыс.

Просмотров 4,3 тыс.

50% 1

Программу данного курса вы можете посмотреть по ссылке - docs.google.com/document/d/1U...
В этой лекции мы рассмотрим сортировку Шелла. Этот алгоритм является усовершенствованной версией алгоритма сортировки вставкой. Интересной особенностью этого алгоритма является зависимость эффективности от способа выбора шага. В лекции будет продемонстрировано реализация этого алгоритма на Python и Java. Также проведены вычислительные эксперименты по исследованию эффективности как самого алгоритма так и выбора шага.
Ссылка на конспект этой лекции - drive.google.com/file/d/1edb5...
Ссылка на реализацию этого алгоритма на Python и Java - drive.google.com/drive/folder...

Опубликовано:

26 окт 2020

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 21

@user-ud6rn1bc1p Год назад

Потрясающая лекция!) Спасибо большое за подробно разжёванный материал. Было очень интересно.

@radmitr 6 месяцев назад

Как всегда лекция на высоте!

@radmitr 6 месяцев назад

Для вычисления шага по Кнуту на Java можно ещё так: - в конструкторе добавить равно: `...2

@mosyan4ik 2 года назад

Спасибо за прекрасное объяснение! Качественный контент 👍

@user-yh8mj6pf9k 3 года назад

Спасибо за реализацию на Java

@vitaliksavchuk7536 Год назад

Годнота

@volselongames4505 2 года назад

Александр добрый вечер, хотел такой вопрос задать, я когда смотрел твоё видео про пузырьковую сортировку, ты говорил то что данный алгоритм не эффективный и то что его можно отнести к учебным, у данного алгоритма сложность O(n^2) а теперь я все алгоритмы сортировки пересмотрел по твоим видео, и у них у всех сложность по времени O(n^2), а по памяти O(n). Так а какую в итоге то использовать, или на своё усмотрение, к какой душа лежит😆😆😆

@volselongames4505 2 года назад

всё я разобрался спасибо👍👍👍

@oleksandrtsymbaliuk 2 года назад

Ой не все вы посмотрели по сортировкам :) Например сортировка слиянием и быстрая сортировка дают O(n ln(n)). А использовать в общем случае - модифицированную быструю сортировку. Но если есть возможность то в идеале поразрядную.

@volselongames4505 2 года назад

@Oleksandr Tsymbaliuk да да, я там посмотрел уже, спасибо большое👍👍👍

@georgyvanopas1453 2 года назад

А как создать счётчик перестановок и сравнений в питоне?

@oleksandrtsymbaliuk 2 года назад

Ну самый простой способ - создайте где глобальные переменные. Инициализируйте их нулями. А в самой функции сортировки увеличивайте их на единицу при каждом сравнении и перестановке. После работы функции в этих переменных и будет хранится количество сравнений и перестановок.

@ldSt3345 3 года назад

Но ведь в алгоритме Шелла формируются подмассивы из элементов с соответствующим шагом, а внутри них используется инзершн сорт...

@oleksandrtsymbaliuk 3 года назад

Добрый день. Нет алгоритм Шелла именно такой как описано в видео. В этом несложно убедится прочтя или классические работы Дональда Кнута или оригинальную статью с описанием данного алгоритма. То что вы описываете это небольшое усовершенствование которое используется в алгоритме быстрой сортировки. И в этом также легко убедиться прочтя монографию Седжевика.