|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
05.05.2018, 12:45 | #1 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
[РЕШЕНО][VB] quicksort qbasic быстрая сортировка половиной
данная тема не содержит вопросов
и тема размещена здесь т.к. нет спец ветки qbasic и надеюсь студентам и мне пригодится понимание про 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 и ещё есть методы обмена без доп переменной В свете вышесказанного: на тему сортировка и МЫ обнаруживаются остроумные решения ускоряющие тысячи операций в разы Вдобавок создал строки контролирующие время пока отсутствующие в программе в начале темы и возможно проверять на скорость варианты сортировки вкратце: рассчитываем средний элемент и за 1 цикл раскидываем в начало и в конец в другой массив и сортируем 2 части раздельно Код:
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
05.05.2018, 12:47 | #2 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
вкратце: рассчитываем средний элемент
и за 1 цикл раскидываем в начало и в конец в другой массив и сортируем 2 части раздельно
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
05.05.2018, 12:49 | #3 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
оказывается худшими исходными данными
являются данные специально подготовленные и подтверждается формула числа перестановок : =2*4*3/2 = 12 перестановок и 6 перестановок вместо изначальных =8*7/2 = 28 перестановок и вместо массово ошибочного числа перестановок =8^2 = 64 перестановок 12 перестановок в 5 раз быстрее 6 перестановок в 10 раз быстрее
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
05.05.2018, 12:59 | #4 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
додумав деление на 4 участка
100ооо элементов наизнанку сортировались 66 секунд и программа не универсальная: циклы подряд наверняка возможно превратить в 3 цикла тогда небось получится делить ещё на части разделение на 4 части менее предсказуемо на 4 части неудачно делит нечётное количество и тест показал нормально классно делит на 2 части известна формула количества проходов = LOG(N) / LOG(2) для создания вложенных циклов но думаю останется деление пополам а додумывать рекурсию незачем: выигрыш времени менее заметный при повышении разделения на части логарифм Кремниевая долина logarithm Silicon valley https://www.youtube.com/watch?v=bYm9AXPzRZQ Visualization of 24 Sorting Algorithms In 2 Minutes https://www.youtube.com/watch?v=BeoCbJPuvSE
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
Последний раз редактировалось сфинкс; 05.05.2018 в 13:04. |
07.05.2018, 10:42 | #5 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
сам экспериментально нашёл и исправил особенность
типа если ввести большое значение в массив тогда средний окажется искажён и массив делится пополам неправильно а оказалось решение встроено в виде счётчика количества элементов меньше среднего и работает причём без GОТО и значит классный код 1-вые непонятные циклы лишь заполнение массива специально худшими значениями и заодно 100ооо элементов сортировал за менее 120 секунд 1ооо сортирует за 0,05с за 274ооо проходов и 4600 перестановок Код:
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
Последний раз редактировалось сфинкс; 07.05.2018 в 11:26. |
08.05.2018, 12:27 | #6 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
сценарий соревнования
алгоритмов сортировки текст программы содержит циклы перестановок дабы программа исключала подпрограммы на языке низшего уровня формат программ для испытаний: exe дано: текстовый файл 100ооо целых чисел в столбик позволяет сформировать худшие не случайные массивы и всегда проверяется одинаковый массив на все программы сортировщик скачивает текстовый файл время: старт в процессе сортировки суммирует число проходов и перестановок время: финиш пишет время сортировки и число проходов и перестановок выводит сортированный массив в другой текстовый файл в результате будет ясна и скорость и число проходов и перестановок
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
08.05.2018, 23:22 | #7 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
в данной теме и на всём форуме
видимо только я задумался и реализовал подсчёт числа проходов и перестановок и в эти часы создал универсальные строки добавляемые в программы для сравнения хоть bas хоть exe: конкурс сортировок и универсальная оболочка и МЫ число ячеек n и признаки четвертей массива abcd в файл c:/N.txt zapoln.bas / ехе создаёт c:/KOHKYPC.txt с целью создать области заполненные данными большими и малыми и реально создавать любой массив одинаковый для любого сортировщика zapoln.bas Код:
Код:
неизвестно где найденный алгоритм сначала дополненный моими счётчиками а ниже см. без счётчиков: Код:
на понятном человеческом языке Код:
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
09.05.2018, 17:03 | #8 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
в процессе соревнования сортировок
выявил 3 алгоритма basic и мой занимал 3-е место отставая на доли секунды и ежели читаете данные строки легко додуматься: удалось оптимизировать как и предполагалось в начале темы разделив массив пополам и ещё пополам и посмотрев файл результатов всё отсортировано 10ооо ячеек за о,72 с а оппонент почти секунду 22ооо ячеек за 3,3 с а оппонент почти 5 сек 100ооо ячеек за 66 с а оппонент за 90 сек и то мой алгоритм ещё улучшится разделяя не пополам а именно в зависимости от среднего на каждом участке но пока доделывать некогда и пришлось наоборот индексы превратить в переменные для конкурса зато потом наоборот работающая сортировка разовьёт главную идею инструкция испытаний: все программы содержат строки подключающие одинаковый массив данных создаваемый управляемо в виде 1/4-й разной мощности в файле c:/N.txt указано количество и мощности программа zapoln.exe формирует массив на c:/ сортировщики стартуя считывают одно и то же и в процессе показывают одинаковые сообщения и подсчитывают время чисто сортировки сообщая на экране время и число проходов и перестановок и сортировав пишут сортированное на c:/ и ежели тема будет развиваться тогда размещу наработки и ещё новее будут
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
09.05.2018, 20:34 | #9 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
новейшие новости в День Победы:
доделал разбиение на 8 частей пока переменными но легко переделать во вложенные циклы и знаю о возможности делить массив не пополам и результаты мои же улучшены естественно в 2 раза: 10ооо ячеек за о,36 с а оппоненты почти секунду 22ооо ячеек за 1,6 с а оппоненты почти 5 сек 100ооо ячеек за 33 с а оппоненты за 90 сек разместил EEE=EXE в архиве с инструкцией N.txt 1 МБ https://yadi.sk/d/5wQUpG2b3VccE9
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
10.05.2018, 16:23 | #10 |
Форумчанин
Регистрация: 17.06.2012
Сообщений: 976
|
наиболее быстрая сортировка на сей час
на понятном человеческом языке QBasic / QuickBASIC найденная на форуме программистов и небось сами не знают насколько быстрая но сами сообщают мол не универсальная Код:
Код:
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Быстрая сортировка(сортировка Хоара). Сортировка фрагмента массива [C++] | druger | Помощь студентам | 0 | 20.04.2012 15:49 |
Быстрая сортировка(сортировка хаора) с++ | LustHunter | Помощь студентам | 3 | 07.10.2011 19:37 |
quickSort, Быстрая сортировка массива | kzht91 | Помощь студентам | 1 | 17.04.2010 00:30 |
быстрая сортировка настолько быстрая | Serg12 | Помощь студентам | 8 | 28.03.2010 21:31 |