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

[сфинкс]

За минувшее лето разобрана программа единомышленника
и создана улучшенная QB64 Qbasic рекурсивная
Русская сортировка половинами Russian Sorting Halves

показывающая результаты:
там где пузырьковая сортирует 100'ооо за 230 секунд
там где пузырьковая половинами 100'ооо за 70 секунд

там Рекурсия Русская сортировка половинами за 0,33 секунды
и миллион сортирует за 3,5 секунды именно в QB64 Qbasic
повторяю: 1'000'ooo сортирует за 3,5 секунды в QB64 Qbasic

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

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

Russian sorting halves important actions visualization


RussianSortingHalvesDAV: Excel рекурсия таблица AlgoLab
только изменённая мной часть RussianSortingHalvesDAV
исправлен ляп лишних вычислений среднего и без лишних переменных
и без замедляющего оформления: сортирует максимум 250 ячеек за 10 секунд
быстрее в 12 раз чем также ускоренная обычная сортировка

' Russian Sorting Halves DANILIN

DECLARE SUB RussianSortingHalvesDAV (j1!, j2!, Level!, LevelMax!)
CLOSE
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n: PRINT n

'n = 1000000

LevelMax = 1 + LOG(n) / LOG(2)
PRINT n, LevelMax

DIM SHARED d(2, n) 'AS LONG

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

FOR i = 1 TO n: d(1, i) = INT(RND * n): NEXT

IF n < 17 THEN FOR k = 1 TO n: PRINT d(1, k);: NEXT: PRINT
IF n > 16 THEN FOR k = n - 10 TO n: PRINT d(1, k);: NEXT: PRINT

start = TIMER

IF LevelMax > 0 THEN
    CALL RussianSortingHalvesDAV(1, n, 1, LevelMax)
END IF

finish = TIMER

IF n < 17 THEN FOR k = 1 TO n: PRINT d(1, k);: NEXT: PRINT
IF n > 16 THEN FOR k = n - 10 TO n: PRINT d(1, k);: NEXT: PRINT

PRINT finish - start

'OPEN "c:/=RuSortHalves_dav.txt" FOR OUTPUT AS #2
'PRINT #2, finish - start; "sekund "
'PRINT #2, n; "elements", "RECURSION"
'FOR i = 1 TO n: PRINT #2, d(1, i): NEXT

END

SUB RussianSortingHalvesDAV (j1, j2, Level, LevelMax)

IF j2 - j1 < 1 THEN EXIT SUB

FOR j = j1 TO j2
    Sum = Sum + d(1, j)
NEXT
Average = Sum / (j2 - j1 + 1)

Levo = j1 - 1
Prav = j2 + 1

FOR j = j1 TO j2
    IF d(1, j) < Average THEN
        Levo = Levo + 1
        Column = Levo
    ELSE
        Prav = Prav - 1
        Column = Prav
    END IF

    d(2, Column) = d(1, j)
NEXT

FOR j = j1 TO j2
    d(1, j) = d(2, j)
NEXT

IF Level < LevelMax THEN
    IF Levo >= j1 THEN CALL RussianSortingHalvesDAV(j1, Levo, Level + 1, LevelMax)
    IF Prav <= j2 THEN CALL RussianSortingHalvesDAV(Prav, j2, Level + 1, LevelMax)
END IF

END SUB

[NetSpace]

так, с цифрами всё понятно - опупенно быстро. а вот с текстом он как работает? может он все найденные на компе папки, сделать в виде списка, отсортированному по алфавиту, ну, пусть хотя бы за те же 12 секунд?

[сфинкс]

на 2-й странице моё сообщение № 13
про сортировку букв и строк

здесь от 28 мая 2018 года

и есть работающий прототип
пока что без рекурсии

http://programmersforum.ru/showthrea...=319604&page=2

[Alex11223]

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

опупенно быстро

По сравнению с чем?
quicksort и т.п. наверняка быстрее велосипеда автора.

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

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

Дык символы это тоже числа.
Ну а поиск папок к сортировке не имеет отношения, это больше зависит от диска, ФС и т.п.

[сфинкс]

сообщение № 71 с программой улучшено:

ничего не считывает и синтезирует массив случайных
зато в конце пишет сортированный на диск
и оставлена возможность включая строки управлять количеством
и очевидно лучший вариант для ЕХЕ: количество N в файле

2 миллиона сортировал 9 секунд и чисто математически понимая у-2-ение:
проверено: за 1 секунду сортирует 270ооо и за минуту сортирует 13 миллионов

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

моя Русская Сортировка Половинами и скорая и человеческая

ещё ускорение программы связано с преодолением сегодняшнего варианта
предусмотренного в материалах свидетельства о гос.рег.пр.ЭВМ:
массив чётный и нечётный и тоже то же у-2-ив массив в длину

что наверняка приводит к замедлению в 2 раза
что показывают счётчики и в excel и в basic
с абсолютно теоретическими результатами

и значит следующее возможное ускоряющее развитие: 2-мерный массив d(log(N;2),N)

и видимо следующее ускорение возможно в другой реализации

а в данном алгоритме включив дополнительный массив этажей
и еле додумавшись до +1 по вертикали для основного массива

даже когда нормально заработала система d(E(j)+2,Column)=d(E(j)+1,j)
всё одно ускорения не произошло т.к. E(j) надо увеличивать +1 каждый раз
что равносильно перекидыванию массива между 2-мя уровнями
и чётно-нечётное число ячеек ещё вдобавок портит

значит следующее возможное ускоряющее развитие: длинный массив d(2*N)
и действительно успешно: сортирует 100ооо за 0,22 секунды

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

' Russian Sorting Halves DANILIN

DECLARE SUB RussianSortingHalvesDAV (j1!, j2!, Level!, LevelMax!)
CLOSE
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n: PRINT n

'n = 1000000

LevelMax = 1 + LOG(n) / LOG(2)
PRINT n, LevelMax

DIM SHARED d(2 * n) 'AS LONG

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

FOR i = 1 TO n: d(i) = INT(RND * n): NEXT

IF n < 17 THEN FOR k = 1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k = n - 10 TO n: PRINT d(k);: NEXT: PRINT

start = TIMER

IF LevelMax > 0 THEN
    CALL RussianSortingHalvesDAV(1, n, 1, LevelMax)
END IF

finish = TIMER

IF n < 17 THEN FOR k = 1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k = n - 10 TO n: PRINT d(k);: NEXT: PRINT

PRINT finish - start

'OPEN "c:/=RuSortHalves_dav.txt" FOR OUTPUT AS #2
'PRINT #2, finish - start; "sekund "
'PRINT #2, n; "elements", "RECURSION"
'FOR i = 1 TO n: PRINT #2, d(i): NEXT

END

SUB RussianSortingHalvesDAV (j1, j2, Level, LevelMax)

IF j2 - j1 < 1 THEN EXIT SUB

FOR j = j1 TO j2
    Sum = Sum + d(j)
NEXT
Average = Sum / (j2 - j1 + 1)

Levo = j1 - 1
Prav = j2 + 1

FOR j = j1 TO j2
    IF d(j) < Average THEN
        Levo = Levo + 1
        Column = Levo
    ELSE
        Prav = Prav - 1
        Column = Prav
    END IF

    d(n + Column) = d(j)
NEXT

FOR j = j1 TO j2
    d(j) = d(n + j)
NEXT

IF Level < LevelMax THEN
    IF Levo >= j1 THEN CALL RussianSortingHalvesDAV(j1, Levo, Level + 1, LevelMax)
    IF Prav <= j2 THEN CALL RussianSortingHalvesDAV(Prav, j2, Level + 1, LevelMax)
END IF

END SUB

[сфинкс]

ускоряющее развитие:
вместо 2-мерного массива 2 массива d(N) и a(N)
и действительно успешно: сортирует 100ооо за 0,22 секунды

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

' Russian Sorting Halves Danilin

DECLARE SUB RussianSortingHalvesDAV (Lev!, Prv!, Zikl!, Nauka!)
CLOSE
OPEN "c:/N.txt" FOR INPUT AS #5
INPUT #5, n: PRINT n

'n=1000000

Nauka=1+LOG(n)/LOG(2)
PRINT n, Nauka

DIM SHARED d(n) 'AS LONG
DIM SHARED a(n) 'AS LONG

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

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

IF n < 17 THEN FOR k=1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k=n-8 TO n: PRINT d(k);: NEXT: PRINT

start=TIMER

IF Nauka > 0 THEN
 CALL RussianSortingHalvesDAV(1, n, 1, Nauka)
END IF

finish=TIMER

IF n < 17 THEN FOR k=1 TO n: PRINT d(k);: NEXT: PRINT
IF n > 16 THEN FOR k=n-8 TO n: PRINT d(k);: NEXT: PRINT

PRINT finish-start

'OPEN "c:/=RuSortHalves_dav.txt" FOR OUTPUT AS #2
'PRINT #2, finish-start; "sekund "
'PRINT #2, n; "elements", "RECURSION"
'FOR i=1 TO n: PRINT #2, d(i): NEXT

END

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

[Arigato]

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

вот код на Delphi.

Для 10000 элементов выдает 0.09 сек.

Модернизировал ваш алгоритм:

const
  N = 100000000; // размер массива
  M = 10000; // диапазон чисел в массиве (от 0 до M-1)
var
  s:array[1..N]of integer; // исходный массив
  t:array[0..M-1] of Integer; // массив-счетчик

procedure TForm1.Button1Click(Sender: TObject);
var i,j,k:Integer;
    Fr,t1,t2:Int64;
    Dt:Extended;
begin
   Randomize;
   QueryPerformanceFrequency(Fr);
   // заполнение массива
   for i:=1 to N do s[i]:=Random(M);
   QueryPerformanceCounter(t1);

   // начало нерусской сортировки
   FillChar(t, SizeOf(t), 0);
   for i := 1 to N do
     inc(t[s[i]]);
   k := 1;
   for i := 0 to M do
     for j := 1 to t[i] do begin
       s[k] := i;
       inc(k);
     end;
   // конец нерусской сортировки

   QueryPerformanceCounter(t2);
   Dt:=(t2-t1)/Fr;
   //for i:=1 to M do RichEdit1.Lines.Add(IntToStr(s[i]));
   Label1.Caption := FloatToStr(RoundTo(Dt,-2))+' сек.';
end;

Для 10К - 0 сек, для 100К - 0 сек, для 1М - 0 сек, для 10М - 0.01 сек, для 100М - 0.1 сек, для 1G - не запустился, что-то Делфя такой массив создать не смогла

Интересно сравнить скорость алгоритма "Русская сОртирОвка пОлОвинами" от сфинкс с приведенной выше "Нерусской сортировкой". Уважаемый сфинктер, за какое время ваш алгоритм сортирует массив со 100 миллионами элементами?

[сфинкс]

в то время как разработчики QB64
лайкнули мой твиттер про Russian Sort Halves

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

а я видя буквы Delphi даже не знаю в чём проверить
зато на QB64 каждый может+должен=обязан проверить сам

максимально доступный размер массива
2^24 = 1,68E+07 = 16,8 миллионов
скорая и человеческая Русская сОртирОвка пОлОвинами
сортирует за 45 секунд на QB64

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

[Arigato]

сфинкс, приведенный выше алгоритм сортирует массив из 100 миллионов элементов за 0.1 секунды.

[сфинкс]

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

и кто-нибудь когда-нибудь проверит мою QB64 программу
у себя на компьютере и наверняка окажется ещё быстрее

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

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