|
Заблокирован
|
||||||
Quicksort qbasic быстрая сортировка половиной и МЫ04.05.2018, 22:23. Показов 9959. Ответов 86
Метки нет (Все метки)
quicksort qbasic быстрая сортировка половиной и МЫ
на тему сортировка читая дюжину статей с программами иногда часто вижу ляп: для А элементов 2 вложенных массива равные и число перестановок якобы А^2 зато правильнее: I от1 доА и J отI доА и видимо те ошиблись пиша 1 вместо I причём часто противореча пояснениям для А=100 требуется А^2=10ооо ходов а правильнее =100*(99)/2 =4950 ходов 2-жды меньше видно из формулы и ещё вникнув в сортировку пополам получается для А=100 =2*((100/2)*((100/2)-1)/2) = 2450 ходов 4-жды меньше чем советуют по интернету и возможно реально делить на 4 части и далее сортируется пузырьковая сортировка Проведя эксперимент контролируя время сортируя массив обратный от 100ооо до 1 всё про qb64 компилятор qbasic: мой пополам 135 секунд и А^2 215 секунд мой простой 389 секунд и А^2 497 секунд чужие непонятные около 200 секунд и вообще предполагаю используя мои строки контролирующие время реально тестировать многие алгоритмы сортировки на время лучше всего массив от 100ооо до 1 и ещё есть методы обмена без доп переменной В свете вышесказанного: на тему сортировка и МЫ обнаруживаются остроумные решения ускоряющие тысячи операций в разы Вдобавок создал строки контролирующие время пока отсутствующие в программе в начале темы и возможно проверять на скорость варианты сортировки Программу размещаю через тэг code
0
|
||||||
| 04.05.2018, 22:23 | |
|
Ответы с готовыми решениями:
86
Меньшее из двух чисел заменить половиной их суммы Меньшее из двух чисел заменить половиной их суммы, а большее — их удвоенным произведением |
|
|
|||
| 31.05.2021, 14:35 | |||
|
0
|
|||
| 31.05.2021, 15:57 | |||
|
0
|
|||
|
|
|||||||
| 01.06.2021, 15:08 | |||||||
|
В то же время самопальная qsort сравнима по времени с шелл сортировкой. На больших массивах надо подбирать оптимальные последовательности, а для этого требуется месяцы работы. пока не могу выделить достаточного времени. Проверял на Си, так как компилятора FB у меня пока нет, так как с переездами на новые оси, растерял много файлов. Надо еще искать все это хозяйство. А на си проверял так: Кликните здесь для просмотра всего текста
0
|
|||||||
| 01.06.2021, 18:24 | ||
Сообщение было отмечено Quiet Snow как решение
РешениеРеализовал 3 варианта сортировки Шелла (с разным набором длины промежутков, в т.ч. и последовательностью предложенной Седжвиком) В сравнении с модифицированной QSort Шелл все равно проигрывает, хотя последовательность Седжвика ускоряет сортировку У меня на FB сортировка Шелла более чем в 2 раза медленнее QSort на 20 млн. случайных данных. При этом при переносе кода на VBA на 1 млн данных Шелл всего на 30% медленнее QSort Так что многое зависит от ЯП, в котором реализована сортировка, а также от качества компилятора.
2
|
||
|
|
|
| 01.06.2021, 18:58 | |
|
Позже проверю на больших массивах. Раньше пытался проверять, но стандартная qsort ломалась уже на 100000 массиве видимо из-за переполнения программного стека..
0
|
|
|
|
|
| 02.06.2021, 16:40 | |
|
Проверил на массиве из 20 миллионов элементов. Стандартная qsort - 1 сек., шелл - 4 сек., самопальная qsort вообще зациклилась видимо из-за исчерпания стека. Отсортированный массив qsort - 1 сек, шелл - 2. Но опять же стандартная оптимизирована в отличие от шелла. Но у меня нет времени заниматься этим вопросом, как и поиском оптимальных последовательностей. В общем признаю, что на больших массивах qsort рулит.
0
|
|
| 02.06.2021, 16:40 | |
|
Управление COM-1 портом в QBasic
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы.
Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
|