СОРТИРОВКА Целочисленный массив TAG a STRUCTURE Array (или два)

Question

Таким образом, идея состоит в том, чтобы отсортировать большую СТРУКТУРУ, используя элемент этой структуры, для аргументов ради почтового индекса.

Для простоты давайте представим, что есть два массива, одно целое число, содержащее почтовые индексы, и два, массив большей структуры (3 КБ).

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

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

В идеале я бы просто отсортировал массив указателей, но в этом случае мне действительно нужно возвращать массив отсортированной структуры, а не массив отсортированных указателей. Если ничего другого, это упражнение по сортировке массива с тегами.

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

Я не нахожу много помощи в Интернете http://rosettacode.org/wiki/Sorting_an_Array_of_Integers#C

Предложения по элегантному дизайну приветствуются.

Answer 1

Если вы хотите избежать обмена накладными расходами, попробуйте Выбор сортировки . Этот алгоритм сортировки найдет значение и немедленно поместит его в нужное место, выполнив только один обмен, таким образом, Я полагаю , выполняя минимальное число обменов, насколько это возможно.

Answer 2

Вы можете поместить его в список std :: list и затем определить функцию сравнения для сортировки. Следует поменять местами только указатели на каждый узел, а не структуры. Смена указателей - это быстрая 2 или 3 операционная функция.

Answer 3

Выше вы должны использовать std :: vectors, а не массивы. Я не могу себе представить, почему вы не можете вернуть (постоянный) вектор указателей, но если это так, работайте с вектором указателей, сортируя только указатели, а затем, когда отсортировано, скопируйте результирующие отсортированные структуры в другой вектор и вернуть то, что будет означать только одну копию на векторную запись.