альтернатива сортировке вставками + копирование, когда небольшой массив должен быть отсортирован *и* скопирован

Рассмотрим два массива, A и B, оба имеют длину N, причем N довольно мало. Я хотел бы отсортировать элементы в A и сохранить отсортированные элементы в B.

Было бы довольно просто выполнить сортировку вставками на месте для A, а затем массово скопировать отсортированные значения в B. Однако при этом не используются две вещи:

  1. есть свободное пространство размера N, доступное для использования и
  2. отсортированные значения должны в конечном итоге оказаться в B, а не в A.

Может ли кто-нибудь предложить другой подход (возможно, модифицированную сортировку вставками?), Который воспользуется преимуществами одного (или обоих) из них и в конечном итоге превзойдет простое решение сортировки вставками + копирование?


sorting selection-sort insertion-sort
person jph    schedule 12.09.2013    source источник
comment
Сортировка вставками очень неэффективна. Есть ли причина, по которой вы используете его вместо быстрой сортировки / сортировки слиянием / какой-либо другой O (n log n) алгоритм сортировки? И если N достаточно мало, чтобы сделать использование сортировки вставками достойной идеей (скажем, 100 или меньше), никакая модификация не может иметь существенного значения, поскольку время выполнения уже незначительно.   -  person Bernhard Barker    schedule 12.09.2013
comment
Сортировка вставками на самом деле хорошо работает для небольших значений N. Вот почему большинство реализаций быстрой сортировки возвращаются к сортировке вставками, когда сортируемая область меньше некоторого порога. Посмотрите книгу «Разработка функции сортировки» (1993) Бентли и Макилроя. Вот как я планирую его использовать: как запасной вариант, встроенный в более сложную общую сортировку.   -  person jph    schedule 12.09.2013

Ответы (1)


arrow_upward
0
arrow_downward

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

  1. Разделите массив на четверти и отсортируйте с помощью сортировки вставками.
  2. Объедините первую и вторую четверти в пустое пространство, то же самое для 3-й и 4-й четвертей.
  3. Объедините первую половину и вторую половину с нуля в целевой массив

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

person The Great Java    schedule 09.12.2016