Есть ли способ оптимизировать сортировку данных такого типа?

Ответ 1

Что делать, если вы сначала пропустите массив, чтобы группировать числа, чтобы избавиться от дубликатов. Каждый номер может перейти в хэш-таблицу, где число является ключом, а количество раз, которое оно появляется, - это значение. Поэтому, если число 750 000 появляется в массиве 57 раз, хэш-таблица будет удерживать ключ = 750000; value = 57. Затем вы можете сортировать гораздо меньшую хэш-таблицу с помощью клавиш, длина которых должна быть меньше 100.

С этим вам нужно всего лишь пройти один проход через массив, а другой пройти через гораздо меньший список хэш-ключей. Это должно избегать большей части свопов и сравнений.

Ответ 2

Вы можете проверить эту анимацию, которую я увидел из этого сообщения

Я думаю, что ваша проблема попадает в категорию "несколько уникальных", где ускоренная сортировка в трех направлениях и shell sort очень быстрая.

обновление:

Я реализовал некоторые алгоритмы сортировки на основе псевдокодов на sorting-algorithms.com и запускал их на образцах данных, данных OP. Просто для удовольствия:

вставка 0.154s

shell 0.031s

быстрая сортировка 0.018s

radix 0.017s

3-way quick sort 0.013s

Ответ 3

Похоже на Radix Sort или Сортировка ведра было бы возможным, поскольку они могут быть эффективными для целых чисел.

Эффективность сортировки Radix - это O (k · n) для n ключей, которые имеют k или меньше цифр. Иногда k представляется в виде константы, которая бы улучшала сортировку radix (при достаточно большом n), чем лучшие алгоритмы сортировки на основе сравнения, которые все O (n · log (n)). В то время как сортировка ковша - O (N * k) для n ключей и k ковшей.

Это может привести к постоянному (K) коэффициенту для сортировки radix. Из моего Java-экспериментов. Кроме того, стоит отметить, что radix не очень хорошо разбирается в отсортированных элементах.

100k целых чисел:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.075   0.025   0.025
Quicksort           0.027   0.014   0.015
Heap sort           0.056   0.03    0.03
Counting sort       0.022   0.002   0.004
Radix sort          0.047   0.018   0.016

500k целых чисел:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.286   0.099   0.084
Quicksort           0.151   0.051   0.057
Heap sort           0.277   0.134   0.098
Counting sort       0.046   0.012   0.01
Radix sort          0.152   0.088   0.079

1M целых чисел:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          0.623   0.18    0.165
Quicksort           0.272   0.085   0.084
Heap sort           0.662   0.286   0.207
Counting sort       0.066   0.022   0.016
Radix sort          0.241   0.2     0.164

10M целых чисел:

Algorithm           Random  Sorted  Reverse Sorted
Merge sort          7.086   2.133   1.946
Quicksort           4.148   0.88    0.895
Heap sort           11.396  3.283   2.503
Counting sort       0.638   0.181   0.129
Radix sort          2.856   2.909   3.901

Кажется, что элементы 500k - это когда константа начинает одобрять сортировку radix по quicksort.

Ответ 4

Существует алгоритм, который использует отсортированные подпоследовательности. Это вариант Merge Sort, называемый Natural Merge Sort. Я не могу найти хороший пример реализации на C, но с самого начала это не слишком сложно реализовать. В основном это выглядит примерно так:

• Вам нужна структура, содержащая два ints, индекс и длину подпоследовательности. Создайте новый массив (или, возможно, связанный список) этих структур.
• Итерации по всему массиву раз и каждый раз, когда значение меньше предыдущего значения, это начало новой подпоследовательности, поэтому создайте новую структуру и назначьте позицию подпоследовательности и назначьте длину предыдущая подпоследовательность к предыдущей структуре.
• Итерации через свои структуры и выполнение операции слияния на них в парах.
• Повторите шаг 3, пока все не будут объединены.

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

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

Ответ 5

Создайте хэш-таблицу и выделите массив. Для каждого элемента входного массива проверьте, находится ли этот элемент в хеш-таблице. Если да, то увеличивайте его значение. Если нет, вставьте его в хеш-таблицу со значением 1 и добавьте ее в свой массив.

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

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

Ответ 6

Я бы попробовал hand-coded qsort со специальным трюком, который на каждом node хранит номер и количество раз, которое оно встречается. Когда вы увидите это снова, вы увеличиваете счет.

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

Ответ 7

Учитывая отсортированные прогоны, разумной возможностью было бы использовать совместное слияние, чтобы объединить эти прогоны в большие сортированные прогоны, пока весь массив сортируется. Обратите внимание: если для функции просто нужен интерфейс C (вместо того, чтобы записываться в самом C), вы можете использовать std::inplace_merge из стандартной библиотеки С++, но напишите свою функцию с помощью спецификации привязки extern "C", поэтому вы можете использовать это от C.