[devel] [JT] std::sort

[Hihin Ruslan]

Здравствуйте Alex V. Myltsev
  В сообщении от Sunday 17 December 2006 20:54 Alex V. Myltsev 
написал(a):

 > Этого мало. Это у вас вроде строгий частичный порядок получается, но
 > он
 >
 > допускает такую ситуацию: a<b<c<e, a<d<e, пары (b,d) и (c,d)
 > несравнимы.
  > То есть несравнимость может быть нетранзитивной, а это плохо:
 > например,
 >
 > подают нам на вход последовательность {a,c,d,b,e}; она
 > неупорядочена, а
  > сравнением соседних элементов мы этого обнаружить не можем. И
  > сортировка вся идёт лесом.
Как это не парадоксально,  но если читать что несравнимость - это один 
из видов равенства, то можно упорядочить в - вашем примере 
{a,b,c,d,e} или {a,(b,,d),e} - где (c,d,e) - любая перестановка из c,d,e
 Интереснее вариант  a<b<c<e, b<d<e, пары (a,d), (c,d) несравнимы
Имеем {a,b,(c,d),e}, т.е. значение (сортировочной меры) несравнимого 
элемента должно быть равно максимальному из несравнимых с ней 
элементов.
  Если-бы упорядочивали по убыванию, а не по возрастанию, то тогда-бы 
был минимальный элемент.
 В любом случае первый этап такой сортировки - каждому элементу 
присвоить сортировочную меру (вес), а потом сортировать уже элементы по 
этой сортировочной мере.

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

В нашем примере имеем первоначальные веса :
Исходя из b<d<e:
b=1
d=2
e=3

Исходя из a<b<c :
a=1
b=2
c=3

Т.к. у b входит в оба "графа", то имеем откорректированные веса первой 
ветки:
b=2; d=3; e=4;

Т.к. все ветки дерева пройдены и все элементы пройдены - имеем :
a=1 b=2 c=3 d=3 e=3
 
В общем имеем ситуацию сортировки элементов графа 


 > А требуемый strict weak ordering -- это почти полный порядок, но
 > только
 > каждый элемент может быть в нескольких экземплярах. "Нестрогий
 > полный
 > порядок", что ли :).
Это тоже алгоритм, но приводит к дублированию элементов.

 >
 > > Да я Страуса листал а у него книжка толстая и наполовину
 > > бестолковая.
 >
 > Google лучше.
 Может  я мои мысли помогут :)
 
-- 
С уважением Xихин Руслан
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип     : application/pgp-signature
Размер  : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url     : <http://lists.altlinux.org/pipermail/devel/attachments/20061217/5e43e060/attachment-0001.bin>