сортировка алгоритм и ликбез про логарифм и МЫ

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

пока не забыл: сортировка в excel

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

и лучше смотрите как реализована визуализация линиями
и там ставьте внизу число линий 25 поменьше
https://airtucha.github.io/SortVis/

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

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

Код:

<code class="hljs vbnet">
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
</code>

Русская Сортировка Половинами Ускоряет Данилин
Russian Sort Halves Accelerate Danilin


Русская сортировка половинами быстрее Данилин
Russian Sort Halves faster Danilin

 

остающиеся 2 элемента удобно сортировать
ища через «если» из 2 вариантов аб ба
и 3 элемента сортировать ища через «если»
из 6 вариантов абв авб бав бва вба ваб

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


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

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

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

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

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

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

4-кратное ускорение
a 4 times acceleration proof

'RUSSIAN sorting halves 4 part bubble
N = 17539
DIM d(N), a(N), v(N), q(5)
RANDOMIZE TIMER: FOR i = 1 TO N: d(i) = INT(RND * N): NEXT
FOR k = 1 TO 10: PRINT d(k);: NEXT: PRINT: FOR k = N — 9 TO N: PRINT d(k);: NEXT: PRINT: PRINT

start = TIMER: s = 0

' ALL
summa = 0: FOR i = 1 TO N: summa = summa + d(i): NEXT: middle = summa / N: y = 1: z = 0
FOR i = 1 TO N
    IF d(i) < middle THEN a(y) = d(i): y = y + 1: ELSE a(N — z) = d(i): z = z + 1
NEXT
q(3) = y — 1
PRINT «ALL middle = »; middle
FOR k = 1 TO 10: PRINT a(k);: NEXT: PRINT: FOR k = N — 9 TO N: PRINT a(k);: NEXT: PRINT: PRINT

'1 FROM 2
summa = 0: FOR i = 1 TO q(3): summa = summa + a(i): NEXT: middle = summa / q(3): y = 1: z = 0
PRINT «1 FROM 2 = »; middle, «1 ...»; q(3)
FOR i = 1 TO q(3)
    IF a(i) < middle THEN v(y) = a(i): y = y + 1: ELSE v(q(3) — z) = a(i): z = z + 1
NEXT
FOR k = 1 TO 10: PRINT v(k);: NEXT: PRINT: FOR k = q(3) — 9 TO q(3): PRINT v(k);: NEXT: PRINT: PRINT
q(2) = y — 1

'2 FROM 2
summa = 0: FOR i = q(3) + 1 TO N: summa = summa + a(i): NEXT: middle = summa / (1 + N — q(3)): y = q(3): z = 0
PRINT «2 FROM 2 = »; middle, q(3) + 1; "..."; N
FOR i = q(3) TO N
    IF a(i) < middle THEN v(y) = a(i): y = y + 1: ELSE v(N — z) = a(i): z = z + 1
NEXT
FOR k = q(3) TO q(3) + 10: PRINT v(k);: NEXT: PRINT: FOR k = N — 9 TO N: PRINT v(k);: NEXT: PRINT: PRINT
q(4) = y — 1: q(1) = 2: q(5) = N

' SORTING
PRINT «1=»; 1, «2=»; q(2), «3=»; q(3), «4=»; q(4), «5=»; N: PRINT
FOR t = 1 TO 4
    FOR i = q(t) — 1 TO q(t + 1): FOR j = i + 1 TO q(t + 1)
            IF v(i) > v(j) THEN SWAP v(i), v(j): s = s + 1
NEXT: NEXT: NEXT

finish = TIMER

FOR k = 1 TO 10: PRINT v(k);: NEXT: PRINT: FOR k = N — 9 TO N: PRINT v(k);: NEXT: PRINT: PRINT
PRINT «DA RUS 4 », finish — start; «second », «swap »; s

OPEN «c:/RUsortdav4.txt» FOR OUTPUT AS #2
PRINT #2, finish — start; «second », «swap »; s
PRINT #2, N; «Russian sorting halves 4 parts bubble „
FOR i = 1 TO 20: PRINT #2, v(i): NEXT
FOR i = N — 19 TO N: PRINT #2, v(i): NEXT

start = TIMER: s = 0
FOR i = 1 TO N: FOR j = i + 1 TO N
        IF d(i) > d(j) THEN SWAP d(i), d(j): s = s + 1
NEXT: NEXT
finish = TIMER

PRINT “BUBBLE », finish — start; «second », «swap »; s
END

RussianSortingHalvesDAV.bas: рекурсия QB64 Qbasic QuickBasic Basic рекурсия

ускоряющее развитие:
вместо 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 (ab!, yz!, part!, age!)
CLOSE
OPEN «c:/N.txt» FOR INPUT AS #5
INPUT #5, n: PRINT n

'n=123456

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

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)
'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 '

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 age > 0 THEN
 CALL RussianSortingHalvesDAV(1, n, 1, age)
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 22: PRINT #2, d(i): NEXT
FOR i=n-22 TO n: PRINT #2, d(i): NEXT

FOR k=1 TO 20: PRINT d(k);: NEXT: PRINT: PRINT
FOR k=n-9 TO n: PRINT d(k);: NEXT: PRINT: PRINT

END

SUB RussianSortingHalvesDAV (ab, yz, part, age)

IF yz-ab < 1 THEN EXIT SUB

FOR i=ab TO yz
 summa=summa+d(i)
NEXT
middle=summa/(yz-ab+1)

abc=ab-1
xyz=yz+1

FOR i=ab TO yz
 IF d(i) < middle THEN abc=abc+1: a(abc)=d(i): ELSE xyz=xyz-1: a(xyz)=d(i)
NEXT

FOR i=ab TO yz: d(i)=a(i): NEXT

IF part < age THEN
 IF abc >= ab THEN CALL RussianSortingHalvesDAV(ab, abc, part+1, age)
 IF xyz <= yz THEN CALL RussianSortingHalvesDAV(xyz, yz, part+1, age)
END IF

END SUB

PureBasic Русская Сортировка Половинами и скорая и человеческая
PureBasic Russian Sorting Halves and fast and human

считывает только количество из c:/N.txt
удобно чтобы обходиться без оболочки PureBasic
и сортировав хоть миллиарды пишет по 1000
наименьших и наибольших в c:/RSH_DAV.txt

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

; Russian Sorting Halves Danilin
OpenConsole()
Declare RussianSortingHalvesDAV (ab, yz, part, age)

;n=12345678

If ReadFile(0, «c:/N.txt»)
 n=Val(ReadString(0))
 CloseFile(0)
EndIf

age=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(); таймер

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

finish=ElapsedMilliseconds(); таймер

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))

If OpenFile(0, «c:/RSH_DAV.txt»)
 For k=1 To 1000 :WriteString (0, " " +d(k)): Next
 For k=n-1001 To n :WriteString (0, " " +d(k)): Next
 CloseFile(0)
EndIf

Input()
End

; Процедура сортировки
Procedure RussianSortingHalvesDAV (ab, yz, part, age)

If yz-ab < 1 :ProcedureReturn 0
EndIf

For i=ab To yz
summa=summa+d(i)
Next
middle=summa/(yz-ab+1)

abc=ab-1
xyz=yz+1

For j=ab To yz
If d(j) <= middle:
abc=abc+1: a(abc)=d(j)
Else
xyz=xyz-1: a(xyz)=d(j)
EndIf

Next

For w=ab To yz: d(w)=a(w): Next

If part < age :
If abc >= ab :RussianSortingHalvesDAV(ab, abc, part+1, age)
EndIf
If xyz < yz :RussianSortingHalvesDAV(xyz, yz, part+1, age)
EndIf
EndIf

EndProcedure

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

Русская Сортировка Третями
распределяющая: меньше трети и больше двух третей
выглядит бесконечно при рекурсии
ведь непонятно как переходить между третями

Зато делить массив на 3/9/27 частей очевидно легко
в то время как Русская сортировка половинами делит
массив на 2/4/8 частей как Русская Сортировка Осьмушками

Russian Sorting Halves and fast and human
sorts 1'000'000 in 0.2 seconds on C# Csharp

Код:

<code>
// RUSSIAN SORTING HALVES DANILIN
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace davApp
{
    class Program
    {
        private long age;
        static long[] a;
        static long[] d;

        static void Main(string[] args)
        {
            int n = 0;
            // READ NUMBERS
            var inpFile = new StreamReader("N.txt");
            n = Convert.ToInt32(inpFile.ReadLine());
            inpFile.Close();

            var age = 1 + Math.Log(n) / Math.Log(2);

            Console.WriteLine(n);

            a = new long[n + 1];
            d = new long[n + 1];

            for (int i = 1; i <= n; i++)
                d[i] = n - i + 1;

            //var rand = new Random();
            //// RANDOM [1;n]
            //for (int i = 1; i <= n; i++)
            //    d[i] = rand.Next(1, n);

            // REAN N LINE FROM FILE
            //inpFile = new StreamReader("ISX.txt");
            //for (int i = 1; i <= n; i++)
            //    d[i] = Convert.ToInt64(inpFile.ReadLine());
            //inpFile.Close();

            // WRITE ON SCREEN
            int m = Math.Min(n, 20);
            for (int i = 1; i <= m; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();

            // RUSSIAN SORTING HALVES DANILIN
            var start = DateTime.Now;
            if (age > 0)
                dav(1, n, 1, age);
            var finish = DateTime.Now;

            Console.WriteLine("{0} second", (finish - start).TotalSeconds);

            // WRITE ON SCREEN
            Console.WriteLine("[1..{0}]", m);
            for (int i = 1; i <= m; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();

            // WRITE ON SCREEN
            Console.WriteLine("[{0}..{1}]", n - m + 1, n);
            for (int i = n - m + 1; i <= n; i++)
                Console.Write("{0} ", d[i]);
            Console.WriteLine();

            // WRITE IN FILE
            var outFile = new StreamWriter("dav.txt");
            for (int i = 1; i <= m; i++)
                outFile.WriteLine(d[i]);
            outFile.WriteLine();

            for (int i = n - m + 1; i <= n; i++)
                outFile.WriteLine(d[i]);
            outFile.WriteLine();
            outFile.Close();

            Console.WriteLine("Press any key");
            Console.ReadKey();
        }

        static void dav(int ab, int yz, int part, double age)
        {
            if (yz - ab < 1)
                return;

            long summa = 0;
            for (int i = ab; i <= yz; i++)
                summa = summa + d[i];

            double middle = summa / (yz - ab + 1.0);

            var abc = ab - 1;
            var xyz = yz + 1;

            for (int i = ab; i <= yz; i++)
                if (d[i] < middle)
                {
                    abc = abc + 1;
                    a[abc] = d[i];
                }
                else
                {
                    xyz = xyz - 1;
                    a[xyz] = d[i];
                }

            for (int i = ab; i <= yz; i++)
                d[i] = a[i];

            if (part < age)
            {
                if (abc >= ab) dav(ab, abc, part + 1, age);
                if (xyz <= yz) dav(xyz, yz, part + 1, age);
            }
            return;
        }
    }
}
</code>

Russian Sorting Halves and fast and human
sorts 1'000'000 in 2.2 seconds on QB64
sorts 1'000'000 in 0.3 seconds on PureBasic
sorts 1'000'000 in 0.2 seconds on C# Csharp

разделение пузырьковой сортировки на 4 части
ускоряет в 4 раза и данный пример C# и выше qb64
чудесные примеры для обучения включающие важное



Z = N*(N-1)/2
Z = 4*(N/4*(N/4-1)/2+2*N/4)
Z = log(N;2)*(N/log(N;2)*(N/log(N;2)-1)/2+2*N/log(N;2))

// Russian Sorting Halves 4 part accelerate bubble sorting
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace octoberApp
{
 class Program
 {
 static int n;
 static double[] d;
 static double[] a;
 static double[] v;
 static int[] q;

 static void Main(string[] args)
 {
 n = 37519;

 d = new double[n+1];
 a = new double[n+1];
 v = new double[n+1];
 q = new int[5+1];
 var rand = new Random();
 for (int i = 1; i <= n; i++)
 d[i] = Math.Truncate(rand.NextDouble() * n);

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", d[i]);
 Console.WriteLine();

 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", d[i]);
 Console.WriteLine();
 Console.WriteLine();

 var start = DateTime.Now;
 var s = 0;
 //ALL
 double summa = 0;
 for (int i = 1; i <= n; i++)
 summa += d[i];
 double middle = summa / n;
 var y = 1;
 var z = 0;

 for (int i = 1; i <= n; i++)
 if (d[i] < middle)
 {
 a[y] = d[i]; y++;
 }
 else
 {
 a[n — z] = d[i];
 z++;
 }

 q[3] = y — 1;
 Console.WriteLine(«ALL middle = {0}», middle);

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", a[i]);
 Console.WriteLine();
 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", a[i]);
 Console.WriteLine();
 Console.WriteLine();

 // 1 FROM 2
 summa = 0;
 for (int i = 1; i <= q[3]; i++)
 summa += a[i];

 middle = summa / q[3];
 y = 1;
 z = 0;
 Console.WriteLine(«1 FROM 2 = {0} 1 ...{1}», middle, q[3]);

 for (int i = 1; i <= q[3]; i++)
 if (a[i] < middle)
 {
 v[y] = a[i]; y++;
 }
 else
 {
 v[q[3] — z] = a[i];
 z++;
 }

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 for (int i = q[3] — 9; i <= q[3]; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 Console.WriteLine();

 q[2] = y — 1;

 // 2 FROM 2
 summa = 0;
 for (int i = q[3] + 1; i <= n; i++)
 summa += a[i];
 middle = summa / (1 + n — q[3]);
 y = q[3];
 z = 0;
 Console.WriteLine(«2 FROM 2 = {0} {1}...{2}», middle, q[3] + 1, n);
 for (int i = q[3]; i <= n; i++)
 if (a[i] < middle)
 {
 v[y] = a[i]; y++;
 }
 else
 {
 v[n — z] = a[i];
 z++;
 }
 for (int i = q[3]; i <= q[3] + 10; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 Console.WriteLine();

 q[4] = y — 1;
 q[1] = 2;
 q[5] = n;

 //BUBBLE
 Console.WriteLine(«1= {0} 2= {1} 3= {2} 4= {3} 5= {4}», 1, q[2], q[3], q[4], n);
 Console.WriteLine();

 for (int t = 1; t <= 4; t++)
 for (int i = q[t] — 1; i <= q[t + 1]; i++)
 for (int j = i + 1; j <= q[t + 1]; j++)
 if (v[i] > v[j])
 {
 var x = v[i];
 v[i] = v[j];
 v[j] = x;
 s++;
 }

 var finish = DateTime.Now;

 for (int i = 1; i <= 10; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();

 for (int i = n — 9; i <= n; i++)
 Console.Write("{0} ", v[i]);
 Console.WriteLine();
 Console.WriteLine();
 Console.WriteLine(«DArus4 {0} second swap {1}», (finish — start).TotalSeconds, s);

 start = DateTime.Now;
 s = 0;

 for (int i = 1; i <= n; i++)
 for (int j = i + 1; j <= n; j++)
 if (d[i] > d[j])
 {
 var x = d[i];
 d[i] = d[j];
 d[j] = x;
 s++;
 }
 finish = DateTime.Now;

 Console.WriteLine(«BUBBLE {0} second swap {1}», (finish — start).TotalSeconds, s);

 Console.WriteLine(«Press any key»);
 Console.ReadKey();
 }
 }
}