Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Сортированные списки. [D7, WinXP]

Страницы: 1 2 >
liver © (2005-05-25 09:34:00)
Надо написать как можно более быстрый сортированный список.
У кого какие есть идеи ?
Может кто уже писал такое, вернее такое писал каждый. интересует оптимизированный код. Наиболее эыффективный.

Digitman (2005-05-26 13:34:00) [1]

> у меня Double в массиве

да хоть Triple - неважно.

> значения могут быть любые, одинаковые, повторяющиеся, уникальные

под "что чаще" из перечисленного как раз и выбирай алгоритм

liver (2005-05-26 13:29:00) [2]
значения могут быть любые, одинаковые, повторяющиеся, уникальные и т.д.

liver (2005-05-26 13:29:00) [3]
у меня Double в массиве

Digitman (2005-05-26 11:57:00) [4]

> QuickSort побыстрее будет судя по

.. на конкретномряду ..
а на твоем может и медленней быть

liver (2005-05-26 11:53:00) [5]
QuickSort побыстрее будет судя по %DELPHI%\Demos\Threads\thrddemo.dpr

liver (2005-05-26 11:51:00) [6]
будем значит проводить тесты

Digitman (2005-05-26 11:38:00) [7]

> liver (26.05.05 10:50) [23]

основное время при выполнении сортировки "на месте" любым алгоритмом, тратится на "обмен элементов местами".

в случае пузырька и заведомо упорядоченого ряда неуникальных значений ни один обмен не осуществляется, и работа алгоритма завершается в один проход цикла сравнений.

в случае рекурс.алгоритмов, базирующихся на "половинном делении", сортировка того же ряда как правило приводит как минимум к одному "обмену".

Anatoly Podgoretsky (2005-05-26 11:30:00) [8]
liver (26.05.05 10:50) [23]
если массив упорядоченый то бинарная сортировка выигрывает у пузырька. во всяком случае я такое прочел.

На самом деле наоборот, ты больше такую траву не кури, то есть не читай такие испочники.

Digitman (2005-05-26 10:55:00) [9]
там представлено всего 3 широкоизвестных алгоритма, но ничто не мешает добавить еще косой десяток интересующих, дабы иметь более полную картину

Digitman (2005-05-26 10:54:00) [10]

> liver (26.05.05 10:50) [23]

ты не гадай на кофейной гуще, а возьми и поэкспериментируй с готовым демо-проектом (%DELPHI%\Demos\Threads\thrddemo.dpr), наглядно (визуально) показывающим преимущества и недостатки того или иного алгоритмов сортировки на том или ином ряду

liver (2005-05-26 10:50:00) [11]
если массив упорядоченый то бинарная сортировка выигрывает у пузырька. во всяком случае я такое прочел.

Digitman (2005-05-26 10:05:00) [12]

> liver (26.05.05 09:20) [20]
> Если вставлять на этапе вставки то скорость будет больше
> чем все сразу сортировать

это ты загнул.

Anatoly Podgoretsky (2005-05-26 09:48:00) [13]
liver (26.05.05 09:20) [20]
Кто тебе такое сказал.

liver (2005-05-26 09:20:00) [14]
Digitman ©

нет, не от балды.
Сортировка бинарная быстрее чем пузырьком.
Если вставлять на этапе вставки то скорость будет больше чем все сразу сортировать.

Андрюха7 (2005-05-25 16:42:00) [15]
http://algolist.manual.ru/ds/index.php
На этом сайте много полезной инфы на эту и не только темы.

Alex Konshin (2005-05-25 13:02:00) [16]
Ты сначала определись, для чего тебе этот список. И список-ли тебе нужен.
Нужен ли тебе будет последовательный доступ к элементам?
Нужен ли доступ по номеру?
Будет ли он динамически изменяться или после построения он будет практически read-only?

Даже если последовательный доступ нужен, это не означает автоматически, что нельзя использовать те же бинарные деревья, наприр AVL-tree - их замечательно можно обходить влюбом порядке. А уж поиск/вставка/удаление там очень быстрые.

Смотри AVLtree и Arrays нв моем сайте из анкеты.

Digitman (2005-05-25 10:27:00) [17]

> я так думаю что лучше сортировать на этапе вставки
> много мелких...я так думаю

решение - от балды ?

наверно, да)

ты должен определиться, нужно ли тебе иметь для каких-то задач уже отсортированный список между некими двумя последовательными вставками ... если не нужно, то и резона нет вставлять элемент с учетом упорядоченности списка

liver (2005-05-25 10:22:00) [18]
я так думаю что лучше сортировать на этапе вставки
много мелких...я так думаю

Anatoly Podgoretsky (2005-05-25 10:17:00) [19]
Ты должен сам решить, много мелких тормозов или один большой.

Anatoly Podgoretsky (2005-05-25 10:16:00) [20]
Так все таки вставка или сортировка, а вставляет кто?

Страницы: 1 2 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »