[РЕШЕНО][VB] quicksort qbasic быстрая сортировка половиной

[Arigato]

Сообщение от сфинкс

предвижу реализованная на том же языке программирования
Русская Сортировка Половинами сортирует те же данные быстрее

Ошиблись, не будет она быстрее.

А с чего такое название, почему русская? Вы вот по-русски толком мысли излагать не можете, а сортировку назвали "русской". Из-за чего у вас проблемы с изложением своих мыслей? Вроде как территориально вы из РФ. Вас вообще люди понимают?

[kvitaliy]

Сообщение от сфинкс

ускоряющее развитие:
вместо 2-мерного массива 2 массива d(N) и a(N)

сортирует 1000ооо за 2,2 секунды
сортирует миллион за 2,2 секунды
sorts 1'000'000 in 2.2 seconds
сортирует 1'000'000 за 2,2 секунды

Сообщение от сфинкс

предвижу реализованная на том же языке программирования
Русская Сортировка Половинами сортирует те же данные быстрее

Предвижу, что работает медленнее, чем встроенная стандартная сортировка.
Начнём тест? Возьму массив на 10'000'000, современный компилятор это вам не интерпретатор QB64, работает в десятки раз быстрее.
sorterr.png
Время сортировки - сортирует 10'000'000 за 2,15 секунды
Стандартная сортировка в том же коде это делает в 2 раза БЫСТРЕЕ, за 1,04 сек.
Обратите внимание на правильность сортировки. Первые 20 значений сортировка не верно сделана, многие значения перепутаны местами. Особенно последние 10 значений вообще не отсортированы.

Вывод:Алгоритм сортировки работает долго, работает не верно.
P.S. Предвижу Автору всё равно на тесты. Сейчас начнёт обычный бред типа такого

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

Кому интересно, исходный текст на PB и скомпилированный вариант

[сфинкс]

красными овалами выделены
ошибки алгоритма ошибшегося
и в счётчике скачивания 1 раз мой

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

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

благо в моей программе включается
управление количеством N=
и возможно считывать из c:/N.txt
что удобнее при наличии EXE

и возможны варианты заполнения
FOR i=1 TO n: d(i)=n-i+1: NEXT ' обратный
'FOR i=1 TO n STEP 2: d(i)=n-i+1: d(i+1)=d(i): NEXT ' несколько одинаковых
'FOR i=1 TO n: d(i)=INT(RND*n): NEXT ' случайные

и вывод результатов на диск
убрав ' в строках перед остановкой END

в сообщении 76
http://programmersforum.ru/showpost....5&postcount=76

итого план создания новых версий РСП/RSH
ввиду важности все пункты под номером 1

1. проверить мою программу РСП/RSH в QB64 на 100000
1. проверить мою программу РСП/RSH в QB64 на 1000000 и более
1. сочинить свою программу на своём языке программирования
1. проверить свою программу на 100000 и на 1000000 и более

[kvitaliy]

Сообщение от сфинкс

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

Смысл использовать алгоритм, который невозможно переместить на другой язык программирования? Ни кто не станет использовать такой алгоритм, который только для QB64.
Если считаете, что я ошибся при переписывании, то сравните, и покажите, что именно там переписано не так? Код сортировки одинаковый 1:1

Procedure RussianSortingHalvesDAV (Lev, Prv, Zikl, Nauka)
; If Prv-Lev < 1 THEN EXIT SUB
  If Prv-Lev < 1 :ProcedureReturn 0: EndIf
   For i=Lev To Prv
       Summ=Summ+d(i)
   Next
Sred=Summ/(Prv-Lev+1)

Levo=Lev-1
Prav=Prv+1

For i=Lev To Prv
  
  If d(i) < Sred ;THEN
    Levo=Levo+1: Mesto=Levo:
  Else
    Prav=Prav-1: Mesto=Prav
  EndIf  
 a(Mesto)=d(i)
Next

For i=Lev To Prv: d(i)=a(i): Next

If Zikl < Nauka ;THEN
 If Levo >= Lev :RussianSortingHalvesDAV(Lev, Levo, Zikl+1, Nauka):EndIf
 If Prav <= Prv :RussianSortingHalvesDAV(Prav, Prv, Zikl+1, Nauka): EndIf
EndIf

EndProcedure

И исходный код

SUB RussianSortingHalvesDAV (Lev, Prv, Zikl, Nauka)

IF Prv-Lev < 1 THEN EXIT SUB

FOR i=Lev TO Prv
 Summ=Summ+d(i)
NEXT
Sred=Summ/(Prv-Lev+1)

Levo=Lev-1
Prav=Prv+1

FOR i=Lev TO Prv
 IF d(i) < Sred THEN Levo=Levo+1: Mesto=Levo: ELSE Prav=Prav-1: Mesto=Prav
 a(Mesto)=d(i)
NEXT

FOR i=Lev TO Prv: d(i)=a(i): NEXT

IF Zikl < Nauka THEN
 IF Levo >= Lev THEN CALL RussianSortingHalvesDAV(Lev, Levo, Zikl+1, Nauka)
 IF Prav <= Prv THEN CALL RussianSortingHalvesDAV(Prav, Prv, Zikl+1, Nauka)
END IF

END SUB

Где хотя бы одно различие?

[сфинкс]

1. проверить мою программу РСП/RSH в QB64 на 100000
1. проверить мою программу РСП/RSH в QB64 на 1000000 и более

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

[kvitaliy]

Сообщение от сфинкс

ошибки алгоритма ошибшегося

При чем тут программа, если кривой алгоритм? Ни кто не станет использовать конкретно эту программу для практических целей. Всем нужен алгоритм. А он не работает. А если бы и работал, то всё равно медленный.

[сфинкс]

точнее: "он не работает" в одной из реализаций
на непредсказуемом языке программирования
и небось пора сообщать разработчикам про их ошибку в пюрэ-бейсик

зато и алгоритм и программа работают в Excel & QB64 & QBasic
однако почему не стартовала программа с у-2-енным массивом неизвестно

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

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

и не делает лишних испытаний т.к. нечто сортируется минуту

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

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

что важно понимать всё больше и больше:
Русская Сортировка Половинами и скорая и человеческая
Russian Sorting Halves and fast and human

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

и наиболее новой является программа из сообщения 76
http://programmersforum.ru/showpost....5&postcount=76

[kvitaliy]

Сообщение от сфинкс

на непредсказуемом языке программирования

До вашего алгоритма у меня небыло повода усомнится в его возможностях.
Десятки переведённых программ с Делфи, Си, VB6 работают как задумано.
Попробуйте как положено объявить или декларировать все переменные в своём коде.
Возможно и прояснятся какие нюансы.

[сфинкс]

проверить бы мою программу из сообщ. №76
в QB64 на 100000 и на 1000000 и более

мои результаты: всё работает
и специально не выдаю готовые bas & exe
дабы все сами испытали

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

и вдобавок алгоритм РСП/RSH приносит пользу проверяя языки

возможно было бы расставить контрольные точки
да не знаю как пюрэ-бейсик пишет на диск и как считывает
поэтому реализация QB64 ещё более качественная

добавлено экранное кино с контролем массива

[сфинкс]

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

внезапно включился правильно алгоритм

PureBasic Russian Sorting Halves Recursive
сортирует 1000000 за 0,3 секунды

; Russian Sorting Halves Danilin
OpenConsole()
Declare RussianSortingHalvesDAV (Lev, Prv, Zikl, Nauka)

n=12345678

Nauka=Int(1+(Log(n)/Log(2)))
Global Dim  d(n) 
Global Dim  a(n) 

For i=1 To n
  ;d(i)=Random(n,1) ; случайные значения от 1 до n
  d(i)=n-i+1;
Next 

   ;  вывод исходных значений до сортировки
PrintN(" Исходный без сортировки Первые 20")
For k=1 To 20: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Последние 10")
For k=n-9 To n : Print(" "+ d(k)): Next: PrintN("")

start=ElapsedMilliseconds() ; Включаем таймер для RussianSortingHalvesDAV

If Nauka > 0 :
  RussianSortingHalvesDAV(1, n, 1, Nauka)
EndIf

finish=ElapsedMilliseconds()  ; Выключаем таймер для RussianSortingHalvesDAV

PrintN("*********************************************")
PrintN(" После сортировки RussianSorting Первые 50")
For k=1 To 50: Print(" "+ d(k)): Next: PrintN("")
PrintN(" Последние 20")
For k=n-19 To n : Print(" "+ d(k)): Next: PrintN("")

PrintN( "Время сортровки RussianSorting = " + Str(finish-start))
Input()
End

; Процедура сортировки
Procedure RussianSortingHalvesDAV (Lev, Prv, Zikl, Nauka)

  If Prv-Lev < 1 :ProcedureReturn 0
  EndIf ;If Prv-Lev < 1 :ProcedureReturn 0: EndIf

For i=Lev To Prv
  SM=SM+d(i)
Next
Sred=SM/(Prv-Lev+1)

Levo=Lev-1
Prav=Prv+1

For j=Lev To Prv
  If d(j) <= Sred: 
    Levo=Levo+1: Mesto=Levo: 
  Else 
    Prav=Prav-1: Mesto=Prav:
    EndIf
   a(Mesto)=d(j)
Next

For w=Lev To Prv: d(w)=a(w): Next

If Zikl < Nauka :
  If Levo >= Lev :RussianSortingHalvesDAV(Lev, Levo, Zikl+1, Nauka)
  EndIf
  If Prav < Prv :RussianSortingHalvesDAV(Prav, Prv, Zikl+1, Nauka)
  EndIf
EndIf

EndProcedure