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

Чем меньше амбиции тем счастливее живёшь

Помог бы сам тогда раз такой умный 😁

Евгений тоже умный, только амбиций меньше)

А я только сейчас увидел

Туше́

If I have a Z-order ordered list of view's, and each view's x,y is relative to its parent x,y, how would I correctly draw each view?

I'd create a separate table of absolute coordinates then iterate for each item in z-ordered list and
- if this item's absolute coordinates are known - draw it
- otherwise go to its parent and check if that parent's coordinates are known. Repeat recursively

another approach would be to go through the object tree first and calculate all the absolute coordinates then go through z-list and draw stuff

hmmm

could i do this during construction of my list?

    int analyze(View root, int depth) {
        if (root instanceof ViewGroup) {
            ViewGroup viewGroup = (ViewGroup) root;
            int r = set(viewGroup, depth);
            int childCount = viewGroup.getChildCount();
            if (childCount != 0) {
                children = new ArrayList<>();
                for (int i = 0; i < childCount; i++) {
                    ViewHierarchy viewHierarchy = new ViewHierarchy();
                    int r2 = viewHierarchy.analyze(viewGroup.getChildAt(i), depth + 1);
                    if (r2 > r) r = r2;
                    children.add(viewHierarchy);
                }
            }
            return r;
        } else return set(root, depth);
    }

or would it be easier to compute this when my list is constructed, at the expense of traversing it twice instead of once

eg something like

    private void computeOffsets(ViewHierarchy parent) {
        x = view.getX();
        y = view.getY();
        if (parent != null) {
            x += parent.x;
            y += parent.y;
        }
        for (ViewHierarchy hierarchy : this) {
            hierarchy.computeOffsets(this);
        }
    }

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

Так как в массиве с индексами index_array уже есть вся информация о расстановке элементов в массиве со значениями values_array, то сортировать ничего не надо, нужно просто перетасовать массив со значениями в соответствии с этими индексами - за O(n).

Если нет ограничения на использование памяти, можно выделить второй массив и перекидать в него значения из первого по указанным индексам, как вы и сделали, судя по дальнейшим комментариям. Но можно сделать и с памятью О(1) - in place.

Каждый элемент в index_array имеет следующую информацию - текущий индекс этого элемента в values_array и требуемый индекс - где этот элемент должен быть. Можно просто прыгать по index_array, переставляя элементы на нужные места.

Алгоритм следующий:
   1. Назначаем два индекса, текущий (где элемент стоит на данный момент) = 0 и требуемый = index_array[0]. Сохраняем значение values_array по текущему индексу в переменную.
   2. Если текущий индекс совпадает с требуемым, то этому элементу перестановка не нужна, ищем следующий, который не на месте. Если таких не осталось, конец исполнения.
   3. Ставим сохранённое текущее значение на требуемый индекс в values_array. Так как эта операция затрёт элемент, который уже там находится, нужно его предварительно сохранить, как и индекс, который хранится для него в index_array.
   4. Сохранённый индекс становится текущим индексом, сохранённое значение текущим значением, переходим на пункт 2.

Я решил эту задачу на Python, могу закинуть в чат, если нужно.

Ну если нужно создавать массив индексов размера н то это уже не О(1) а О(н), нет?

Он же уже есть. Изначатель у вас два массива - значения, индексы, правильно?