Четверг, 19.07.2018, 18:14
Приветствую Вас Гость | RSS

Анти лотерейный математичесий сайт и всё БЕСПЛАТНО

Anti Lottery math site all FREE anti casino против казино

Карта мира Конкурс ставок IntelBet мой ВКонтакте КеноКено КЕНО ЮТЮБ KENO mini YOUTUBE Яндекс.Метрика Гость,

карта статистики посетителей & конкурсы бесплатных прогнозов конкурсы бесплатные & ВКонтакте & Математический Блог & КеноКено & КЕНО ЮТЮБ KENO mini YOUTUBE

НЕТ рекламы НЕТ партнёрских НЕТ рефералов NO advertising NO partners NO referrals pas de publicite pas de partenaires pas de references ешқандай жарнама ешқандай серіктестер жоқ реферал

IQ бесплатно КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE КЕНО ЮТЮБ KENO mini YOUTUBE

CITIZENS of USA and EU to me DONATE please: almost $ 0.8 WMZ = € 0.7 WME =
= pressed picture DONATE above or WMZ Z636495154357 WME E123268917690

BÜRGERS der USA und der EU zu mir SCHENKEN bitte: Der WMZ von fast 0.8 $ = der WME von 0.7 € =
= hat den picture SCHENKEN oben gedrückt oder WMZ Z636495154357 WME E123268917690

les CITOYENS des Etats-Unis et d'UE à moi DONNENT s'il vous plaît : WMZ de presque 0.8$ = WME de 0.7€ =
= a appuyé sur picture DONNENT au-dessus ou WME E123268917690 WMZ Z636495154357

время застолбить за собой новое слово интиграаль
интИГРАаль = интеграл + игра + грааль = ИНТиграАЛЬ

time to stake a new word
temps de jeu un nouveau mot
Zeit um dem Spiel ein neues Wort

intigraal
intIGRAal = integral + igra + graal = INTigraAL

Уважаемые посетители данного сайта из Кремниевой Долины!

Видя все посещения данного сайта через карту мира

стоимость каждого дня посещения данного сайта из Кремниевой Долины

составляет $1 Webmoney скопирован из кошелька Z636495154357

Dear visitors of this site from Silicon Valley!

Seeing all visits to this site through world map

cost of each day visiting this site from Silicon Valley

is $ 1 Webmoney copied from wallet Z636495154357

Главная | Регистрация | Вход

Главная » Файлы » Мои файлы

Русская Сортировка половинами и quicksort быстрая сортировка qbasic и МЫ
[ Скачать с сервера (4.26 Mb) ] 16.04.2014, 18:41

Русская Сортировка половинами и 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 части неравные раздельно

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

любителям сортировать ютюб

 

додумав деление на 4 участка

100ооо элементов наизнанку
сортировались 66 секунд

и программу размещу позже
пока не универсально: циклы подряд

наверняка возможно превратить в 3 цикла
тогда небось получится делить ещё на части

 

на 4 части неудачно делит нечётное количество
зато перешёл от имён в 2-мерный массив

известна формула количества проходов
= LOG(N) / LOG(2)
для создания вложенных циклов
и думаю останется деление пополам

n = 39
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

finish = TIMER

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

PRINT finish - start, s, p
END

общие строки при правильном расположении
внутри программы рассчитывают время
для сравнения сортировки многими алгоритмами
соблюдая универсальные имена переменных

n = 100000
RANDOMIZE TIMER

FOR i = 1 TO n
    a(i) = n - i + 1
    'a(i) = INT(RND * n)
NEXT: PRINT: PRINT

start = TIMER: p = 0: s = 0

s = s + 1 ' число циклов
p = p + 1 ' число перестановок

finish = TIMER

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

PRINT: PRINT: PRINT finish - start, s, p
END

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

вместо изначальных =8*7/2 = 28 перестановок
и вместо массово ошибочного числа перестановок
=8^2 = 64 перестановок
12 перестановок в 5 раз быстрее
6 перестановок в 10 раз быстрее

в процессе соревнования сортировок
выявил 3 алгоритма basic и мой занимал 3-е место
отставая на доли секунды

и ежели читаете данные строки легко додуматься:
удалось оптимизировать как и предполагалось
в начале темы разделив массив пополам и ещё пополам

и посмотрев файл результатов всё отсортировано

10ооо ячеек за о,72 с а оппонент почти секунду
22ооо ячеек за 3,3 с а оппонент почти 5 сек
100ооо ячеек за 66 с а оппонент за 90 сек

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

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

инструкция испытаний:
все программы содержат строки подключающие
одинаковый массив данных создаваемый управляемо
в виде 1/4-й разной мощности

в файле c:/N.txt указано количество и мощности
программа zapoln.exe формирует массив на c:/
сортировщики стартуя считывают одно и то же

и в процессе показывают одинаковые сообщения
и подсчитывают время чисто сортировки сообщая
на экране время и число проходов и перестановок
и сортировав пишут сортированное на c:/

и ежели тема будет развиваться
тогда размещу наработки и ещё новее будут

Нобелевская премия сама себя не получит

 

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

хоть 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

zaminus.bas считывает из N.txt количество ячеек и создаёт
управляемый KOHKYPC.txt с нецелыми и отрицательными числами

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 / (RND * 100)
    d(n / 4 + i) = -INT(RND * 100 * b) + b / (RND * 100)
    d(n / 2 + i) = INT(RND * 100 * c) + c / (RND * 100)
    d(3 * n / 4 + i) = INT(RND * 100 * d) + d / (RND * 100)
NEXT

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

FOR i = 1 TO n
    LOCATE 1, 1: PRINT i; "iz"; n, 100 * i / 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

сортировка считывающая данные из c:/KOHKYPC.txt
и пишущая в ==sortda2yshz.txt

школьная сортировка и циклы и переменные

' DA 2 SIDE MASSIV sort
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n

DIM d(2, n), q(3)

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

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

FOR i = 1 TO n: sum1 = sum1 + d(1, i): NEXT
sred1 = sum1 / n: PRINT sred1: PRINT

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

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

q(1) = 1: q(2) = y - 1: q(3) = n

FOR t = 1 TO 2
    FOR i = q(t) TO q(t + 1): FOR j = i + 1 TO q(t + 1)
            IF d(2, i) > d(2, j) THEN SWAP d(2, i), d(2, j): p = p + 1
        s = s + 1: NEXT: '    FOR k = 1 TO n: PRINT d(2, k);: NEXT: PRINT
    NEXT
NEXT

finish = TIMER

FOR i = 1 TO n: sum3 = sum3 + d(2, i): NEXT: sred3 = sum3 / n: PRINT

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

OPEN "c:/==sortda2yshz.txt" FOR OUTPUT AS #2
PRINT #2, finish - start; "секунд", "циклы"; s, "смены"; p
PRINT #2, n; "шт.", "школьная 2 части цикл и переменные"
FOR i = 1 TO n: PRINT #2, d(2, i): NEXT
END

Тестирование на одинаковых массивах

пузырьковая bubble = все со всеми: ошибочный массовый алгоритм из интернета
школьная = улучшенная пузырьковая: различные элементы без перестановки равных

русская сортировка: школьная или выбором включая деление на 2 части включает
цикл и переменные без индекса = улучшенная школьная и массив делится на 2 части
и также улучшается сортировка выбором и другие человеческие нормальные понятные
и возможно делить на 4 части и на 8 частей не усложняя понимание

русская сортировка 2 части смены =x*(N/x)*((N/x)-1)/2 N=8 x=2 =2*4*3/2 12 N=100 2450
школьная смены =N*(N-1)/2 N=8 =8*7/2 28 N=100 4950
пузырьковая bubble смены =N^2 N=8 =8^2 64 N=100 10000
русская сортировка 4 части смены =x*(N/x)*((N/x)-1)/2 N=8 x=4 =4*2*1/2 4 N=100 1200

100ооо шт.   

русская сортировка 4 части 70 секунд
русская сортировка 2 части 170 секунд
школьная 230 секунд
пузырьковая bubble 440 секунд
выбором сортировка select 140 секунд
русская сортировка выбором 2 части 105 секунд
русская сортировка выбором 4 части 67 секунд

1000 шт.  

русская сортировка 4 части циклы  135048 смены  39725
русская сортировка 2 части циклы   261342 смены   92805
школьная циклы   499500  смены   227585
пузырьковая bubble internet ошибочная циклы   998001 смены   227585
выбором сортировка select циклы      999 смены      6346
русская сортировка выбором 2 части циклы      999 смены     4406
русская сортировка выбором 4 части циклы      999 смены    3811

10000 шт. 

русская сортировка выбором 4 части циклы 10000 смены 48736
русская сортировка выбором 2 части циклы 10000 смены 67704
выбором сортировка select циклы 10000 смены 97888

текстовые строки

русская сортировка 2 части 1000 строк циклы 264280 смен 137131
школьная 1000 строк циклы 499500 смены 264139
русская сортировка 2 части 100ооо строк 390 секунд
школьная 100ооо строк 650 секунд

во всех тестах формировался массив
где русская сортировка работает наиболее медленно

в интернете управляемая визуализация сортировок
https://airtucha.github.io/SortVis/
лучше выбирать число столбцов 25 поменьше
и https://toptal.com/developers/sorting-algorithms/
и http://sorting.at
а также самостоятельно изучайте всевозможные сортировки в википедиях

shell сортировка

' 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

select сортировка выбором сравнивает текущий
с максимальным из оставшихся и переставляет местами

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


самым быстрым 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

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

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

 

Категория: Мои файлы | Добавил: DANILIN
Просмотров: 540 | Загрузок: 100 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:

Форма входа

Категории раздела

Поиск

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0
Бесплатный конструктор сайтов - uCozЯндекс.Метрика