Как вернуть первые N максимальных элементов из массива без сортировки массива?

dollar, Если порядо максимумов неважен, как в этой задаче - то K log K исчезает.

Как вернуть первые N максимальных элементов из массива без сортировки массива?

dollar, QuickSelect'ом надо взять только N-ый элемент один раз. Тогда первые N элементов будут в начале массива (ведь именно так quickselect и гарантирует, что N-ый элемент будет где надо).

Еще раз, quickselect (хоть и с большой константой) работет за линию в худшем случае без каких-либо допущений.

Наличие random'а позволяет на практике получить быстрый линейный алгоритм.

Или есть также алгоритмы быстрее O(n log n), хоть и не линейные, но работающие быстро и не в среднем.

Как вернуть первые N максимальных элементов из массива без сортировки массива?

dollar, Ваши поблажки (предположения о распределении чисел) весьма серъезные. Плюс даже с ними ваш алгоритм работает линейно лишь в среднем. Ведь может так оказаться, что все числа в массиве больше 970.
А приведенный мной, работающий за линию в среднем, алгоритм без поблажек - имеет константу примерно 2.

И его модификация с алгоритмом Блюма-Флойда-Пратта-Ривеста-Тарьяна будет работать за O(N) всегда, вне зависимости от размера K. Да, там мделенная константа, но это не важно. Этот алгоритм уже опровергает ваше "строго - никак".

Как вернуть первые N максимальных элементов из массива без сортировки массива?

dollar, Нет, не читерство. Оно проходит по массиву в среднем 2 раза, каким бы большим K не было.

Сначала вы делаете partition всего массива за один проход. Потом разбиваете левую половину, потом четверть и т.д. В итоге N+N/2+N/4 <= 2N.

Если K считать за константу, то практически любой метод будет работать за O(N), да. Но константа будет очень разная.

Как вернуть первые N максимальных элементов из массива без сортировки массива?

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

Вот пусть N=1, Тогда куча выродится в тупо один элемент. Один максимум. Тоже самое, что у вас. Не медленнее.

Может, при N=2? Да нет. Все те же N..2N сравнений, и до 2 перемещений на элемент. как у вас.

А вот уже при больших N в куче будет меньше и сравнений и присваиваний.

Как вернуть первые N максимальных элементов из массива без сортировки массива?

2.Ну да, самый тупой и медленный вариант. Но, возможно, самый простой. А при малых N и небольшом размере массива, возможно, эти недостатки не будут иметь значения.

По-моему, вызов одного sort() будет проще.

Как вернуть первые N максимальных элементов из массива без сортировки массива?

Этот ваш алгоритм по скорости равен "N раз найти минимум в массиве". Работает за O(M N), где M - длина массива.

Но вы почти додумались до хорошего алгоритма. Надо в acc использовать не массив, а кучу или приоритетную очередь на максимум. Тогда поиск вытесняемого элемента будет за O(log n).

Как вернуть первые N максимальных элементов из массива без сортировки массива?

Есть, есть строгие алгоритмы. Работающие за линейную сложность, гарантрованно возвращающие первые N элементов. Правда на практике используются скорее алгоритмы, которые или работют за O(M log N) или за O(M) в среднем (где M - размер массива).

Как вернуть первые N максимальных элементов из массива без сортировки массива?

Не надо quickSelect вызвать N раз. После вызова с параметром N первые N элементов уже будут минимальными. N-ый будет на своем месте, а вот все пердыдущие могут быть и перемешаны. Ведь quickselect гарантирует правильность N-ого элемента именно тем, что все левее его - меньше его, а все правее - больше.

А выбор минимума N раз - это самое плохое, что можно сделать.
Если массив маленький, то тупо сортировка будет быстрее чем N раз искать минимум. Если N маленькое, то алгоритм с кучей из моего ответа будет гораздо быстрее.

Как проверить n-количество или они образуют последовательность Фибоначчи?

Приведите пример входных данных и нужного ответа поограммы. Лучше несколько примеров - и положительные и отрицательные. Вопрос вообще непонятен.

Из за чего кириллица в исходном коде, после компиляции выводится латиницей (транслитерацией)?

Spooky 2020, Вы изменили исходник и увидели изменения тоже транслитерированными?

Из за чего кириллица в исходном коде, после компиляции выводится латиницей (транслитерацией)?

Армянское Радио, задание кодировки исходников совсем не тоже самое, что подменять строки полностью по какому-то никак нестандартизованному алгоритму, нигде не описанному.

Из за чего кириллица в исходном коде, после компиляции выводится латиницей (транслитерацией)?

Армянское Радио, Да ну, не верю, что компилятор будет строки константы переписывать. А вдруг они будут по сети посылаться? Или интерпретироваться как числа? Это же тупо набор байт. Я еще готов поверить, что wcout насилует строки при выводе, но это вряд ли. Скорее редактор при сохранении корябит исходник. Но еще более вероятно, что ничего этого не происходит и автор просто запускает что-то не то. Транслит - убогая практика, появившаяся от не поддержки кирилицы в разных сценариях. То, что этот ужас где-то действительно реализован как валидная стратегия локализации - это очень вряд ли.

Из за чего кириллица в исходном коде, после компиляции выводится латиницей (транслитерацией)?

Spooky 2020, поменяйте русскую строку первую. Добавьте, например, "аба" в конец, перекомпилируйте, запустите. Проверьте, действительно ли порограмма выводит это самое "аба" как "aba"? Я думаю, что вывод не изменится, потому что вы что-то не то компилируете или запускаете.

Из за чего кириллица в исходном коде, после компиляции выводится латиницей (транслитерацией)?

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

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

Сработает ли деструктор, присвоив atomic?

Mercury13, Добавлю, что вы пытаетесь детектировать UB через другое UB. То, что оно иногда сработает лишь даст вам ложную илюзию отстуствия UB в вашем коде. Если всякие аналоги valgrind не вариант, то подумайте над тем, как передавать через qt не голые указатели. Хоть guid, хоть индекс в массиве объектов будет тогда уж лучше, если наличие вот этого не-вашего кода так все усложняет, что надо городить всякие хаки для проверки на висячие указатели.

Какие разработчики работают с алгоритмами?

Alexandroppolus, вот. как я и говорил. Посмотрите комментарий RabraBabr - "алгоритмы не нужны"

Сработает ли деструктор, присвоив atomic?

Mercury13,

Упала сразу же — это круто! Хуже, когда не упала и потихоньку портит память.

Гарантий никаких нет. Поскольку ваша проверка сама содержит в себе UB, может быть что угодно.

Сработает ли деструктор, присвоив atomic?

Mercury13, Короче. Я понял. Это у вас оппортунистская проверка - задетектить UB после того, как оно произойдет. Оппортунистское, потому что все-равно может на какой-нибудь системе упасть во время проверки данных не в своей памяти, плюс то что там кто-то левый положет потом может случайно стать равно SCRAMBLE.

И ответ на ваш вопрос - нет, компиялтор может и удалить. Есть всякие платформо-зависимые функции для гарантированного зануления памяти, но как их прикрутить к атомикам - я не знаю. Но вообще компилятор может додуматся, что во время жизни объекта value не меняется и вообще удалить проверку нафиг.

Я бы не городил этот огород, а использовал тот же valgrind для проверки. Ну или, если хотите, то вам придется написать собственный менеджер памяти. Переопределить new и delete и или не удалять память вообще и там внутри где-то как-то помечать (например, выделить на 4 байт больше перед данными). Или где-то запоминать, что память отчищена и проверять на висячие указатели какой-то функцией, отдельной от возможно удаленного объекта.

Сработает ли деструктор, присвоив atomic?

Mercury13,

У живого объекта проверочная цифра правильная, а у умершего

Умершего объекта обычно больше нет. Его память возвращена системе, или переиспользована для других данных компилятором. Любое обращение к памяти объекта после вызова деструктора (если вы его руками, конечно, не вызываете) - это уже обращение по висящему указателю, что есть UB.

Если же вы сами руками вызываете деструктор у объекта (при этом у вас должен быть собственный какой-то менеджер памяти), то в этом случае, раз вы все еще хотите обращатся к какому-то полю объекта, вам стоит его не уничтожать, а переводить в "невалидное" состояние. Память все-равно не освобождена - ведь иначе UB будет. Для этого будет достаточно тупо bool is_alive и не надо какую-то защиту с канарейками городить. Ну или использовать первые несколько байт для пометки о валидности объекта, а остальные реинтерпритировать как ваш объект, тогда проверка будет как бы отдельно от логики самого объекта.

QModelIndex слишком мал, чтобы держать умный указатель

Не совсем понимаю контекст.

Объект может быть потёрт не только деструктором, но и совершенно посторонним кодом.

Это каким таким кодом? Если только у вас не собственный менеджер памяти, то объект трется при вызове delete на указателе, или после выхода переменной из scope. А деструктор обычно не трет объект, а лишь вызывается автоматически перед его "удалением" (не считая вызова free какого-нибуть).