Самый эффективный алгоритм сортировки для большого набора чисел

Во-первых, вам понадобится карта word -> count. 50 000 слов — это немного — в памяти легко уместится, так что не о чем беспокоиться. В С++ вы можете использовать стандартный STL std::map.

Затем, когда у вас есть карта, вы можете скопировать все ключи карты в вектор.

Затем отсортируйте этот вектор с помощью пользовательского оператора сравнения: вместо сравнения слов сравните количество на карте. (Не беспокойтесь о конкретном алгоритме сортировки — ваш массив не такой большой, поэтому вам подойдет любая стандартная библиотечная сортировка.)

Я бы начал с быстрой сортировки и пошел дальше.

Посетите вики-страницу об алгоритмах сортировки, чтобы узнать о различиях.

Вы должны попробовать сортировку MSD radix. Он отсортирует ваши записи в лексикографическом порядке. Вот проект кода Google, который может вас заинтересовать.

Взгляните на ссылку. Наглядное представление о том, как работает другой алгоритм. Это даст вам подсказку!

Алгоритмы сортировки

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

Первый шаг. Создайте хеш-карту со словами в качестве ключевых значений и частотностью в качестве связанных значений. Вы будете заполнять эту хеш-карту при анализе файла. Пока вы это делаете, обязательно отслеживайте самую высокую встречаемую частоту. Этот шаг имеет сложность O(n).

Второй шаг. Создайте список с количеством записей, равным наибольшей частоте из первого шага. Индекс каждого слота в этом списке будет содержать список слов с частотным подсчетом, равным индексу. Таким образом, слова, встречающиеся в документе 3 раза, попадут, например, в список[3]. Переберите хеш-карту и вставьте слова в соответствующие места в списке. Этот шаг имеет сложность O(n).

Третий шаг. Пройдитесь по списку в обратном порядке и выведите все слова. Этот шаг имеет сложность O(n).

В целом этот алгоритм выполнит вашу задачу за O(n) время, а не O(nlogn), которое требуется для быстрой сортировки.

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

Каждый раз, когда в моем профиле появляется сортировка, я пробую основные сорта. У меня никогда не было ничего, что превзошло бы и Quicksort, и Combsort.

Я думаю, вы хотите сделать что-то, как описано в следующем посте:

http://karephul.blogspot.com/2008/12/groovy-closures.html

Языки, которые поддерживают закрытие, значительно упрощают решение, например, LINQ, как упомянул Эрик.

Для больших наборов вы можете использовать так называемую «индексацию на основе сортировки» при поиске информации, но для 50 000 слов вы можете использовать следующее:

• прочитать весь файл в буфер.
• проанализируйте буфер и создайте вектор токенов с помощью struct token { char *term, int termlen; } term — указатель на слово в буфере.
• отсортировать таблицу по терминам (лексикографическому порядку).
• установить entrynum = 0, перебрать вектор терминов, когда термин новый, сохранить его в векторе: struct { char *term; внутренняя частота; } в index entrynum установите частоту равной 1 и увеличьте номер записи, в противном случае увеличьте частоту.
• отсортировать вектор по частоте в порядке убывания.

Вы также можете попробовать реализовать цифровые деревья, также известные как Trie. Вот ссылка