сортировка шелла на списках о_О
Вроде как метод Шелла не требует случайного доступа, а в списке проще переставлять элементы
Так что все нормально
Так что все нормально
пара курсоров на нужном расстоянии пробегают и меняют.
ну мы там сначала переставляем элементы на ключевых позициях. поскольку это список, то чтоб до них добраться нам надо пройти весь список. это не случайный доступ, но тоже не сильно хорошо.
скажем, если ключи 9, 5, 3, 2, 1, то мы чтобы пройти элементы отстоящие друг ну друга на 9 позиции все равно пройдем весь список. обычная сортировка вставкой тут будет работать скорее всего быстрее, разве нет?
скажем, если ключи 9, 5, 3, 2, 1, то мы чтобы пройти элементы отстоящие друг ну друга на 9 позиции все равно пройдем весь список. обычная сортировка вставкой тут будет работать скорее всего быстрее, разве нет?
тут быстрее всего merge-sort.
а этот шелл неплохая иллюстрация оперирования списком сразу в нескольких местах,
и работать он тут будет с такой-же асимптотикой как и при случайном доступе.
а этот шелл неплохая иллюстрация оперирования списком сразу в нескольких местах,
и работать он тут будет с такой-же асимптотикой как и при случайном доступе.
уже вроде ответил 
для шага 9 тебе надо сначала сделать 9 сдвигов (то есть O(1 а потом гнать пару указателей по всему списку
мне кажется, что эта задача совсем не на сортировку, а на то чтоб не обдолбались с указателями
например, переставив два элемента можно случайно забыть, что указатели тоже поменялись местами
для шага 9 тебе надо сначала сделать 9 сдвигов (то есть O(1 а потом гнать пару указателей по всему списку
мне кажется, что эта задача совсем не на сортировку, а на то чтоб не обдолбались с указателями
например, переставив два элемента можно случайно забыть, что указатели тоже поменялись местами
А, догнал. тупил. 
да, скорее всего.. блин, забывать начинаю уже алгоритмы эти. пришлось в вики описание искать, тогда только понял, где не прав.
всем спасибо!
всем спасибо!
Оставить комментарий
Vadim69
что надо курить, чтоб такое задание детям дать? у меня сестра из универа притащила. дан односвязный список. отсортировать его методом Шелла. список, да еще односвязный - там же дофига ненужных действий по переходу к нужному элементу получится, или я чего-то не понимаю?