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

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

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

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

Там стопудово маппинг, раскидывает по диапазонам, а дальше кусочки каким-то из быстрых добивает,
т.е. компромисс сжираемой памяти и скорости.
В потоке, кстати можно проверить сколько стека жрёт, убавлять стек, пока не крешнет.
Кинь *.EXE, посмотрю у себя это чудо.

@sfinx78 · 08.05.2018, 13:09 **[ТС]**

мной проверено и не работает sortdemo.bas
в разных qb* и в turbobasic tb*

@vlisp · 08.05.2018, 13:24

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

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

это похоже на машинный перевод, возможно бот (нейросеть?), возможно вообще не с этой планеты или азиат

@CoderHuligan · 08.05.2018, 13:34

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

возможно вообще не с этой планеты или азиат

Он не ОДНО, их МНОГО.)))

@Quiet Snow · 08.05.2018, 13:49

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

мной проверено и не работает sortdemo.bas

Специально для криворукого сфинкса, который 3 страницы плачется и не может запустить
элементарную прогу на QuickBasic:
https://yadi.sk/i/wLP7ngBE3VXzqk

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

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

Он не ОДНО, их МНОГО.)))

Ну да, там ещё И ЛЫСАЯ СОБАКА участвует и "миллионы читателей".

@CoderHuligan · 08.05.2018, 14:03

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

"миллионы читателей"

Наверно секта "Мы ненавистники сортдемобас!")))

@Quiet Snow · 08.05.2018, 14:17

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

Наверно секта "Мы ненавистники сортдемобас!")))

Ага, надо ещё его сорт проверить, пока петушок в ретузы не дал...

Прикиньте гугл со своей нейросетки AlphaZero начнёт так обстреливать нас бедолаг.
Это же полностью парализует всю полезную активность на конференциях.

@sfinx78 · 08.05.2018, 15:08 **[ТС]**

проверим выполнены ли условия:

цитата Сегодня, 13:53

чтобы sortdemo.bas работал в своей
оболочке в windows 7 без эмулятора

цитата Сегодня, 13:58

важно: чтобы sortdemo.bas работал в своей
оболочке в windows 7 без эмулятора

итого: условия не выполнены

и ввиду того что sortdemo.bas
невозможно приспособить к соревнованиям
значит sortdemo.bas выбывает из соревнований

о невозможности приспособить к соревнованиям:

? за сколько секунд сортирует 100ооо ячеек
заполненных потенциально невыгодным образом
в 1-й половине массива от большего к меньшему
и во 2-й половине массива от меньшего к большему ?

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

оказывается невозможно ввести массивы
много тысячные максимум кажись до 10ооо

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

в dosbox мой сортировал 5ооо ячеек 25ооо проходов за 7оо секунд
в qb64 мой сортировал 5ооо ячеек те же 25ооо проходов за о.3 секунды

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

вывод: важно: чтобы сортировка работала
в своей оболочке в windows 7 без эмулятора

и напоминаю: кому непонятно
пишите какие абзацы непонятные
и пока никто не показал что именно не понятно

@Quiet Snow · 08.05.2018, 15:19

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

проверим выполнены ли условия:
цитата Сегодня, 13:53
чтобы sortdemo.bas работал в своей
оболочке в windows 7 без эмулятора
цитата Сегодня, 13:58
важно: чтобы sortdemo.bas работал в своей
оболочке в windows 7 без эмулятора
итого: условия не выполнены

Сфинкс боюсь сейчас ты не в том положении, чтобы диктовать какие-то там условия,
ибо дал в ретузы ты мощно.
Поэтому свои требования про Windows7 и прочее засунь себе глубоко и подальше.

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

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

много тысячные максимум кажись до 10ооо

Ну все всё видят да

Очень показательно.

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

в qb64 мой сортировал 5ооо ячеек те же 25ооо проходов за о.3 секунды

Это дно днистое. С такими результатами любой софт, где ты используешь свою голимую
сортировку - будет безбожно лагать.

@sfinx78 · 08.05.2018, 15:20 **[ТС]**

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

алгоритм от профффессионалов 20-го века
медленный донельзя и тормозящийся эмулятором

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

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

да ещё читал возможно переставлять
без доп переменной и без swap

и пока не обнаружено ничего нового
значит соревнуются кажись 3 basic сортировки

@Quiet Snow · 08.05.2018, 15:21

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

и напоминаю: кому непонятно
пишите какие абзацы непонятные
и пока никто не показал что именно не понятно

Да все уже всё поняли. Щас я ещё видос сниму про твою обоссанную сортировку,
которая 10 секунд лопатит массив из 100000 элементов и можно будет расходиться.

@locm · 08.05.2018, 15:52

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

Кинь *.EXE, посмотрю у себя это чудо.

В архиве.

@Quiet Snow · 08.05.2018, 16:02

Наслаждайтесь парни:
https://yadi.sk/i/TusD3iRy3VYR8V

Оставляю вас наедине с виртуозом программистом.

Добавлено через 49 секунд

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

В архиве.

ok, спасибо дядь, посмотрю.

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

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

В архиве.

2.3 секунды. XEON X5470 4 ядра.

@sfinx78 · 08.05.2018, 16:36 **[ТС]**

10 секунд моей сортировки 10ооо ячеек это Победа

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

10 секунд моей сортировки 10ооо ячеек это Победа

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

10 секунд моей сортировки 10ооо ячеек это Победа

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

10 секунд моей сортировки 10ооо ячеек это Победа

@sfinx78 · 08.05.2018, 16:45 **[ТС]**

до 11 секунд

100ооо ячеек

1,7 млрд проходов

467ооо перестановок

@sfinx78 · 08.05.2018, 17:54 **[ТС]**

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

PureBasic
1
2
3
4
5
6
7
8
9
10
#size = 20000000
Dim x.l(#size-1)
 
RandomData(@x(), #size*4) ; Заполнение массива случайными числами.
 
time = ElapsedMilliseconds()
SortArray(x(), #PB_Sort_Ascending) ; Сортировка массива.
time = ElapsedMilliseconds() - time
 
MessageRequester("", StrF(time/1000, 1)+ " секунд")

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

Assembler
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
SUB ASM_QSort(a() AS INTEGER, l AS INTEGER, r AS INTEGER)
  DIM AS INTEGER i=l, j=r, x=a((l+r)\2)
Asm
 QS_L0:              'Do
  mov ecx, [a]
  mov ecx, [ecx]
 QS_L1:
  mov ebx, [i]
  lea edi, [ecx+ebx*4]
  mov ebx, [x]
  cmp [edi], ebx     'While a(i)<x
  jge QS_L2
  inc dword ptr [i]  'i+=1
  jmp QS_L1
 QS_L2:
  mov ebx, [j]
  lea esi, [ecx+ebx*4]
  mov eax, [esi]
  cmp [x], eax       'While x<a(j)
  jge QS_L3
  dec dword ptr [j]  'j-=1
  jmp QS_L2
 QS_L3:
  cmp [i], ebx       'If i<=j Then
  jg QS_L4
  mov eax, [edi]     'Swap a(i), a(j)
  xchg eax, [esi]
  mov [edi], eax 
  inc dword ptr [i]  'i+=1
  dec dword ptr [j]  'j-=1
 QS_L4:
  cmp [i], ebx       'Loop Until i>j
  jle QS_L0
END Asm

значит требуются ещё программы чисто basic
лучше совместимые с qb64

да и посрамлены якобы непонимающие:

тестировавший мой код без GоTо за 10 секунд
разобрался в моём коде молниеносно

что и требовалось доказать

а я пока ещё отточу открытие года

да ещё лайфхак:

чтобы не печатались все 100ооо ячеек = n
легко обособить печать 10 ячеек
FOR k = n-10 TO n: PRINT d(1, k);: NEXT: PRINT
и легче контролируется сортировка

@Quiet Snow · 08.05.2018, 18:31

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

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

Ой какой лапочка, ой как оправдывается. Бедняжке пруфами яйки прищемили под его же правилами....

Прикинь, не знал что вот это "язык низшего уровня"("низшего" звучит как "падшего"

):

QSort

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SUB Qsort(start AS INTEGER,Finish AS UInteger)
  DIM AS UInteger I=start,J=Finish,X=NumArray(INT((I+J)/2)),A
  WHILE  I <= J
    WHILE NumArray(I) < X
      I+=1
    WEND
    WHILE NumArray(J) > X
      J-=1
    WEND
    IF I<=J THEN
      A = NumArray(I)
      NumArray(I) = NumArray(J)
      NumArray(J) = A
      I+=1
      J-=1
    EndIf
  WEND
  IF J > Start THEN Qsort(start,J)
  IF I < Finish THEN Qsort(I,Finish)
END SUB

и вот это

RapidSort

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
SUB RapidSort (Item()AS INTEGER, LoElement AS INTEGER, HiElement AS INTEGER)
  DIM AS INTEGER n, wert, nptr, arr, rep, LoVal, HiVal
  LoVal=Item(LoElement)
  HiVal=Item(HiElement)
  FOR n=LoElement TO HiElement
    IF LoVal> Item(n) THEN LoVal=Item(n)
    IF HiVal< Item(n) THEN HiVal=Item(n)
  NEXT
  REDIM SortArray(LoVal TO HiVal) AS INTEGER
  FOR n=LoElement TO HiElement
    wert=Item(n)
    SortArray(wert)=SortArray(wert)+1
  NEXT
  nptr=LoElement-1
  FOR arr=LoVal TO HiVal
    rep=SortArray(arr)
    FOR n=1 TO rep
      nptr=nptr+1
      Item(nptr)=arr
    NEXT
  NEXT
  ERASE SortArray
END SUB

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

а я пока ещё отточу открытие года

Давай давай, трудись ботан, ГИА и ЕГЭ только не просри, а то сортиры чистить придётся всю оставшуюся.

@Pro_grammer · 08.05.2018, 18:53

Как бы мне не нравился PureBasic, и как бы locm не сомневался в вычислительных способностях FreeBasic
Но как говорится результаты на лицо:

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

В архиве.

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

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

сортировка реализованная на Freebasic

Встроенная функция сортировки PureBasic, которой я давеча хвастался перед кодом на QBasic, как Пурик порвал Qbasic, так же и FreeBasic порвал Пурик

Или Фред плохо сортировку написал, или реально FB считает очень быстро!

@Quiet Snow · 08.05.2018, 19:11

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

Или Фред плохо сортировку написал

Надо по загрузке ядер посмотреть. Есть предположение, что в PB сортировка не жадная на процессор,
т.е. не блокирует жёстко ядра, может какая-нть мелкозернистая. У кого есть точные профайлеры, посмотрите.
Обычный диспетчер задач нифига нормально не показывает по загрузке, всё что я вижу - это 3 ядра,
загруженные примерно на половину, т.е. чисто ориентировочно оно может работать в 2 раза быстрее.

Меня больше удивило другое, асмовая сортировка просирает FB-шной на моём проце. Ну и всё это на
FB не использует потоки, т.е. это можно ещё раза в 3.5 минимум ускорить(т.е. проход, перебрасываем
элементы по значению в 4 отдельных массива, дальше отдаём на каждое ядро).

К тому же, думаю если переписать Rapid на PB, он будет тоже где-то так фигарить, будет разница максимум
в 5% в пользу PB.

@The trick · 08.05.2018, 19:14

Алгоритм сортировки Long значений по возрастанию из PureBasic (из EXE locm'а):

Visual Basic
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
Function SortArray_Long(lArray() As Long, ByVal lFirstIndex As Long, ByVal lLastElement As Long) As Long
    Dim lResult     As Long
    Dim lIndex      As Long
    Dim lLastPart   As Long
    
    lResult = lLastElement - lFirstIndex
    lIndex = lFirstIndex
    
    If (lLastElement - lFirstIndex > 0) Then
    
        Do
            
            lLastPart = Partition(lArray, lIndex, lLastElement)
            SortArray_Long lArray, lIndex, lLastPart
            lIndex = lLastPart + 1
            lResult = lLastElement - lIndex
            
        Loop While (lLastElement - lIndex > 0)
    
    End If
    
    SortArray_Long = lResult
    
End Function
 
Function Partition(lArray() As Long, ByVal lStartIndex As Long, ByVal lEndIndex As Long) As Long
    Dim lLow    As Long
    Dim lHigh   As Long
    Dim lMid    As Long
    Dim lMidIdx As Long
    Dim lTmp    As Long
    
    lLow = lArray(lStartIndex)
    lHigh = lArray(lEndIndex)
    lMidIdx = (lStartIndex + lEndIndex) \ 2
    lMid = lArray(lMidIdx)
    
    ' // Get middle element
    If lLow <= lHigh Then
        If lMid > lLow Then
            If lLow <= lHigh And lMid >= lHigh Then
                lMidIdx = lEndIndex
            End If
        Else
            lMidIdx = lStartIndex
        End If
    End If
    
    ' // Swap
    lMid = lArray(lMidIdx): lArray(lMidIdx) = lLow: lArray(lStartIndex) = lMid
    
    Partition = lEndIndex
    
    Do
    
        Do While lArray(Partition) > lMid
            Partition = Partition - 1
        Loop
        
        Do While lArray(lStartIndex) < lMid
            lStartIndex = lStartIndex + 1
        Loop
        
        If lStartIndex >= Partition Then Exit Do
        
        lTmp = lArray(lStartIndex): lArray(lStartIndex) = lArray(Partition): lArray(Partition) = lTmp
        Partition = Partition - 1
        lStartIndex = lStartIndex + 1
        
    Loop While True
        
End Function

Добавлено через 1 минуту
Pro_grammer, кидай EXE

Новые блоги и статьи Все статьи Все блоги /
Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .	Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .

@sfinx78 Заблокирован
	08.05.2018, 13:09 [ТС]
	мной проверено и не работает sortdemo.bas в разных qb* и в turbobasic tb* 0

@sfinx78 Заблокирован
	08.05.2018, 15:08 [ТС]
	проверим выполнены ли условия: цитата Сегодня, 13:53 чтобы sortdemo.bas работал в своей оболочке в windows 7 без эмулятора цитата Сегодня, 13:58 важно: чтобы sortdemo.bas работал в своей оболочке в windows 7 без эмулятора итого: условия не выполнены и ввиду того что sortdemo.bas невозможно приспособить к соревнованиям значит sortdemo.bas выбывает из соревнований о невозможности приспособить к соревнованиям: ? за сколько секунд сортирует 100ооо ячеек заполненных потенциально невыгодным образом в 1-й половине массива от большего к меньшему и во 2-й половине массива от меньшего к большему ? у меня подобное заполнение массива в 1 строчку оказывается невозможно ввести массивы много тысячные максимум кажись до 10ооо и ещё вдобавок в эмуляторе заведомо медленно да и не считает перестановки хотя могли додуматься "профффессионалы" в dosbox мой сортировал 5ооо ячеек 25ооо проходов за 7оо секунд в qb64 мой сортировал 5ооо ячеек те же 25ооо проходов за о.3 секунды Нобелевская премия сама себя не получит вывод: важно: чтобы сортировка работала в своей оболочке в windows 7 без эмулятора и напоминаю: кому непонятно пишите какие абзацы непонятные и пока никто не показал что именно не понятно 0

@sfinx78 Заблокирован
	08.05.2018, 15:20 [ТС]
	лучше я засуну подальше тянущий резину за хвост в долгий ящик алгоритм от профффессионалов 20-го века медленный донельзя и тормозящийся эмулятором и никому не нужный для ускорения и для использования т.к. непонятно как сортировать именно свои данные и не считающий число перестановок а ведь число перестановок важнее времени при испытании логики алгоритмов да ещё читал возможно переставлять без доп переменной и без swap и пока не обнаружено ничего нового значит соревнуются кажись 3 basic сортировки 0

@sfinx78 Заблокирован
	08.05.2018, 16:36 [ТС]
	10 секунд моей сортировки 10ооо ячеек это Победа мне хоть и жалко мегабайт на мега кино зато минуты в конце со счётчиками посмотрел 10 секунд моей сортировки 10ооо ячеек это Победа потому как другой алгоритм использует язык низшего уровня сами убедитесь и не случайно чужая программа скрыта и нужно нажимать спойлер 10 секунд моей сортировки 10ооо ячеек это Победа и вдобавок мой алгоритм ускоряется единственным проходом и большее число проходов логарифмически зависимы и пока с сортировкой глубже моей программы нету 10 секунд моей сортировки 10ооо ячеек это Победа 0

@sfinx78 Заблокирован
	08.05.2018, 16:45 [ТС]
	до 11 секунд 100ооо ячеек 1,7 млрд проходов 467ооо перестановок Миниатюры 0