Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 05.05.2018, 12:45   #1
сфинкс
Форумчанин
 
Аватар для сфинкс
 
Регистрация: 17.06.2012
Сообщений: 953
По умолчанию [РЕШЕНО][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 части раздельно

Код:
n = 37
DIM d(2, n), sum(5), sred(5)
RANDOMIZE TIMER

FOR i = 1 TO n
    d(1, i) = n - i + 1
    PRINT d(1, i);
NEXT: PRINT

start = TIMER: p = 0: s = 0

FOR i = 1 TO n: sum(1) = sum(1) + d(1, i)
NEXT: sred(1) = sum(1) / n: PRINT sred(1):


y = 1: z = 0: FOR i = 1 TO n
    IF d(1, i) < sred(1) THEN d(2, y) = d(1, i): y = y + 1: ELSE d(2, n - z) = d(1, i): z = z + 1
NEXT

FOR i = 1 TO n: PRINT -d(2, i);: NEXT: PRINT
FOR i = 1 TO n: sum(2) = sum(2) + d(2, i): NEXT
sred(2) = sum(2) / n: PRINT sred(2): PRINT


FOR i = 1 TO n / 2: FOR j = i TO n / 2
        IF d(2, i) > d(2, j) THEN x = d(2, i): d(2, i) = d(2, j): d(2, j) = x: p = p + 1
s = s + 1: NEXT: NEXT
FOR i = n / 2 TO n: FOR j = i TO n
        IF d(2, i) > d(2, j) THEN x = d(2, i): d(2, i) = d(2, j): d(2, j) = x: p = p + 1
s = s + 1: NEXT: NEXT

FOR i = 1 TO n: sum(3) = sum(3) + d(2, i): NEXT: sred(3) = sum(3) / n: PRINT


finish = TIMER

FOR i = 1 TO n: PRINT d(2, i);: NEXT
PRINT: PRINT sred(3): PRINT

PRINT finish - start, s, p
END
Случайные и Массивы 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
Сообщений: 953
По умолчанию

вкратце: рассчитываем средний элемент
и за 1 цикл раскидываем в начало и в конец
в другой массив и сортируем 2 части раздельно
Изображения
Тип файла: png davsort.png (9.5 Кб, 130 просмотров)
Случайные и Массивы 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
Сообщений: 953
По умолчанию

оказывается худшими исходными данными
являются данные специально подготовленные
и подтверждается формула числа перестановок :
=2*4*3/2 = 12 перестановок и 6 перестановок

вместо изначальных =8*7/2 = 28 перестановок
и вместо массово ошибочного числа перестановок
=8^2 = 64 перестановок
12 перестановок в 5 раз быстрее
6 перестановок в 10 раз быстрее
Изображения
Тип файла: png davsort81.png (11.7 Кб, 129 просмотров)
Случайные и Массивы 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
Сообщений: 953
По умолчанию

додумав деление на 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
Сообщений: 953
По умолчанию

сам экспериментально нашёл и исправил особенность
типа если ввести большое значение в массив
тогда средний окажется искажён
и массив делится пополам неправильно

а оказалось решение встроено в виде счётчика
количества элементов меньше среднего и работает
причём без GОТО и значит классный код

1-вые непонятные циклы лишь заполнение массива
специально худшими значениями и заодно
100ооо элементов сортировал за менее 120 секунд
1ооо сортирует за 0,05с за 274ооо проходов и 4600 перестановок

Код:
n = 13
DIM d(2, n), sum(5), sred(5)

RANDOMIZE TIMER

FOR i = 1 TO INT(n / 2)
    d(1, i) = INT(RND * 20) + 5
    PRINT i; "="; d(1, i);
NEXT: PRINT

FOR i = INT(n / 2) + 1 TO n
    d(1, INT(i + 0.5)) = INT(RND * 10) + 1
    PRINT INT(i + 0.5); "="; d(1, i);
NEXT: PRINT: PRINT

FOR k = 1 TO n: PRINT d(1, k);: NEXT: PRINT

start = TIMER: p = 0: s = 0

FOR i = 1 TO n: sum(1) = sum(1) + d(1, i)
NEXT: sred(1) = sum(1) / n: PRINT sred(1): PRINT

y = 1: z = 0: FOR i = 1 TO n
    IF d(1, i) < sred(1) THEN d(2, y) = d(1, i): y = y + 1: ELSE d(2, n - z) = d(1, i): z = z + 1
NEXT: PRINT

FOR i = 1 TO n: sum(2) = sum(2) + d(2, i): NEXT
sred(2) = sum(2) / n: PRINT sred(2), y: PRINT

FOR i = 1 TO y - 1: FOR j = i TO y - 1
        IF d(2, i) > d(2, j) THEN x = d(2, i): d(2, i) = d(2, j): d(2, j) = x: p = p + 1
    s = s + 1: NEXT:
NEXT

FOR i = y TO n: FOR j = i TO n
        IF d(2, i) > d(2, j) THEN x = d(2, i): d(2, i) = d(2, j): d(2, j) = x: p = p + 1
    s = s + 1: NEXT:
NEXT

FOR i = 1 TO n: sum(3) = sum(3) + d(2, i): NEXT: sred(3) = sum(3) / n: PRINT


finish = TIMER

FOR i = 1 TO n: PRINT d(2, i);: NEXT
PRINT: PRINT sred(3)

PRINT finish - start, s, p
END
Случайные и Массивы 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
Сообщений: 953
По умолчанию

сценарий соревнования
алгоритмов сортировки

текст программы содержит циклы перестановок дабы
программа исключала подпрограммы на языке низшего уровня

формат программ для испытаний: 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
Сообщений: 953
По умолчанию

в данной теме и на всём форуме

видимо только я задумался и реализовал
подсчёт числа проходов и перестановок

и в эти часы создал универсальные строки
добавляемые в программы для сравнения

хоть bas хоть exe:
конкурс сортировок и универсальная оболочка и МЫ

число ячеек n и признаки четвертей массива abcd в файл
c:/N.txt

zapoln.bas / ехе создаёт c:/KOHKYPC.txt с целью создать
области заполненные данными большими и малыми
и реально создавать любой массив
одинаковый для любого сортировщика

zapoln.bas
Код:
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n, a, b, c, d

DIM d(n)

RANDOMIZE TIMER

FOR i = 1 TO INT(n / 4)
    d(i) = INT(RND * 100 * a) + a
    d(n / 4 + i) = INT(RND * 100 * b) + b
    d(n / 2 + i) = INT(RND * 100 * c) + c
    d(3 * n / 4 + i) = INT(RND * 100 * d) + d
NEXT

OPEN "c:/KOHKYPC.txt" FOR OUTPUT AS #1

FOR i = 1 TO n
PRINT #1, d(i): NEXT

END
встраиваем ключевые строки и тестируем и контролируем

Код:
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM d(n)

OPEN "c:/KOHKYPC.txt" FOR INPUT AS #1
FOR i = 1 TO n: INPUT #1, d(i): NEXT

FOR k = n - 10 TO n: PRINT d(k);: NEXT: PRINT
start = TIMER: p = 0: s = 0

FOR i = 1 TO n - 1: FOR j = i TO n
        IF d(i) > d(j) THEN SWAP d(i), d(j): p = p + 1
s = s + 1: NEXT: NEXT

finish = TIMER

FOR i = n - 10 TO n: PRINT d(i);: NEXT: PRINT
PRINT finish - start, s, p

OPEN "c:/REZ55.txt" FOR OUTPUT AS #2
FOR i = 1 TO n: PRINT #2, d(i): NEXT

END
самым быстрым Qbasic совместимым пока считаю
неизвестно где найденный алгоритм
сначала дополненный моими счётчиками
а ниже см. без счётчиков:

Код:
 OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM x(n) AS LONG
DIM y(-1 TO n) AS LONG
y(-1) = 1

OPEN "c:/KOHKYPC.txt" FOR INPUT AS #1
FOR i = 1 TO n: INPUT #1, x(i): NEXT

FOR k = n - 10 TO n: PRINT x(k);: NEXT: PRINT
start = TIMER: p = 0: s = 0

' algorithm

FOR i = 1 TO n
    y(x(i)) = y(x(i)) + 1: p = p + 1
NEXT i
 
FOR i = 1 TO n
    y(i) = y(i) + y(i - 1): p = p + 1
NEXT
 
FOR i = 0 TO n
    FOR j = y(i - 1) TO y(i)
        x(j) = i: p = p + 1
s = s + 1: NEXT j, i
 
' algorithm

finish = TIMER

FOR i = n - 10 TO n - 1: PRINT x(i);: NEXT: PRINT
PRINT finish - start, s, p

OPEN "c:/REZ11.txt" FOR OUTPUT AS #2
FOR i = 1 TO n: PRINT #2, x(i): NEXT

END
наиболее быстрая сортировка на сей час
на понятном человеческом языке

Код:
n = 1000
DIM x(n) AS LONG
DIM y(-1 TO n) AS LONG
y(-1) = 1

FOR i = 1 TO n: x(i) = INT(RND * 1000): NEXT

FOR i = 1 TO n
    y(x(i)) = y(x(i)) + 1
NEXT 

FOR i = 1 TO n
    y(i) = y(i) + y(i - 1)
NEXT

FOR i = 0 TO n
    FOR j = y(i - 1) TO y(i)
        x(j) = i
NEXT j, i

FOR i = 1 TO n: PRINT x(i);: NEXT

END
Случайные и Массивы 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
Сообщений: 953
По умолчанию

в процессе соревнования сортировок
выявил 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
Сообщений: 953
По умолчанию

новейшие новости в День Победы:

доделал разбиение на 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
Сообщений: 953
По умолчанию

наиболее быстрая сортировка на сей час
на понятном человеческом языке QBasic / QuickBASIC
найденная на форуме программистов

и небось сами не знают насколько быстрая
но сами сообщают мол не универсальная

Код:
n = 1000
DIM x(n) AS LONG
DIM y(-1 TO n) AS LONG
y(-1) = 1
 
FOR i = 1 TO n: x(i) = INT(RND * 1000): NEXT
 
FOR i = 1 TO n
    y(x(i)) = y(x(i)) + 1
NEXT 
 
FOR i = 1 TO n
    y(i) = y(i) + y(i - 1)
NEXT
 
FOR i = 0 TO n
    FOR j = y(i - 1) TO y(i)
        x(j) = i
NEXT j, i
 
FOR i = 1 TO n: PRINT x(i);: NEXT
END

Код:
' SHELL сортировка

n = 100000
DIM a(n)

FOR i = 1 TO n: a(i) = INT((RND * 1000) + 5): NEXT
FOR k = n - 10 TO n: PRINT a(k);: NEXT: PRINT
start = TIMER

' algorithm

d = n \ 2
WHILE d > 0
    DO
        done = 1
        FOR i = 1 TO n - d
            IF a(i) > a(i + d) THEN
                SWAP a(i), a(i + d)
                done = 0
            END IF
        NEXT
    LOOP UNTIL done
    d = d \ 2
WEND

' algorithm

finish = TIMER
FOR i = n - 10 TO n: PRINT a(i);: NEXT: PRINT
PRINT finish - start
END
Случайные и Массивы https://programmersforum.ru/showthread.php?t=344371 Учим C# & basic & excel & python https://programmersforum.ru/showthre...=327446&page=5 ничего нерекомендую
сфинкс вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Быстрая сортировка(сортировка Хоара). Сортировка фрагмента массива [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