FreeBasic
Главная
Вход
Регистрация
Суббота, 20.07.2024, 08:39Приветствую Вас Гость | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Сортировка связанного списка
haavДата: Суббота, 22.01.2022, 20:43 | Сообщение # 1
Генералиссимус
Группа: Администраторы
Сообщений: 1362
Репутация: 49
Статус: Offline
Кто нибудь пробовал сортировать связанные списки?

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

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


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

mergesort

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

qsort

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

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

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

Итог:

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




Вы сохраняете власть над людьми покуда оставляете им что-то…Отберите у человека все, и этот человек уже будет неподвластен вам…
 
VitaminДата: Воскресенье, 23.01.2022, 12:13 | Сообщение # 2
Лейтенант
Группа: Пользователи
Сообщений: 55
Репутация: 4
Статус: Offline

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

а какой при этом был метод сортировки?
 
haavДата: Воскресенье, 23.01.2022, 12:15 | Сообщение # 3
Генералиссимус
Группа: Администраторы
Сообщений: 1362
Репутация: 49
Статус: Offline
Цитата Vitamin ()
а какой при этом был метод сортировки?

QSORT.


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