Сортировка данных и возвращение им прежнего порядка

[@flexoid]

Уж простите, но фото просто шикарное.

[@k06a]

Искал по разным источникам иллюстрацию сортировки,
нашёл на вики в статье Сортировочная станция ))

[@Agent_J]

Суровая сортировочная станция, внушает

[@Lungo]

А ведь есть и побольше — Bailey Yard

[@Kyborg2011]

Минусики на фото кода это такая ловушка? Я не один попробовал нажать на них?:)

[@k06a]

Я пришёл к выводу, что код проще всего оформить скриншотами.
Ссылка на исходный текст под каждым имеется.

[@Kyborg2011]

Я не против:) Оформлено красиво, просто так и хочется нажать:)

[@f0b0s]

Вас в каждой статье просят перестать так делать. Вы назло что ли? Нет, топики и правда неплохие и Вы здорово оживились за последние несколько дней, но код скриншотами это по меньшей мере странно.

[@k06a]

Я уже перестал)

[@k06a]

Сриншоты сделаны в редакторе Notepad++.

[@mark_ablov]

самый лучший способ — это работать с парами (std::pair <MyData * / MyData & / MyData, int>, где второе значение — начальный индекс).

[@k06a]

А как потом сортировать по второму значению в паре?

[@mark_ablov]

кастомный компаратор, ну или bind из буста можно заюзать.

[@mark_ablov]

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

    size_t len = len = m_sections.size();
    for (size_t i = 0; i < len; i++)
        realSectIdxRv.push_back(i);
    for (size_t i = 0; i < len; i++)
    {
        // находим минимум среди имён [i, len]
        size_t minj = i;
        for (size_t j = i + 1; j < len; j++)
        {
            if (strcmp(m_sections[j].name.c_str(), m_sections[minj].name.c_str()) < 0)
                minj = j;
        }
        // записываем на i-ую позицию эту строку, она i-ая по порядку
        swap(m_sections[i], m_sections[minj]);
        swap(realSectIdxRv[i], realSectIdxRv[minj]);
    }

[@k06a]

У вас же получается сложность О(n^2).
А std::sort() дает в среднем О(n*log(n)).

[@mark_ablov]

я знаю. поэтому и написал первую строчку :)

[@tzlom]

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

[@k06a]

Это уже третий способ.
Итого имеем:
1) Запоминание операций обмена при сортировке
2) Сортировка дважды по разному параметру
3) Сортировка не самих значений, а указателей на них

[@Mineev]

Только вот в Domino хранить index, который всего лишь нужен для сохранения порядка начальной сортировки — не очень хорошо. C точки зрения ООП — это нарушение абстракции.

[@k06a]

Когда речь заходит о спортивном программировании, чаще всего про ООП вообще не вспоминают. Тут речь больше об алгоритмах и их реализациях, чем об эстетизме…

[@cursed]

Вы так говорите, как будто ООП это хорошо.

[@k06a]

А вы так говорите, будто нет))
ООП + интерфейсы + паттерны + смартпоинтеры = СИЛА

[@cursed]

Когда пишешь лабу в институте — возможно.

[@Mineev]

Только вот в Domino хранить index, который всего лишь нужен для сохранения порядка начальной сортировки — не очень хорошо. C точки зрения ООП — это нарушение абстракции.

[@stroncium]

С какого момента нарушение абстракции? Это индекс, по которому мы находились в изначальном потоке данных, явно принадлежит элементу. Или номер дома дому не принадлежит?

[@DarkRIP]

Лучше всего это можно сделать через boost::multi_index, контейнер именно для этого и создан.

[@alexeygrigorev]

Ну буст мало на каких контестерах доступен. Почти на всех недоступен, поэтому на него лучше не надеяться

[@alexeygrigorev]

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

[@alexeygrigorev]

А вот ответ на вопрос, как сортировать по second
www.cplusplus.com/reference/algorithm/sort/ см example

[@red1ynx]

Когда прочитал про возвращение прежнего порядка, в первую очередь подумалось вернуть данные, сохраненные перед сортировкой (:

[@red1ynx]

Реально используете notepad++ для разработки, или только для подсветки синтаксиса в статье?

[@k06a]

Использовал для разработки только на асме))
А так — быстрый редактор кода, подсветка.
Быстрые макросы очень нравятся — ради них иногда открываю.

[@Antigluk]

Но зачем скриншотами?! Не могу понять)

[@eyeless_watcher]

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

[@k06a]

Бывает, что отсортированным и обработанным данным в итоге требуется исходный порядок.

[@eyeless_watcher]

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

[@Dreddik]

Пересортировать вновь по индексам будет примерно аналогичной операцией, как поиск элемента и установка его на нужное место.
Разве нет?
Причем памяти при этом потребуется в два раза меньше

[@eyeless_watcher]

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

[@Dreddik]

Хм, и правда ведь, массив указателей вполне хорошее решение :)

[@BowFingeR]

тут вот на днях на просторах инета нашел за О(n):
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait

:)

[@Anexroid]

Что это?

[@Anexroid]

Кажется понял)))