#c #arrays #sorting #memory #arduino
#c #массивы #сортировка #память #arduino
Вопрос:
У меня есть массив int без знака с n элементами (в n котором не более 20-25 элементов). Возможны дубликаты.
Я знаю, что наименьшие k значения имеют тип A , а другие (более крупные) n-k значения имеют тип B . Чтобы различать A и B , мне нужно найти индексы k наименьших значений (или n-k наибольших значений, в зависимости от того, что проще / быстрее). Исходный массив не должен быть изменен, поскольку индекс элемента содержит информацию.
В Интернете есть несколько решений этой проблемы (например, здесь). Однако большинство из них пытаются оптимизировать время обработки и пренебрегают использованием памяти.
Поскольку я реализую код на C на микроконтроллере (на базе Arduino), я должен сосредоточиться на низком использовании памяти и, при необходимости, занять немного больше времени обработки. Поэтому я чувствую себя небезопасно, используя указатели и рекурсию (возможно, я бы не стал, если бы знал об этом больше, но на самом деле это не так).
Можете ли вы порекомендовать, какой алгоритм лучше всего подходит для этой задачи (реализация приветствуется, но не обязательна)?
Комментарии:
1. Быстрый выбор был бы одним, ссылка объясняет это подробно.
2. Подход «сортировка выбор первых k элементов» недостаточно хорош для вас?
3. Что не так с минимальной / максимальной кучей в предоставленной вами ссылке: geeksforgeeks.org/k-largestor-smallest-elements-in-an-array ? Куча имеет тот же размер, что и конечный результат. Обрабатывайте выходной массив как кучу.
4. сортировка кучи @speendo ограничена значением O(log(HeapSize)). Таким образом, для 32 элементов или меньше максимальная глубина рекурсии равна 5
5. Почему бы вам не сделать копию массива и не использовать классическую пузырьковую сортировку? Это медленно, но вас, похоже, не волнует скорость. Это может быть реализовано без использования указателей или рекурсии. Объем памяти будет равен n (размер массива, поскольку вы будете создавать копию), если вам удастся использовать функцию подкачки на основе xor.