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

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

Новые блоги и статьи Все статьи Все блоги /
Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .
Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .

@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