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

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

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

Алгоритм сортировки

Страницы: < 1 2
Styx_ © (2005-12-13 23:21:00)
Добрый день!

Необходимо отсортировать массив объектов с использованием функции сравнения элементов f( a, b), которая может возвращать значения "больше" (1), "меньше" (-1) и "объекты несравнимы" (0), причём в принципе возможна ситуация, когда
a< b< c< a
Что-то я не могу сообразить, как бы это всё отсортировать, а в случае возникновения указанной неразрешимости - не впасть в бесконечный цикл, а попытаться выдать результат с наименьшим числом несоответствий.

Нужно всё это, собственно, для сортировки графических примитивов в "алгоритме художника".

Спасибо!

Leonid Troyanovsky (2005-12-14 13:13:00) [21]

> Styx_ (14.12.05 13:01) [13]

> расположенные дальше, должны отрисовываться раньше; порядок
> отрисовки объектов с непересекающимися проекциями непринципиален.

Вот именно такой интерпретации и следует придерживаться, т.е.
f(a, b) = -1 ~ b ближе a
f(a, b) = 0 ~ a, b равноудалены
f(a, b) = 1 ~ a ближе b.

И никакого "зацикливания" не будет.

Ну, а TList сортирует путем QuickSort, т.е. лучше пузырька.

--
Regards, LVT.

Styx_ (2005-12-14 13:10:00) [22]
Делается всё это не на Delphi, а на Action Script во Flash... Уж простите, что залез с этим сюда, но здесь люди явно более подкованные, чем на Flash-форумах :) Соответственно использовался метод sort() объекта Array, который точно так же позволяет задавать произвольную функцию сравнения. Насколько я понимаю (судя по трассировке вызовов моей функции), он работает именно пузырьком.

Собственно, в чем суть:
есть исходный массив
a,b,c,d
f(a,b)=-1
f(b,c)=0
f(c,d)=-1
С точки зрения "пузырька" он отсортирован, но фактически может быть, что
f(a,c)=1

> Чего-то не так с физической моделью

Не понимаю.
-1 -> a ближе, чем b,
1 -> b ближе, чем a

Styx_ (2005-12-14 13:01:00) [23]

> дай определение "ближе-дальше" для случая именно пересекающихся
> проекций

Определение вполне бытовое :)
С точки зрения отрисовки по "алгоритму художника" - объекты, расположенные дальше, должны отрисовываться раньше; порядок отрисовки объектов с непересекающимися проекциями непринципиален.

TUser (2005-12-14 13:00:00) [24]
Задача решаема.

> Но вылезают ошибки сортировки :(

Приведи свою реализацию пузырька.

Leonid Troyanovsky (2005-12-14 12:57:00) [25]

> Styx_ (13.12.05 23:21)

> функции сравнения элементов f(a,b), которая может возвращать
> значения "больше" (1), "меньше" (-1) и "объекты несравнимы"
> (0), причём в принципе возможна ситуация, когда
> a < b < c < a

> Styx_ (14.12.05 12:43) [9]
> 0: проекции объектов не пересекаются
> -1: проекции объектов пересекаются, a ближе к наблюдателю

Т.е., "a" ближе к наблюдателю, чем "a"?
Чего-то не так с физической моделью.

А, вообще-то, у TList есть метод Sort, который сортирует элементы
по произвольному критерию. Задай оную функцию и сортируй.

--
Regards, LVT.

Digitman (2005-12-14 12:52:00) [26]

> a ближе к наблюдателю

> b ближе к наблюдателю

дай определение "ближе-дальше" для случая именно пересекающихся проекций

Styx_ (2005-12-14 12:43:00) [27]
А, я понял, что неправильно применил термин "перекрывает". Вот более точное описание:

0: проекции объектов не пересекаются
-1: проекции объектов пересекаются, a ближе к наблюдателю
1: проекции объектов пересекаются, b ближе к наблюдателю

Styx_ (2005-12-14 12:30:00) [28]

> т.е. частичное перекрытие невозможно по условию .. так ?

Почему невозможно? Собственно, только оно и интересует - в случае полного объект можно просто не отрисовывать, и сортировка ни к чему.

Digitman (2005-12-14 12:20:00) [29]

> перекрывает

т.е. частичное перекрытие невозможно по условию .. так ?

Styx_ (2005-12-14 12:15:00) [30]

> А что значит несравнимые объекты

Значение функции f(a,b) трактуется следующим образом:
-1: a в проекции перекрывает b
1: b в проекции перекрывает a
0: проекции объектов не пересекаются

Причем случай с циклом пока не принципиален, потому как в трёхмерной модели, которую мне нужно отрисовать, таких циклов не будет.

А пузырьком и я сделал... Но вылезают ошибки сортировки :(

Я так понимаю, что надо заполнить матрицу результатами сравнения всех пар объектов и далее отсортировать строки и столбцы таким образом, чтобывыше диагонали все значения были, скажем, неотрицательными. Только вот дальше этой мысли моя голова пока не может продвинуться :)

TUser (2005-12-14 09:14:00) [31]
Я что-то подобное делал. Объекты могли быть нормально сортируемыми, а могли образовывать цикл. Все сделал обычным пузырьком.

TUser (2005-12-14 09:12:00) [32]
А что значит несравнимые объекты. Должно быть определено отношение порядка (а значит они всегда сравнимы), иначе ничего отсортировать нельзя.

Думкин (2005-12-14 06:49:00) [33]
> Styx_ (13.12.05 23:21)

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

Styx_ (2005-12-14 00:50:00) [34]
А каким "обыкновенным"? Все известные мне алгоритмы подразумевают, что 0 - это равенство, и из
f(a,b) = -1 и f(b,c) = 0 следует, что f(a,c)=-1
Что в данном случае не так, и действительно нужно вычислить f() для всех пар... Или я чего-то не понимаю?

PAVIA (2005-12-13 23:39:00) [35]
Просто сортируешь обыкновенным методом. Алгоритм художника как раз и не дает правельного результат на том случае. Если такой случай имеет место, то для нахождения наименьшего числа несоответствий нужен полный перебором всех вариантов. Что бывает не приемлимым из-за большого числа объектов.

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

Наверх

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