⇢ 
Семён
Помогите с программой на языке С.
Кто знает алгоритм, как написать программу, которая будет сортировать элементы массива по частоте встречаемости? Мне не нужен код, объясните ход действий, пожалуйста.
ИЗ
Ирина Зверева
Надо создать дополнительный (возможно, ассоциативный) массив с частотами элементов и отсортировать его; если исходный массив не содержит ничего, кроме ключей, то можно к нему не возвращаться, а создать новый массив из дополнительного (как в сортировке подсчетом) .
А вообще ужас - нормальным людям уже приходится дописывать, что они нормальные.. . эх...
Кристина
Правильный, но сложный (если не использовать чужие наработки) путь - это словари. Валишь все значения в словарь, считая попутно, сколько раз что там встречается, затем сортируешь, используя словарь как критерий.
Другой путь - сортируем исходный массив, создаем массив записей вида (начальный индекс, количество элементов) , сортируем его тоже и нафиг перезаполняем исходный массив на его основе. Можно сразу построить массив с частотным критерием, без изначальной сортировки, но сдается мне, что так будет дольше - сложность будет O(n^2) вместо О (n log(n)).
Похожие вопросы