Сортировка битовым массивом

@Alexia Harell · Регистрация: 21.06.2020

Студворк — интернет-сервис помощи студентам

Сортировка битовым массивом
Пусть даны не более 24 чисел со значениями в диапазоне от 0 до 23, например,
{1, 20, 5, 9, 12, 8}. Данный набор чисел удобно представим 24-разрядной битовой последовательностью. В ней единичные биты отражают наличие в исходном наборе числа, равного номеру этого бита в последовательности.
В нашем примере получим следующую битовую последовательность:
010001001100100000001000. Последовательное считывание бит и их отображение в соответствующее число позволит естественным образом получить исходный набор чисел в отсортированном виде – {1, 5, 8, 9, 12, 20}.
На этой идее можно реализовать сортировку большого объема числовых данных в
файле. Достаточно один раз считать содержимое файла, заполнить при этом в памяти ЭВМ
битовый массив и на его основе быстро сформировать новое содержимое файла в уже отсортированном виде.
Как можно реализовать данную задачу на с++?

Алексей1153 · 15.12.2020, 15:43

Сообщение от Alexia Harell

Как можно реализовать данную задачу на с++

std::bitset - для чисел с определённым максимумом
или
std::vector - для произвольного количества чисел

Не по теме:

но способ идиотский, если честно )

берётся std::set/std::mutliset и всё

Новые блоги и статьи Все статьи Все блоги /
Популярные LM модели ориентированы на увеличение затрат ресурсов пользователями сгенерированного кода (грязь -заслуги чистоплюев). Hrethgir 12.06.2025 Вообще обратил внимание, что они генерируют код (впрочем так-же ориентированы разработчики чипов даже), чтобы пользователь их использующий уходил в тот или иной убыток. Это достаточно опытные модели,. . .	Топ10 библиотек C для квантовых вычислений bytestream 12.06.2025 Квантовые вычисления - это та область, где теория встречается с практикой на границе наших знаний о физике. Пока большая часть шума вокруг квантовых компьютеров крутится вокруг языков высокого уровня. . .	Dispose и Finalize в C# stackOverflow 12.06.2025 Работая с C# больше десяти лет, я снова и снова наблюдаю одну и ту же историю: разработчики наивно полагаются на сборщик мусора, как на волшебную палочку, которая решит все проблемы с памятью. Да,. . .	Повышаем производительность игры на Unity 6 с GPU Resident Drawer GameUnited 11.06.2025 Недавно копался в новых фичах Unity 6 и наткнулся на GPU Resident Drawer - штуку, которая заставила меня присвистнуть от удивления. По сути, это внутренний механизм рендеринга, который автоматически. . .	Множества в Python py-thonny 11.06.2025 В Python существует множество структур данных, но иногда я сталкиваюсь с задачами, где ни списки, ни словари не дают оптимального решения. Часто это происходит, когда мне нужно быстро проверять. . .
Работа с ccache/sccache в рамках C++ Loafer 11.06.2025 Утилиты ccache и sccache занимаются тем, что кешируют промежуточные результаты компиляции, таким образом ускоряя последующие компиляции проекта. Это означает, что если проект будет компилироваться. . .	Настройка MTProxy Loafer 11.06.2025 Дополнительная информация к инструкции по настройке MTProxy: Перед сборкой проекта необходимо добавить флаг -fcommon в конец переменной CFLAGS в Makefile. Через crontab -e добавить задачу: 0 3. . .	Изучаем Docker: что это, как использовать и как это работает Mr. Docker 10.06.2025 Суть Docker проста - это платформа для разработки, доставки и запуска приложений в контейнерах. Контейнер, если говорить образно, это запечатанная коробка, в которой находится ваше приложение вместе. . .	Тип Record в C# stackOverflow 10.06.2025 Многие годы я разрабатывал приложения на C#, используя классы для всего подряд - и мне это казалось естественным. Но со временем, особенно в крупных проектах, я стал замечать, что простые классы. . .	Разработка плагина для Minecraft Javaican 09.06.2025 За годы существования Minecraft сформировалась сложная экосистема серверов. Оригинальный (ванильный) сервер не поддерживает плагины, поэтому сообщество разработало множество альтернатив. CraftBukkit. . .

@Alexia Harell 0 / 0 / 0 Регистрация: 21.06.2020 Сообщений: 50

	Сортировка битовым массивом 15.12.2020, 14:57. Показов 3661. Ответов 1 Метки нет (Все метки) Сортировка битовым массивом Пусть даны не более 24 чисел со значениями в диапазоне от 0 до 23, например, {1, 20, 5, 9, 12, 8}. Данный набор чисел удобно представим 24-разрядной битовой последовательностью. В ней единичные биты отражают наличие в исходном наборе числа, равного номеру этого бита в последовательности. В нашем примере получим следующую битовую последовательность: 010001001100100000001000. Последовательное считывание бит и их отображение в соответствующее число позволит естественным образом получить исходный набор чисел в отсортированном виде – {1, 5, 8, 9, 12, 20}. На этой идее можно реализовать сортировку большого объема числовых данных в файле. Достаточно один раз считать содержимое файла, заполнить при этом в памяти ЭВМ битовый массив и на его основе быстро сформировать новое содержимое файла в уже отсортированном виде. Как можно реализовать данную задачу на с++? 0

Опции темы