Сортировка связанного списка

[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]

Страница 1 из 1
1

Сортировка связанного списка

haav

Дата: Суббота, 22.01.2022, 20:43 | Сообщение # 1

Генералиссимус

Группа: Администраторы

Сообщений: 1373

Репутация: 50

Статус: Offline

Кто нибудь пробовал сортировать связанные списки?

Что я попробовал:

qsort
mergesort
отправка данных в массив , сортировка и возврат сортированных данных в список

У меня сложилось впечатление , что 3 вариант самый выгодный. И вот какие у меня получились тесты при заполнении 1000000 элементов:

mergesort

при полностью отсортированных данных: 0.2
при случайных данных: 0.9-1.1

qsort

при полностью отсортированных данных: очень долго , не дождешься. Если кол-во данных уменьшить в 10 раз , то 30 секунд
при случайных данных: 0.2

вариант с массивом

при полностью отсортированных данных: 0.06
при случайных данных: 0.21

Итог:

mergesort еще как-то можно использовать , особенно если данные уже частично отсортированы.
qsort можно использовать , только если уверен, что данные точно не отсортированы и разбросаны по списку случайно. Забавно правда?
вариант с массивом самый выгодный , поскольку всех отодрал по полной , несмотря на то, что выделялась лишняя память и данные туда сюда гонялись.

Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…