есть вектор точек с координатами ХУ. std::vector<Points>, где
Points структура, хранящая Х/У.
на плоскости они разбросаны, к примеру, вот так:

 1   2   3
 6   5   4
 8   7   9
10  12  11

номерами — я просто как бы ссылки дал на все объекты Points.
как видим они даже могут изначально быть неупорядоченными.
задача строго упорядочить по таким одновременным условиям:

задается некий Хо, относительно которого надо получить сортировку
по Иксам по убыванию(равенству) влево от Хо и тут же по возрастанию
вправо от Хо. И все это на фоне убывания У в одном варианте прохода
алгоритма, и по возрастанию — в другом.
т.о. для первого варианта сортировки
(где Хо пусть равен координате х для точек 2-5-7-12 исходной
последовательности) получим:

 2   1   3    ||
 5   4   6    ||
 8   7   9    ||
11  10  12    \/ У убывает

во втором (У возрастает):

11  10  12
 8   7   9
 5   4   6
 2   1   3

и как можете заметить внутри каждого среза с одним Уi
относительно Хо, на примере первого среза из
первого варианта:

<---
2  1
     --->
      3

сперва две точки по убыванию икса, относительно Хо,
потом третья — идущая по возрастанию...
точка 1 принадлежит Хо, точка 3 строго больше.

вопрос — как сие сделать на С++???
понятно — что списки на каждый срез можно сделать. отдельно
все что больше Хо отсортировать в убывание, потом остаток в возрастание.
потом склеить...

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

есть идеи? может я чтото упускаю из виду?

Здравствуйте, Аноним, Вы писали:

Похоже, что проблема тут не с алгоритмом сортировки, а с пониманием условия по которому нужно сортировать. А сам алгоритм можно выбрать практически любой.

А>и как можете заметить внутри каждого среза с одним Уi
А>относительно Хо, на примере первого среза из
А>первого варианта:
А>

А><---
А>2  1
     --->>
А>      3
А>

А>сперва две точки по убыванию икса, относительно Хо,
А>потом третья — идущая по возрастанию...
А>точка 1 принадлежит Хо, точка 3 строго больше.

Очень плохое описание. Мне кажется, что оно противоречит примерам.

А>вопрос — как сие сделать на С++???

std::sort же.

Использовать так:

std::vector<Points> points;
...
std::sort(points.begin(), points.end(), cmp(x0));

Описав вначале предикат сравнения:

struct cmp {
    cmp(int X0): x0(X0) {}
    bool operator()(const Point& a, const Point& b) const {
        if (a.y != b.y) 
            return a.y < b.y; // точки всегда упорядочены по ординатам
        if (a.x <= x0 && b.x <= x0)
            return a.x > b.x; // точки слева от прямой x=x0 упорядочены в по убыванию абсцисс
        else
            return a.x < b.x; // точки из правой полуплоскости и из разных полуплоскостей упорядочены по возрастанию абсцисс
    }
    int x0;
};

Соответственно, второй случай, с инвертированием оси Y, делается заменой одного символа в кода, ну или добавлением параметра, если так тебе будет удобнее.

Здравствуйте, watch-maker, Вы писали:

WM>Здравствуйте, Аноним, Вы писали:

WM>Похоже, что проблема тут не с алгоритмом сортировки, а с пониманием условия по которому нужно сортировать. А сам алгоритм можно выбрать практически любой.

А>>и как можете заметить внутри каждого среза с одним Уi
А>>относительно Хо, на примере первого среза из
А>>первого варианта:
А>>

А>><---
А>>2  1
     --->>>
А>>      3
А>>

А>>сперва две точки по убыванию икса, относительно Хо,
А>>потом третья — идущая по возрастанию...
А>>точка 1 принадлежит Хо, точка 3 строго больше.

WM>Очень плохое описание. Мне кажется, что оно противоречит примерам.

А>>вопрос — как сие сделать на С++???

WM>std::sort же.

WM>Использовать так:
....

чтото я вас не понял)) сами написали код)) спасибо! завтра проверю)))
ща просто прочитал — ну походу должно работать)))
но вот почему вы сами себе противоречите — говоря, что
WM>Очень плохое описание. Мне кажется, что оно противоречит примерам.
да и примеры очень точны...

Здравствуйте, Аноним, Вы писали:

А>чтото я вас не понял)) сами написали код))
Всё очень просто: сам придумал задачу — сам её решил.
Пример кода написан для одной из интерпретаций, которая мне показалась имеющей шанс встретится в реальной задаче. Но это не означает, что это именно эта интерпретация соответствует исходной и решает вашу задачу.

Такой предикат задаёт следующее отношение порядка:

1. Точки с меньшей ординатой всегда идут перед точками с большей ординатой;
2. В случае равенства ординат точки слева от прямой x=x0 и лежащие на ней идут перед точками, расположенными справа от прямой;
3. В случае равенства ординат все точки все точки слева от прямой x=x0 и лежащие на ней упорядочены по убыванию абсцисс;
4. В случае равенства ординат все точки все точки справа от прямой x=x0 упорядочены по возрастанию абсцисс.

Если именно это нужно — замечательно.


А>но вот почему вы сами себе противоречите — говоря, что
WM>>Очень плохое описание. Мне кажется, что оно противоречит примерам.
А>да и примеры очень точны...

Это очень здорово, что вам понятны примеры. Но они непонятны мне.
Сначала сообщаете, что у вас есть вектор точек на плоскости, а потом в качестве примера приводите матрицу 4×3 И почему-то результат сортировки по прежнему матрица 4×3
А стоило бы привести список координат точек, да требуемое отношение порядка, например.

Здравствуйте, watch-maker, Вы писали:

WM>Здравствуйте, Аноним, Вы писали:


А>>но вот почему вы сами себе противоречите — говоря, что
WM>>>Очень плохое описание. Мне кажется, что оно противоречит примерам.
А>>да и примеры очень точны...

WM>Это очень здорово, что вам понятны примеры. Но они непонятны мне.
WM>Сначала сообщаете, что у вас есть вектор точек на плоскости, а потом в качестве примера приводите матрицу 4×3 И почему-то результат сортировки по прежнему матрица 4×3
WM>А стоило бы привести список координат точек, да требуемое отношение порядка, например.

ну так если все Point из вектора выписать на плоскости — в соответствии с хранящимися в них координатами, то
на плоскости получится вот такая матрица. и сортировка вектора (как раз как вы более широко описали)
просто должна означать, что при получении каждой последующей i++ точки из вектора, будут выполняться условия,
описанные вами.
и если теперь отсортированную матрицу выписать на плоскости — в соответствии с хранящимися в них координатами,
то на плоскости получится матрица номер 2.

Здравствуйте, Аноним, Вы писали:

А>задается некий Хо, относительно которого надо получить сортировку
А>по Иксам по убыванию(равенству) влево от Хо и тут же по возрастанию
А>вправо от Хо.

То есть, по возрастанию абсолютной дистанции |dX| = |X-Xo|

A> И все это на фоне убывания У в одном варианте прохода
А>алгоритма, и по возрастанию — в другом.

Тут нужно определиться: что приоритетнее — упорядочить по Y или по dX


А>вопрос — как сие сделать на С++???

Есть разные способы.

— Можно хранить точки в векторе и сортировать их то одним, то другим способом.
— Можно в ассоциативном контейнере (set либо boost::multi_index), но при этом Xo придётся задавать как неизменное свойство контейнера.
— Можно в иерархическом контейнере (вектор векторов) — каждый элемент первого уровня является набором точек с одинаковым значением Y, а между собой эти точки упорядочены по dX. Тогда перебор с разным направлением сортировки Y будет сводится просто к проходу по этому вектору в разных направлениях.
— Можно, наконец, придумать специальную структуру данных, которая для произвольного Xo быстро отдаёт упорядоченный по |dX| набор.

Всё зависит от того, какие требования предъявляются к набору. Будет ли он часто меняться, будут ли часто меняться критерии (особенно, Xo).


А>есть идеи? может я чтото упускаю из виду?

Из виду упускаешь use cases. Сам по себе сферический набор точек в вакууме никому не нужен, а вот в контексте использования могут проясниться важные нюансы.


Кстати про специальную структуру. Чисто в порядке этюда
1. Упорядочиваем точки по X.
2. Для данного Xo находим L = lower_bound(begin,end,Xo) — итератор, левее которого лежат точки, меньшие Xo, а правее — больше-или-равные.
3. Возьмём два диапазона — левый (reverse_iterator(L),rend) и правый (L,end); оба они, очевидно, упорядочены по возрастанию |dX|
4. Выполним ленивое слияние: каждый раз, пытаясь прочитать очередной элемент, будем смотреть на головы этих диапазонов и вынимать (сдвигая голову) тот элемент, для которого |dX| меньше.
Здесь важно то, что исходная сортировка совершается единожды и не зависит от Xo, и сам набор данных после этого остаётся неизменным. То есть, мы можем последовательно и даже одновременно запустить несколько забегов с разными Xo.
Более того, здесь мы можем использовать упорядоченные контейнеры (set), изменение которых дешевле, чем изменение вектора или списка.

Здравствуйте, Аноним, Вы писали:

А>есть вектор точек с координатами ХУ. std::vector<Points>, где...

вот это на стоит посмотреть — http://ru.wikipedia.org/wiki/R-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE — и вообще на тему Spatial Index's.