Quicksort qbasic быстрая сортировка половиной и МЫ

@sfinx78 · 04.05.2018, 22:23. **Показов** 9361. **Ответов** 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

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
n = 100
DIM d(n), a(n)
RANDOMIZE TIMER
 
FOR i = 1 TO n
    d(i) = n - i + 1
    PRINT d(i);
NEXT: PRINT: PRINT
 
sumd = 0: suma = 0: x = 0: y = 1: z = 0
 
FOR i = 1 TO n
    sumd = sumd + d(i)
NEXT: sredd = sumd / n
PRINT: PRINT sredd: PRINT
 
FOR i = 1 TO n
    IF d(i) < sredd THEN a(y) = d(i): y = y + 1: ELSE a(n - z) = d(i): z = z + 1
NEXT
 
FOR i = 1 TO n: suma = suma + a(i): NEXT: sreda = suma / n
 
FOR i = 1 TO n / 2: FOR j = i TO n / 2
        IF a(i) > a(j) THEN x = a(i): a(i) = a(j): a(j) = x
NEXT: NEXT
 
FOR i = n / 2 TO n: FOR j = i TO n
        IF a(i) > a(j) THEN x = a(i): a(i) = a(j): a(j) = x
NEXT: NEXT
 
FOR i = 1 TO n: PRINT a(i);: NEXT
PRINT: PRINT: PRINT sreda: PRINT
 
END

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

@Quiet Snow · 08.05.2018, 19:31

Сообщение от Pro_grammer

так же и FreeBasic порвал Пурик

Внимательно. У m-ch - 6 нулей, у locm'a - 7. Всё нормально никто никого не рвёт.

Добавлено через 12 минут

Сообщение от The trick

Pro_grammer, кидай EXE

Погоди, зачем тебе *.EXE, есть же код на бейсике. Возьми не RapidSort, а обычный QSort.
Rapid будет быстрее это 100%, тут интереснее будет узнать как "честный" Sort отрабатывает
без выделений тонн памяти.

Code
1
2
3
4
FreeBasic Qsort      3.993466846051064
FreeBasic ASM_QSort  4.386607387256305
FreeBasic RapidSort  1.251290920034649
PureBasic Sort       2.3

@The trick · 08.05.2018, 19:36

Сообщение от Quiet Snow

Погоди, зачем тебе *.EXE, есть же код на бейсике.

Я понял, не заметил что исходники есть.

Сообщение от Quiet Snow

тут интереснее будет узнать как "честный" Sort отрабатывает без выделений тонн памяти.

Что имеешь в виду? Там выделяется память в куче и дальше кодом что я привел выше сортируется.

@Quiet Snow · 08.05.2018, 19:44

Сообщение от The trick

Что имеешь в виду? Там выделяется память в куче и дальше кодом что я привел выше сортируется.

Не вдаваясь в алгоритм хочу просто понять, что там будет по времени аналог просто QSort
из сообщения m-ch. Ты же на VB алгоритм функции из проги locm'a переписал из дебагера?
Т.е. ты хочешь сравнить скорости или не?

@The trick · 08.05.2018, 19:51

Сообщение от Quiet Snow

Ты же на VB алгоритм функции из проги locm'a переписал из дебагера?

Да, декомпилировал.

Сообщение от Quiet Snow

Т.е. ты хочешь сравнить скорости или не?

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

Сообщение от locm

какой тип сортировки не знаю, т. к. библиотечная функция, но явно не пузырек, т. к. наблюдается примерно линейное увеличение затрачиваемого времени в зависимости от числа элементов массива

На VB6 у меня этот алгоритм срабатывает за 2.7 сек, в EXE locm'а за 2.2 секунды (там на асме функция написана). Обычный qSort работает на VB6 2.9 сек:

Visual Basic
1
2
3
4
5
6
7
8
9
Private Sub qSortLng(ar() As Long, ByVal low As Long, ByVal high As Long)
    Dim i As Long, J As Long, M As Long, wsp As Long
    i = low: J = high: M = ar((i + J) \ 2)
    Do Until i > J: Do While ar(i) < M: i = i + 1: Loop: Do While ar(J) > M: J = J - 1: Loop
        If (i <= J) Then wsp = ar(i): ar(i) = ar(J): ar(J) = wsp: i = i + 1: J = J - 1
    Loop
    If low < J Then qSortLng ar, low, J
    If i < high Then qSortLng ar, i, high
End Sub

@Quiet Snow · 08.05.2018, 20:02

Сообщение от The trick

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

А ну ok. Тоже полезная инфа. Да скорее всего взяли один из перспективных вариантов QSort'a,
слышал стандартный QSort в 1.5 раза ускоряли, а переписывание на асм даёт что-то около 5%.

@Pro_grammer · 08.05.2018, 20:19

Сообщение от Quiet Snow

У m-ch - 6 нулей, у locm'a - 7. Всё нормально никто никого не рвёт.

AAA! Ввели в заблуждение, Пурик 20 миллионов сортировал, а FB всего 2 лимона.
Ну тогда да, Пурик лучший! Я счастлив.

@Quiet Snow · 08.05.2018, 20:25

Сообщение от The trick

Обычный qSort работает на VB6 2.9 сек

Получается близко к идеальному PB-шный. Т.е. если брать 1.5 раза то это будет 1.9 сек.
Ну это мы конечно измеряем сферического коня в вакууме, но всё равно забавно.

Добавлено через 3 минуты

Сообщение от Pro_grammer

Ну тогда да, Пурик лучший! Я счастлив.

Ну FB не сильно отстал, просто совсем втупую юзать Rapid Sort я бы точно не стал)))

@The trick · 08.05.2018, 20:35

Сообщение от Quiet Snow

Получается близко к идеальному PB-шный.

Про какой именно? PB использует модернизированный алгоритм по крайней мере в том примере что кинул locm.
Если речь идет про быстродействие компиляторов то стоит сравнивать одинаковый код в обоих языках. В VB6 просто нет встроенной сортировки, а в PB мы получается сравниваем с ассемблерным кодом. С таким же успехом можно и в VB6 написать на ассемблере и скорости будут одинаковые.

@Quiet Snow · 08.05.2018, 20:43

Сообщение от The trick

Про какой именно? PB использует модернизированный алгоритм по крайней мере в том примере что кинул locm

Ну смотри буквально недавно же была тема, где VB всё нагибал, не помню насколько, но
вроде не сильно. Так вот если прикинуть что чистый QSort на PB быстрее не будет(почему
я просил именно QSort) то мы имеем следующую картину, делим время на 1.5 и получаем
"потипа идеальный случай" и приставляем к нему то время, за которое отрабатывает полностью
заряженный и оптимизированный алгоритм PB. Получается что-то близкое к идеальному
соотношению. Потому и было сказано, что это сферический конь в вакууме, выкладки очень
приблизительные. Если написать QSort на PB, будет точнее и понятнее, разумеется.

@Pro_grammer · 08.05.2018, 21:03

Сообщение от The trick

речь идет про быстродействие компиляторов

Скорее нет.
Как будто сравниваем, какой компилятор быстрее скомпилирует N-е кол-во строк

Вернее будет эффективность компиляторов. Так сказать наиболее близкий результат к идеальному машинному коду.
Типа Микрософт VB против GCC против FASM?

@sfinx78 · 09.05.2018, 20:32 **[ТС]**

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

видимо только я задумался и реализовал
и напоминаю на каждой странице про

подсчёт числа проходов и перестановок

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

хоть bas хоть exe

конкурс и универсальная оболочка и МЫ

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

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

zapoln.bas

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

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

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

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

подсказываю дальновидно: мои счётчики
перестановок p=p+1 и проходов s=s+1
нужны лишь 1 раз а в обычное время тормозят
посему важно исключить лишнее чтоб не тормозить

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

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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

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

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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

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

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

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

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

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

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

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

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

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

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

Добавлено через 3 часа 30 минут
новейшие новости в День Победы:

доделал разбиение на 8 частей пока переменными
но легко переделать во вложенные циклы
и знаю о возможности делить массив не пополам

и результаты мои же улучшены естественно в 2 раза:
10ооо ячеек за о,36 с а оппонент почти секунду
22ооо ячеек за 1,6 с а оппонент почти 5 сек
100ооо ячеек за 33 с а оппонент за 90 сек

разместил EEE=EXE в архиве с инструкцией N.txt
1 МБ https://yadi.sk/d/5wQUpG2b3VccE9
и каждый: может + должен = обязан
сравнить со своими алгоритмами сортировки

@locm · 09.05.2018, 20:57

Тест Тьюринга не пройден.

@CoderHuligan · 10.05.2018, 14:46

Вообще, - что вы зациклились на быстрой сортировке?! В реальных проектах её всё равно ОПАСНО использовать. Поэтому, лучше не надо. Есть достойный конкурент: сортировка Шелла. Никакой рекурсии, никакого срыва стека. Работает очень быстро, сам игрался с разными сортировками и проводил бенчмарки. Самые быстрые сортировки это Шелл и квиксорт. Причём шелл практически не уступает быстрой, а иногда и превосходит её.

@Pro_grammer · 10.05.2018, 17:19

Сообщение от CoderHuligan

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

Я как то писал программу визуализации сортировки, с музыкой. Шелла сильно уступала Быстрой при сортировке случайного массива, где значения могут повторятся. Если последовательный массив, то сортирует быстро.
Сама программа:

@Замабувараев · 14.05.2018, 11:00

Чат, самая лучшая сортировка — это корзинная сортировка. И вот почему.
1. Это сортировка без сравнений.
2. Сложность О(n).

@locm · 14.05.2018, 12:21

Сообщение от Замабувараев

Сложность О(n).

https://ru.wikipedia.org/wiki/Блочная_сортировка

относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

Недостатки: сильно деградирует при большом количестве мало отличных элементов, или же на неудачной функции получения номера корзины по содержимому элемента. В некоторых таких случаях для строк, возникающих в реализациях основанного на сортировке строк алгоритма сжатия BWT, оказывается, что быстрая сортировка строк в версии Седжвика значительно превосходит блочную сортировку скоростью.

@Замабувараев · 14.05.2018, 17:09

locm, а что корзинная сортировка — это сортировка без сравнений, не смутило?

@Quiet Snow · 14.05.2018, 18:32

Сообщение от Замабувараев

locm, а что корзинная сортировка — это сортировка без сравнений, не смутило?

locm-a должна смутить сортировка списками или картой?
Сейчас все сортировки в реальных задачах - гибридные, одной из самых быстрых остаётся модиф. QSort.
И никто не говорил, что его нельзя реализовать без рекурсии. Сравнения тоже нужны,
потому что в реальных задачах мы не всегда сортируем голый массив, часто требуется сортировать
значения, каждое из которых подвязано к структуре. При обмене мы можем поменять местами
указатели или память непосредственно(что не потребует доп. массива указателей).
А озвученный метод действительно хорош, применяю у себя, не читая википедий, доволен.

@m-ch · 31.05.2021, 08:27

Сообщение от CoderHuligan

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

Тоже сравнил различные сортировки между собой
(Быструю сортировку, быструю сортировкой с модификацией - сортировка вставками малых массивов, сортировку Шелла, сортировку расческой, сортировку слиянием)
Шелл оказался самый медленный, Сортировка расческой существенно ее превосходит, сортировка слиянием показывает похожие результаты с быстрой сортировкой на случайных данных.

В тестах сортировал целые числа в количестве: 1 млн, 2 млн, 5 млн, 10 млн, 20 млн

Самая быстрая получилось QSort с сортировкой вставками малых массивов, по скорости на FB уже сопоставима с сортировкой на PB, 20 млн сортируется менее 3х секунд

@CoderHuligan · 31.05.2021, 13:58

Сообщение от m-ch

Шелл оказался самый медленный,

Во-первых у вас используется самый примитивный шелл. Во-вторых для каждой сортировки генерируется свой рэндомный массив, хотя надо сравнивать на одном и том же массиве, то есть рэндомно заполнять для всех сортировок один массив. Попозже сделаю свои сравнения и здесь выложу.

Новые блоги и статьи Все статьи Все блоги /
Был там один разговор по поводу свободы в материальном мире. kumehtar 19.08.2026 Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .	Когда логика программы не спасает от человеческих ошибок Maks 18.08.2026 В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .	Лето уходит kumehtar 17.08.2026	Мысли в слух kumehtar 17.08.2026 Забавно, насколько сейчас стала доступна информация. Например о магии, духовном развитии, медитациях, и других подобных направлениях, ранее зачастую тайных, передаваемых от учителя к ученику. Хотя. . .
Перемещение строк из ТЧ в другой документ с учетом текущего пробега Maks 17.08.2026 Реализация из решения ниже выполнена на примере нетипового документа "Автозапчасти", с ТЧ "Шины". За основу взят алгоритм отсюда: https:/ / www. cyberforum. ru/ blogs/ 359708/ 10838. html Задача: . . .	Саморегулирующийся социальный контракт для сервера cross-section. Hrethgir 14.08.2026 С кодом конечно таких глубоких размышлений пока не было, впрочем я уже привык к алгоритмизации. Суть предмета записи: снова в диалоге с нейросетью (я взял пока себе ник для учётки админа - Rector). . . .	Часы электронные Uhbif79 12.08.2026 Выкладываю программу часов. Программа позволяет: 1. Использовать системное время и дату, 2. Есть возможность вводить время и дату вручную. 3. Реализованы 2 будильника: начало и конец рабочего дня. . . .	Часы с будильником на основе класса QLCDNumber Uhbif79 12.08.2026 Всем добрый день, выкладываю программу часов с будильником на основе класса QLCDNumber. Здесь я пробовал самостоятельно создавал классы, впервые столкнулся с видимостью переменной одного класса из. . .

@locm 7161 / 3338 / 344 Регистрация: 28.10.2011 Сообщений: 13,167 Записей в блоге: 7
	09.05.2018, 20:57
	Сообщение было отмечено Quiet Snow как решение Решение Тест Тьюринга не пройден. 0

@CoderHuligan 1753 / 1019 / 257 Регистрация: 30.06.2015 Сообщений: 5,132 Записей в блоге: 56
	10.05.2018, 14:46
	Вообще, - что вы зациклились на быстрой сортировке?! В реальных проектах её всё равно ОПАСНО использовать. Поэтому, лучше не надо. Есть достойный конкурент: сортировка Шелла. Никакой рекурсии, никакого срыва стека. Работает очень быстро, сам игрался с разными сортировками и проводил бенчмарки. Самые быстрые сортировки это Шелл и квиксорт. Причём шелл практически не уступает быстрой, а иногда и превосходит её. 0

@Замабувараев COM‐пропагандист 936 / 785 / 149 Регистрация: 18.12.2014 Сообщений: 2,256 Записей в блоге: 4
	14.05.2018, 11:00
	Чат, самая лучшая сортировка — это корзинная сортировка. И вот почему. 1. Это сортировка без сравнений. 2. Сложность О(n). 0

@Замабувараев COM‐пропагандист 936 / 785 / 149 Регистрация: 18.12.2014 Сообщений: 2,256 Записей в блоге: 4
	14.05.2018, 17:09
	locm, а что корзинная сортировка — это сортировка без сравнений, не смутило? 0

Quicksort qbasic быстрая сортировка половиной и МЫ

Решение